An unsymmetrized multifrontal LU factorization

Amestoy, Patrick R. ; Puglisi, Chiara

Lawrence Berkeley National Laboratory

关键词: Sparse Linear Equations Direct Methods;    Computer Calculations Sparse Linear Equations Direct Methods;    99 General And Miscellaneous//Mathematics, Computing, And Information Science;    Factorization;    Algorithms;   

DOI  :  10.2172/776628
RP-ID  :  LBNL--46474
RP-ID  :  AC03-76SF00098
RP-ID  :  776628

美国|英语

来源: UNT Digital Library

【 摘 要 】

A well-known approach to compute the LU factorization of a general unsymmetric matrix bf A is to build the elimination tree associated with the pattern of the symmetric matrix A + A{sup T} and use it as a computational graph to drive the numerical factorization. This approach, although very efficient on a large range of unsymmetric matrices, does not capture the unsymmetric structure of the matrices. We introduce a new algorithm which detects and exploits the structural unsymmetry of the submatrices involved during the process of the elimination tree. We show that with the new algorithm significant gains both in memory and in time to perform the factorization can be obtained.