Wyniki wyszukiwania - BazTech

1

Algorytmizacja procesu wyznaczania długości ścieżek w sieci rozbudowanej podstawą optymalizacji zagadnień transportowych

Ignaciuk S., Wawrzosek J., Kubera E., Baryła-Paśnik M., Piekarski W.

Logistyka

|

2015

|

nr 5

145--154, CD1

PL

Matematyczne metody optymalizacyjne służą jako narzędzie wykorzystywane przy podejmowaniu decyzji w działalności transportowej. Graf jest powszechnie stosowany do prezentacji problemów logistycznych. Znanym zagadnieniem w literaturze przedmiotu jest wyznaczanie najkrótszej ścieżki w grafie nie-skierowanym o nieujemnych wagach na krawędziach pomiędzy dwoma węzłami tej sieci. Odmianą tego zagadnienia jest problem znalezienia najkrótszych ścieżek pomiędzy wszystkimi parami węzłów grafu. Działanie takie w zakresie zagadnień transportowych ma na celu utworzenie pełnej macierzy odległości między wszystkimi węzłami grafu (wyznaczenie najkrótszych odległości między wszystkimi punktami na-dania i odbioru towaru). Współczesne techniki informatyczne pozwalają na przechowywanie w pamięci komputera pełnych danych zawierających informację obejmującą odległość między dwoma dowolnymi węzłami sieci i ciąg węzłów opisujących tą najkrótszą ścieżkę. W oparciu o taką istniejącą bazę można dokonywać optymalizacji procesów transportowych. Celem pracy jest wskazanie algorytmu, który na bazie wag przypisanych krawędziom grafu nieskierowanego (interpretowanymi jako odległości między dwoma węzłami) wyznacza macierz najkrótszych odległości między wszystkimi węzłami grafu oraz dodatkowo wyznacza ścieżki najkrótszych połączeń. Proces ten prowadzi m.in. do zastąpienia macierzy rzadkiej przez macierzą pełną. Równocześnie proces modelowania stanowi przejście pomiędzy zagadnieniami z zakresu teorii grafów a teorii przestrzeni metrycznych. Tak utworzona macierz pełna może stanowić podstawę do tworzenia bazy pełnych cykli Hamiltona lub innych zagadnień systemów transportowych. Wstępna analiza zaproponowanego tu algorytmu etapowego wskazuje, że jest on porównywalny ze znanymi algorytmami, a w niektórych przypadkach działa nawet szybciej. Kolejnym krokiem w następnej pracy będą czynności odwrotne do opisanych powyżej. Połączenie obu procedur pozwala na kontrolę procesu tworzenia minimal-nego grafu rozpinającego wszystkie najkrótsze ścieżki, ewentualnie tworzenie drzewa rozpinającego ścieżki, w których najkrótsze połączenia różnią się od najkrótszych dróg z zadaną z góry dokładnością. Wskazano możliwość wykorzystania wyników w optymalizacji transportu w przemyśle mleczarskim.

EN

A well-known issue in the professional literature is how to determine the shortest path in an undirected graph with non-negative weighted edges between two network nodes. A variation of this issue is to find the shortest paths between all the node pairs of a graph. Modern techniques allow one to store in the computer memory complete data containing information about the distance between any two network nodes and a sequence of nodes describing the shortest path. On the basis of such existing databases optimisation of transportation processes can be undertaken. This study aims at showing an algorithm that basing on the weights of an undirected graph edges (interpreted as the distance in some node pairs) determines the shortest distance matrix between all the nodes of the graph and additionally determines paths of shortest connections. This process leads to the replacement of a sparse matrix by a full matrix. The simultaneous modelling process forms transition between issues of the graph theory and the theory of metric spaces. The full matrix formed this way may lend itself to create the base of complete Hamilton cycles or other issues in transportation systems. An initial analysis of the stage-form algorithm proposed here indicates that it is comparable with known algorithms, and in some cases it works even faster. The next step in the subsequent study will consist in operations being reversed in comparison to the ones described above. Combining both procedures will allow for controlling the process of creating a minimal graph spanning all the shortest paths, and possibly creating a graph spanning paths, whose shortest connections differ from the shortest paths with pre-determined accuracy. The possibility of using the results for optimisation of transport in the dairy industry was shown.

2

