A Supernodal Approach to Sparse Partial Pivoting

Autor:	Stanley C. Eisenstat, James Demmel, John R. Gilbert, Joseph W. H. Liu, Xiaoye S. Li
Rok vydání:	1999
Předmět:	Speedup Memory hierarchy Computation Linear system MathematicsofComputing_NUMERICALANALYSIS Incomplete LU factorization LU decomposition law.invention law Algorithm Analysis Pivot element Sparse matrix Mathematics
Zdroj:	SIAM Journal on Matrix Analysis and Applications. 20:720-755
ISSN:	1095-7162 0895-4798
DOI:	10.1137/s0895479895291765
Popis:	We investigate several ways to improve the performance of sparse LU factorization with partial pivoting, as used to solve unsymmetric linear systems. We introduce the notion of unsymmetric supernodes to perform most of the numerical computation in dense matrix kernels. We introduce unsymmetric supernode-panel updates and two-dimensional data partitioning to better exploit the memory hierarchy. We use Gilbert and Peierls's depth-first search with Eisenstat and Liu's symmetric structural reductions to speed up symbolic factorization. We have developed a sparse LU code using all these ideas. We present experiments demonstrating that it is significantly faster than earlier partial pivoting codes. We also compare its performance with UMFPACK, which uses a multifrontal approach; our code is very competitive in time and storage requirements, especially for large problems.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::7cb70695e0c224ecae6d7b37d426c302 https://doi.org/10.1137/s0895479895291765 Zobrazit plný text záznamu Plný text ve formátu PDF