BazTech - Yadda

1

Kaczmarz algorithm revisited

Sznajder R.

Czasopismo Techniczne. Nauki Podstawowe

|

2015

|

Y. 112, iss. 2-NP

247--254

EN

In 1937, Stefan Kaczmarz proposed a simple method, called the Kaczmarz algorithm, to solve iteratively systems of linear equations Ax = b in Euclidean spaces. This procedure employs cyclic orthogonal projections onto the hyperplanes associated with such a system. In the case of a nonsingular matrix A, Kaczmarz showed that his method guarantees convergence to the solution of Ax = b. The Kaczmarz algorithm was rediscovered in 1948 and became an important tool in medical engineering. We briefly discuss generalizations of this method and its ramifications, including applications in computer tomography, image processing and contemporary harmonic analysis.

PL

W 1937 roku Stefan Kaczmarz zaproponował prostą metodę [KA], zwaną obecnie algorytmem Kaczmarza, za pomocą której można rozwiązywać iteracyjnie układy równań liniowych Ax = b w przestrzeniach euklidesowych. Metoda ta używa cyklicznego ciągu rzutów ortogonalnych na hiperpłaszczyzny związane z tym układem. W przypadku macierzy odwracalnej A Kaczmarz pokazał, że jego metoda gwarantuje zbieżność do rozwiązania układu równań Ax = b. Metoda ta została ponownie odkryta w 1948 roku i stała się ważnym narzędziem w inżynierii medycznej. Omawiamy tutaj pokrótce uogólnienia tej metody i ich zastosowania w tomografii komputerowej, przetwarzaniu obrazów i we współczesnej analizie harmonicznej.

2

Zagadnienie rozwiązywania wybranych zadań algebry liniowej za pomocą sieci neuronowych

Mrówczyńska M.

Prace Naukowe Instytutu Górnictwa Politechniki Wrocławskiej. Konferencje

|

2009

|

Vol. 129, nr 54

97-102

PL

W pracy przedstawiono wybrane zastosowania praktyczne i wyniki symulacji komputerowych z zakresu numerycznej algebry liniowej, realizowanej za pomocą sieci neuronowych. Mając na względzie aspekty zastosowań, uznano za celowe nadać priorytet opisowi zagadnienia wyrównania nadokreślonych układów liniowych w normie l2 oraz w normie l1. Do standardowych operacji numerycznych zaliczono również algorytmy obliczania inwersji macierzy kwadratowych oraz wyznaczania ich wartości własnych i wektorów własnych.

EN

The paper presents selected practical uses and results of computer simulations from the field of numerical linear algebra realised by means of neural networks. Bearing in mind practical aspects it was decided that priority should be given to description of the problem of equalizing overdetermined linear systems in the norm l2 and in the norm l1. Algorithms for calculating inversion of square matrices and specifying their own values and their own vectors were also included in standard numerical operations.

3

Rozwiązywanie numeryczne układów równań liniowych metodą kwadratu gradientów sprzężonych

Szczerbiński Z., Steinborn K.

Metody Informatyki Stosowanej

|

2009

|

nr 4 (21)

113-126

PL

W niniejszym artykule opisano metode˛ kwadratu gradientów sprzężonych rozwiązywania układów równań liniowych oraz jej programową implementację, wraz z przeprowadzonymi za jej pomoca˛ testami efektywności samej metody (skupiono się tu na dokładności wyników) oraz testami przyspieszenia działania w systemach wieloprocesorowych. Testy efektywności metody dowiodły, że metoda kwadratu gradientów sprzężonych bardzo szybko dąży do rozwiązania. Odbywa się˛ to jednak kosztem większej liczby błędów zaokrągleń , a w przypadku wersji obliczania residuum na nowo—kosztem większych oscylacji i mniejszej stabilności.W artykule wykazano, że błędy zaokrągleń , jakie pojawiają˛ się˛ w trakcie wyznaczania rozwiązania, można minimalizować stosując restartowanie metody. Przyspieszanie obliczeń, dzięki zastosowaniu systemów wieloprocesorowych, jest obecnie powszechnym rozwiązaniem, wykorzystywanym do rozwiązywania dużych układów równań liniowych.W artykule potwierdzono korzyści wynikające z ich zastosowania; zaznaczono jednak przy tym, że byłyby one (przypuszczalnie) znacznie wyraźniejsze dla większych, niż analizowane, układów równań i dla realizacji obliczeń z wykorzystaniem większych liczb procesorów. Można obecnie przewidywać dynamiczny rozwój takich badań w związku z obserwowanym od kilku lat rozwojem architektur komputerowych w kierunku zwiększania liczby procesorów w systemie (również: rdzeni w procesorze), nie zaś jedynie zwiększania częstotliwości taktów zegara, co miało przede wszystkim miejsce dotychczas (i czego kres wydaje się być bliski z powodu fizycznych ograniczeń półprzewodników, np. problemu odprowadzania ciepła, jak i ograniczenia naturalnego jakim jest skończona prędkość światła). W tym kierunku zmierzaja˛ również plany autorów niniejszego artykułu na przyszłość. Przewiduja˛ one badanie efektywności obliczeń równoległych, realizujących opisaną w artykule metodę, dla układów równań o (nawet) kilka rzędów większych rozmiarach, na platformach sprzętowych zawierających znacznie większe liczby procesorów (wyspecjalizowane klastry obliczeniowe, superkomputery).

EN

The article is concerned with issues arising in numerical solution of sparse systems of linear equations. Upon introduction to the subject of projection methods for solving such systems, the method of conjugate gradients squared is described in detail, along with its implementation both as a sequential and parallel program. Detailed analyses of both the numerical and timing results, produced by these programs while solving example linear systems, are performed. It is also described how to modify the computation process in order to obtain more accurate results.

4

Rozwiązywanie układów równań liniowych niejednorodnych

Ufnalski W.

LAB Laboratoria, Aparatura, Badania

|

2005

|

R. 10, nr 3

22-27

5

Parallel computing applied to solving large Markov chains. A feasibility study.

Szczerbiński Z.

Studia Informatica

|

2003

|

Vol. 24, nr 4

7-28

EN

The article is concerned with parallel computation issues arising in numerical solution of systems of linear eąuations which describe stationary pro-babilitifis of stat.es in largc Markov chairis. Upon introduction to the .subject of Markov chains and their solution, several adeąuate solution methods arę surreyed, froni the cla.ssical through projection to decompositional ones. Each algoriUiin is accoinpaniocl by a study of its suitability to parallel computing (rnulti- and vector procfissing). Additional opinions on aspects of the potential for parallelization in the discussed methods arę contained in the conclusion.

PL

Artykuł jest poświęcony zagadnieniom obliczeń równoległych, występującym w trakcie numerycznego rozwiązywania układów równań liniowych, opisujących stacjonarne prawdopodobieństwa stanów w dużych łańcuchach Markowa. Po wprowadzeniu do tematyki łańcuchów Markowa, dokonano przeglądu wybranych metod rozwiązywania, począwszy od klasycznych, poprzez projekcyjne, do metod dekompozycyjnych. Dla każdego algorytmu została dokonana analiza, na ile nadaje się on do wykonania w trybie równoległym (wieloprocesorowyrn lub wektorowym). Dodatkowe uwagi dotyczące możliwości zrównoleglania dla omawianych metod zawarto w części końcowej.