Analiza skupień i redukcja wymiarowości w hierarchicznym modelu korpusowym języka

Wicijowski J., Ziółko B.

Studia Informatica

|

2010

|

Vol. 31, nr 2A

133-145

PL

Przedstawiono model semantyczny języka polskiego pochodzący z obróbki materiału językowego z polskiej Wikipedii. Model służy weryfikacji hipotez zdaniowych w systemie automatycznego rozpoznawania mowy. Przedstawiono metody filtracji i klasteryzacji dokumentów w celu przyśpieszenia obliczeń. Autorzy kładą nacisk na oddelegowaniu zadań do silnika bazy danych tam, gdzie jest to pożądane ze względu na szybkość.

EN

The article presents a semantic model of the polish language based on the polish Wikipedia texts. The model is a part of an automatic speech recognition system and verifies sentences hypotheses. Methods of filtering and clustering of the documents, which aim to accelerate the computations, are presented. The authors emphasize the delegation of the processing tasks to the database engine, where it is possible to gain the performance.

3

Quick offline sparse matrices

Wicijowski J.

Prace Instytutu Elektrotechniki

|

2010

|

Z. 247

209-222

EN

When dealing with large datasets, computer memory constraints are a common problem. With the volumes of data exceeding 1 GiB of size, storage of the whole datasets in RAM becomes infeasible. Since in most applications one deals with only a portion of dataset at a time, the rest may be kept offline on nonvolatile memory that provides larger capacities. The access to nonvolatile memory is typically a few orders of magnitude slower than of RAM, so an efficient method of storage should be proposed to keep the number of disc accesses count as small as possible. In the paper I describe the offline storage of sparse matrices that is built on top of Hierarchical Data Format (precisely, on the latest revision - HDF5) addressing the problem of matrix-vector multiplication.

PL

Ograniczenia pamięci komputera są powszechnym problemem przy obliczeniach przeprowadzanych na wielkich zbiorach danych. Przy danych roboczych przekraczających 1 GiB, składowanie całości w pamięci operacyjnej staje się utrudnione, a często nawet nieosiągalne. Ponieważ w większości aplikacji wykonuje się działania jedynie na fragmencie zbioru danych, reszta może być przechowywana w pamięci stałej, która zapewnia dużo większe pojemności. Dostęp do pamięci stałej jest zazwyczaj kilka rzędów wielkości wolniejszy niż do RAMu, zatem należy przedstawić metodę składowania ograniczającą do minimum ilość dostępów do dysku. W artykule opisuję format przechowywania macierzy rzadkich na dysku, zbudowanym na bazie formatu HDF5 (Hierarchical Data Format) pod kątem minimalizacji czasu mnożenia tej macierzy przez wektor.

4

Biblioteka podstaw klas macierzowych. Część II

Sokół R.

Prace Naukowe Politechniki Śląskiej. Elektryka

|

2009

|

z. 3

85-102

PL

Język C++ nie wspiera bezpośrednio realizacji operacji macierzowych na macierzach pełnych (implementacja każdej operacji wymaga zapisu bloku pętli); w ogóle też nie obsługuje technik rzadkiego zapisu macierzy. Skutkuje to niepotrzebnym powielaniem tych samych fragmentów kodu i koniecznością optymalizowania każdego z nich z osobna. Nieuniknione jest też pogorszenie czytelności kodu, spowodowane zastąpieniem czystego zapisu algebraicznego fragmentami kodu realizującego te operacje. Aby zlikwidować ten problem i przyspieszyć tworzenie oprogramowania optymalizującego rozpływ mocy w systemie elektroenergetycznym (intensywnie wykorzystującego operacje macierzowe), stworzono bibliotekę klas języka C++, standaryzującą zapis operacji algebraicznych na macierzach w tym języku. Biblioteka została stworzona w ramach projektu badawczego N511 001 32/0852.

EN

The C++ language does not directly support matrix algebra (implementing every operation requires open-coding a loop); it also does not support sparse matrix techniques. The end effect are code duplication and the necessity of optimising each independent code block separately. One cannot also avoid code readability degradation, caused by replacing a clean algebraic form with C++ code snippets. To solve this problem and improve code creation time (especially in case of the OPF-problem solving software, being developed as a part of a research project), a C++ class library was created. The library consists of classes implementing basic algebraic operations on simple and sparse matrices. The work was funded from the science budget as the research project No N511 001 32/0852.

