Premium
On the purely algebraic data‐sparse approximation of the inverse and the triangular factors of sparse matrices
Author(s) -
Bebendorf M.,
Fischer T.
Publication year - 2011
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.714
Subject(s) - mathematics , sparse matrix , bounded function , inverse , discretization , sparse approximation , matrix (chemical analysis) , logarithm , condition number , algebraic number , discrete mathematics , algebra over a field , algorithm , pure mathematics , mathematical analysis , eigenvalues and eigenvectors , geometry , gaussian , physics , materials science , quantum mechanics , composite material
The approximation of the inverse and the factors of the LU decomposition of general sparse matrices by hierarchical matrices is investigated. In this first approach, we present and motivate a new matrix partitioning algorithm which is based on the matrix graph by proving logarithmic‐linear complexity of the approximant in the case of bounded condition numbers. In contrast to the usual partitioning, the new algorithm allows to treat general grids if the origin of the sparse matrix is the finite element discretization of differential operators. Numerical examples indicate that the restriction to bounded condition numbers has only technical reasons. Copyright © 2010 John Wiley & Sons, Ltd.