Numerical eciency of the conjugate gradient algorithm - sequential implementation

• Autorzy: Gościk J. , Gościk J.

Warianty tytułu

PL

Numeryczna algorytmu gradientów sprzężonych - implementacja sekwencyjna

• Języki publikacji: PL

Abstrakty

PL

Przedstawiono wyniki realizacji drugiego etapu projektu mającego na celu opracowanie i wdrożenie algorytmów rozwiązywania wielkich układów równań liniowych generowanych w procesie aproksymacji eliptycznych równań różniczkowych o pochodnych cząstkowych (PDE) metodą różnic skończonych. W szczególności skoncentrowano się na implementacji wersji sekwencyjnej najbardziej reprezentatywnej metody iteracyjnej zdefiniowanej w przestrzeni Kryłowa (metody gradientów sprzężonych). W pierwszej części pracy opisano szczegóły implementacji schematu iteracyjnego rozwiązywania dyskretnej postaci równania Poissona, uogólniając sformułowanie również do zagadnień przestrzennie trójwymiarowych.Wdrugiej części pracy skoncentrowano się przedstawieniu czasu wykorzystania procesora podczas wykonywania najbardziej czasochłonnych operacji algebry liniowej na macierzach rzadkich. Oceny poprawności formalnej jak też i wydajności obliczeniowej stworzonego kodu sekwencyjnego dokonano poprzez rozwiązanie trzech zagadnień testowych z wykorzystaniem dwóch komputerów o różnej konfiguracji sprzętowej.

EN

In the paper we report on a second stage of our eorts towards a library design for the solution of very large set of linear equations arising from the finite dierence approximation of elliptic partial dierential equations (PDE). Particularly a family of Krylov subspace iterative based methods (in the paper exemplified by the archetypical Krylov space method - Conjugate Gradient method) are considered. The first part of the paper describes in details implementation of iterative algorithms for solution of the Poisson equation which formulation has been extended to the three-dimensional. The second part of the paper is focused on the performance measurement of the most time-consuming computational kernels of iterative techniques executing basic linear algebra operations with sparse matrices. The validation of prepared codes as well as their computational eciency have been examined by solution a set of test problems on two dierent computers.

Słowa kluczowe

PL

metody iteracyjne; metoda różnic skończonych; równanie Poissona; wydajność kodu sekwencyjnego

EN

iterative solvers; finite diference method; Poisson equation; performance of sequential code

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Zeszyty Naukowe Politechniki Białostockiej. Informatyka
• Rocznik: 2009
• Tom: Z. 4
• Strony: 47--62
• Opis fizyczny: Bibliogr. 19 poz., Tab.

Twórcy

autor

Gościk J.

autor

Gościk J.

Bibliografia

• [1] Dongarra J., Luszczek P., Petitet A.: The LINPACK Benchmark: Past, Present, and Future. Concurrency and Computation: Practice and Experience, Vol. 15, No. 9, 2003, pp. 803-820.
• [2] Gościk J., Gościk J.: Numerical effciency of iterative solvers for the Poisson equation using computer cluster. Zeszyty Naukowe Politechniki Białostockiej, Seria: Informatyka, Vol. 3, 2008.
• [3] Saad Y.: Iterative Methods for Sparse Linear Systems. Second Edition, SIAM, Philadelphia, Pa, 2003.
• [4] Lawson C.L, Hanson R.J., Kincaid D.R., Krogh F.T.: Basic linear algebra subprograms for Fortran usage. ACM Transactions on Mathematical Software, Vol. 5, No. 3, September 1979, pp. 308-323.
• [5] Arbenz P., Peterson W.: Introduction to Parallel Computing - A Practical Guide with examples in C. Oxford University Press, 2004, Series: Oxford Texts in Applied and Engineering Mathematics No. 9, Oxford 2004.