A robust inner-outer hierarchically semi-separable preconditioner

作者：Xia J^*

来源：Numerical Linear Algebra with Applications, 2012, 19(6): 992-1016.

DOI：10.1002/nla.1850

• robust preconditioner
• hierarchically semi-separable (HSS) matrix
• inner-outer HSS algorithm
• ULV factorization

In this paper, an innerouter 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 innerouter 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 innerouter preconditioners using direct rank structured factorizations (other than iterative methods).

• 出版日期2012-12