Supernodal algorithm versus object oriented technique in sparse linear equations solver

• Autorzy: Stabrowski M.

Warianty tytułu

PL

Porównanie algorytmu superwęzłowego z obiektową techniką rozwiązywania rzadkich układów równań

• Konferencja: Międzynarodowe Warsztaty "Computational Problems of Electrical Engineering"
• Języki publikacji: EN

Abstrakty

EN

Supernodal technique, used in the field of sparse linear equation solvers, introduces dense kernel for speeding-up the computations. SuperLU solver is the most sophisticated and efficient example of this technique. The research reported here shows that supernodal solver is really fast, but this spectacular speed is obtained through abandoning of numerical stability. It has been shown that SuperLU solver fails in whole class of practical real-world problems. An attempt to characterize and diagnose this problems in terms of matrix parameters has been madę. Pointer solver, being stable numerically and fairly fast alternative for supernodal solver is presented quite comprehensively.

PL

Metoda superwęzłów stosowana przy rozwiązywaniu rzadkich układów równań algebraicznych polega na specjalnym traktowaniu przydiagonalnych fragmentów macierzy rzadkich. Fragmenty te traktowane są jako submacierze pełne, przez co uzyskuje się przyspieszenie obliczeń kosztem, jak podają niektórzy badacze, utraty stabilności numerycznej. Praca jest próbą analizy tego problemu w kategoriach parametrów macierzy rozwiązywanego układu równań. Przedstawia stabilną numerycznie i dość szybką alternatywę - solver ,,wskaźnikowy" (pointer solver).

Słowa kluczowe

EN

sparse linear equations; solvers; numerical stability; supernodal technique

PL

równanie algebraiczne; rzadkie układy; rozwiązywanie; stabilność numeryczna; metoda superwęzłów

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2005
• Tom: R. 81, nr 2
• Strony: 44--47
• Opis fizyczny: Bibliogr. 8 poz., rys., tab.

Twórcy

autor

Stabrowski M.

• Institute of Computer Science, Lublin University of Technology, Lublin, Poland

Bibliografia

• [1] J.W. Demmel, S.C. Eisenstat, J.R. Gilbert, X.S. Li, J.W.H. Liu, ―A supernodal approach to sparse partial pivoting‖, SIAM J. Matrix Anal. Appl., vol. 20, No. 3, pp. 720-755.
• [2] K.S. Kundert, „Sparse matrix techniques‖ in „Circuit Analysis, Simulation and Design‖, Albert Ruehli (editor), North Holland, 1986.
• [3] B.H. Mayoh, „A graph technique for inverting certain matrices, Mathematics of Computation, vol. 19 (1965), pp. 644-646.
• [4] S. Pandit, S. A. Soman, S. A. Khaparde, „Design of generic direct sparse linear system solver in C++ for power system analysis‖, IEEE Transactions on Power Sysytems, vol. 16 (2001), iss. 4, pp. 647-652.
• [5] J.G. Siek, „A Modern Framework for Portable High Performance Numerical Linear Algebra‖, Master Sc. Thesis, Notre Dame University, Indiana 1999.
• [6] M.M. Stabrowski, „Software and hardware optimization of unsymmetrical sparse linear equation solvers‖, Proceedings of XII ISTET Conference , Warsaw 2003, vol. II, pp.159-162.
• [7] T.L. Veldhuizen, M.E. Jernigan, „Will C++ be faster than Fortran‖, in ―Scientific Computing in Object-Oriented Parallel Environments‖. ISCOPE, December 1997.
• [8] S.E. Zitney, J.U. Mallya, T.A. Davis, M.A. Stadherr, „Multifrontal vs frontal techniques for chemical proces simulation on supercomputers‖, Computers in Chemical Engineering, vol. 20 (1996), pp. 614-646.