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

• Autorzy: Szczerbiński Z. , Steinborn K.
• Języki publikacji: PL

Abstrakty

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.

Słowa kluczowe

PL

układy równań liniowych; metody projekcyjne; systemy wieloprocesorowe

EN

systems of linear equations; projection methods; parallel computing; multiprocessor systems

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2009
• Tom: nr 4 (21)
• Strony: 113--126
• Opis fizyczny: Bibliogr. 17 poz., rys., tab.

Twórcy

autor

Szczerbiński Z.

autor

Steinborn K.

• Instytut Informatyki Stosowanej, Państwowa Wyższa Szkoła Zawodowa w Elblągu

Bibliografia

• [1] Bridson R. Notes for CS542G (Conjugate gradient for linear systems) [online]. http://www.cs. ubc.ca/$\sim$rbridson/courses/542g-fall-2007/nov22-cs542g-notes.pdf [dostęp: 2009]
• [2] Dagum L., Menon R. OpenMP: an industry-standard API for shared memory programming. Computational Science and Engineering, Vol. 5, 1998
• [3] Fletcher R. Conjugate gradient methods for indefinite systems. Springer Verlag, 1976
• [4] Fortuna Z., Macukow B., Wa˛sowski J. Metody numeryczne, wyd. czwarte. Wydawnictwa Naukowo-Techniczne, 1998
• [5] Hestenes M. R., Stiefel E. Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, Vol. 49, 1952, s. 409-436
• [6] Karush W. An iterative method for finding characteristic vectors of a symmetric matrix. Pacific Journal of Mathematics, 1951, s. 233-248
• [7] Knottenbelt W. J. Parallel performance analysis of large Markov chains. Ph. D. Thesis, University of London, 1999
• [8] Kuck D. J. The structure of computers and computations. Wiley, 1978
• [9] Lanczos C. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. Journal of Research of the National Bureau of Standards, 1950, s. 255-282
• [10] Padua D. A., Kuck D. J., Lawrie D. H. High-speed multiprocessors and compilation techniques. IEEE Transactions on Computers, No. 9/1980, 1980
• [11] Paige C. C., Saunders M. A. Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis, Vol. 12, 1975, s. 617-624
• [12] Saad Y. Iterative methods for sparse linear systems, wyd. drugie [online]. http://www-users.cs.umn.edu/∼saad/books.html [dost˛ep: 2009]
• [13] Shewchuk J. R. An introduction to the conjugate gradient method without the agonizing pain [online]. http://www.cs.cmu.edu/∼quake-papers/painless-conjugate-gradient.pdf [dostęp: 2009]
• [14] Sonneveld P. CGS, a fast Lanczos-type solver for nonsymmetric systems. SIAMJournal on Scientific and Statistical Computing, Vol. 10, 1989, s. 36-52
• [15] Stewart W. J. Introduction to the numerical solution of Markov chains. Princeton University Press, 1994
• [16] Szczerbi´nski Z. Parallel computing applied to solving large Markov chains. A feasibility study. Studia Informatica, No 4/2003, 2003, s. 7-28
• [17] Szczerbi'nski Z. AMarkov chain model of optical packet formation: solution process acceleration with parallel computing. Proceedings of the Euro-NGI Workshop on New Trends in Modelling, Quantitative Methods and Measurements, 2004, s. 203-211