Premium
A robust inner–outer hierarchically semi‐separable preconditioner
Author(s) -
Xia J.
Publication year - 2012
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.1850
Subject(s) - preconditioner , cholesky decomposition , mathematics , robustness (evolution) , diagonal , triangular matrix , separable space , incomplete cholesky factorization , iterative method , incomplete lu factorization , algorithm , diagonal matrix , matrix (chemical analysis) , mathematical optimization , matrix decomposition , mathematical analysis , pure mathematics , eigenvalues and eigenvectors , geometry , invertible matrix , biochemistry , physics , chemistry , quantum mechanics , gene , composite material , materials science
SUMMARY In this paper, an inner–outer preconditioner for symmetric positive definite matrices based on hierarchically semi‐separable (HSS) matrix representation is presented. A sequence of new HSS algorithms are developed, including some ULV‐type HSS methods and triangular HSS methods. During the construction of this preconditioner, off‐diagonal blocks are compressed in parallel, and an approximate HSS form is used as the outer HSS representation. In the meantime, the internal dense diagonal blocks are approximately factorized into HSS Cholesky factors. Such inner factorizations are guaranteed to exist for any approximation accuracy. The inner–outer preconditioner combines the advantages of both direct HSS and triangular HSS methods, and are both scalable and robust. Systematic complexity analysis and discussions of the errors are presented. Various tests on some practical numerical problems are used to demonstrate the efficiency and robustness. In particular, the effectiveness of the preconditioner in iterative solutions has been shown for some ill‐conditioned problems. This work also gives a practical way of developing inner–outer preconditioners using direct rank structured factorizations (other than iterative methods). Copyright © 2012 John Wiley & Sons, Ltd.