5

Biblioteka podstaw klas macierzowych. Część I

Sokół R.

Prace Naukowe Politechniki Śląskiej. Elektryka

|

2009

|

z. 3

75-84

PL

Język C++ nie wspiera bezpośrednio realizacji operacji macierzowych na macierzach pełnych (implementacja każdej operacji wymaga zapisu bloku pętli) w ogóle też nie obsługuje technik rzadkiego zapisu macierzy. Skutkuje to niepotrzebnym powielaniem tych samych fragmentów kodu i koniecznością optymalizowania każdego z nich z osobna. Nieuniknione jest też pogorszenie czytelności kodu, spowodowane zastąpieniem czystego zapisu algebraicznego fragmentami kodu realizującego te operacje. Aby zlikwidować ten problem i przyspieszyć tworzenie oprogramowania optymalizującego rozpływ mocy w systemie elektroenergetycznym (intensywnie wykorzystującego operacje macierzowe), stworzono bibliotekę klas języka C++, standaryzującą zapis operacji algebraicznych na macierzach w tym języku. Biblioteka została stworzona w ramach projektu badawczego N511 001 32/0852.

EN

The C++ language does not directly support matrix algebra (implementing every operation requires open-coding a loop); it also does not support sparse matrix techniques. The end effect are code duplication and the necessity of optimising each independent code block separately. One also cannot avoid code readability degradation, caused by replacing a clean algebraic form with C++ code snippets. To solve this problem and improve code creation time (especially in case of the OPF-problem solving software, being developed as a part of a research project), a C++ class library was created. The library consists of classes implementing basic algebraic operations on simple and sparse matrices. The work was funded from the science budget as the research project No N511 001 32/0852.

6

Blokowa wielofrontalna metoda podstruktur do rozwiązywania dużych układów równań MES

Fialko S.

Czasopismo Techniczne. Nauki Podstawowe

|

2009

|

R. 106, z. 1-NP

175-188

PL

W niniejszym artykule przedstawiono metodę bezpośrednią rozwiązywania dużych układów równań liniowych algebraicznych z macierzami rzadkimi symetrycznymi, które powstają z zastosowaniem metody elementów skończonych do zadań mechaniki konstrukcji. W przeciwieństwie do znanych implementacji metody wielofrontalnej, podana metoda bazuje na agregacji podstruktur, na które została podzielona konstrukcja - na podstawie algorytmu uporządkowania, z jednoczesną eliminacją całkowicie zagregowanych równań. Tym sposobem faktoryzacja źródłowej macierzy rzadkiej o dużym rozmiarze doprowadzona zostaje do faktoryzacji sekwencji gęstych macierzy o stosunkowo niewielkim wymiarze. W artykule skoncentrowano się przede wszystkim na osiągnięciu wysokiej wydajności na wielordzeniowych komputerach PC.

EN

The direct method for solution of the large linear algebraic equation sets with sparse symmetrical matrices, which arise during application of the finite element method to the problems of structural mechanics, is presented. Proposed approach differs from well-known realizations of the multifrontal method because it is based on the assembling of substructures on which the whole structure is divided by means of application of reordering algorithm, with simultaneous elimination of the fully assembled equations. Thus the factorization of the source large sparse matrix is reduced to factorization of the series of dense matrices with respectively small dimension. The main attention in this article is paid to achievement of high performance on multi-core desktop computers.

7

A block sparse shared-memory multifrontal finite element solver for problems of structural mechanics

Fialko S. Y.

Computer Assisted Mechanics and Engineering Sciences

|

2009

|

Vol. 16, No. 2

117-131

EN

The presented method is used in finite-element analysis software developed for multicore and multiprocessor shared-memory computers, or it can be used on single-processor personal computers under the operating systems Windows 2000, Windows XP, or Windows Vista, widely popular in small or medium-sized design offices. The method has the following peculiar features: it works with any ordering; it uses an object-oriented approach on which a dynamic, highly memory-efficient algorithm is based; it performs a block factoring in the frontal matrix that entails a high-performance arithmetic on each processor and ensures a good scalability in shared-memory systems. Many years of experience with this solver in the SCAD software system have shown the method's high efficiency and reliability with various large-scale problems of structural mechanics (hundreds of thousands to millions of equations).