CIMGS: An incomplete orthogonal factorization preconditioner. A new preconditioner for symmetric positive definite systems is proposed, analyzed, and tested. The preconditioner, compressed incomplete modified Gram--Schmidt (CIMGS), is based on an incomplete orthogonal factorization. CIMGS is robust both theoretically and empirically, existing (in exact arithmetic) for any full rank matrix. Numerically it is more robust than an incomplete Cholesky factorization preconditioner (IC) and a complete Cholesky factorization of the normal equations. Theoretical results show that the CIMGS factorization has better backward error properties than complete Cholesky factorization. For symmetric positive definite M-matrices, CIMGS induces a regular splitting and better estimates the complete Cholesky factor as the set of dropped positions gets smaller. CIMGS lies between complete Cholesky factorization and incomplete Cholesky factorization in its approximation properties. These theoretical properties usually hold numerically, even when the matrix is not an M-matrix. When the drop set satisfies a mild and easily verified (or enforced) property, the upper triangular factor CIMGS generates is the same as that generated by incomplete Cholesky factorization. This allows the existence of the IC factorization to be guaranteed, based solely on the target sparsity pattern.

References in zbMATH (referenced in 11 articles )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Gould, Nicholas; Scott, Jennifer: The state-of-the-art of preconditioners for sparse linear least-squares problems (2017)
  2. Scott, Jennifer; Tuma, Miroslav: Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations (2016)
  3. Huang, Yu-Mei: On (m)-step Hermitian and skew-Hermitian splitting preconditioning methods (2015)
  4. Aihara, Kensuke; Abe, Kuniyoshi; Ishiwata, Emiko: A quasi-minimal residual variant of IDRstab using the residual smoothing technique (2014)
  5. Bai, Zhong-Zhi; Duff, Iain S.; Yin, Jun-Feng: Numerical study on incomplete orthogonal factorization preconditioners (2009)
  6. Bai, Zhong-Zhi; Yin, Jun-Feng: Modified incomplete orthogonal factorization methods using Givens rotations (2009)
  7. Papadopoulos, A. T.; Duff, I. S.; Wathen, A. J.: A class of incomplete orthogonal factorization methods. II: Implemetation and results (2005)
  8. Yang, Laurence Tianruo: Accuracy of preconditioned CG-type methods for least squares problems. (2003)
  9. Zhang, Jun; Xiao, Tong: A multilevel block incomplete Cholesky preconditioner for solving normal equations in linear least squares problems (2003)
  10. Zhang, Shao-Liang; Nakata, Kazuhide; Kojima, Masakazu: Incomplete orthogonalization preconditioners for solving large and dense linear systems which arise from semidefinite programming (2002)
  11. Wang, Xiaoge; Gallivan, Kyle A.; Bramley, Randall: CIMGS: An incomplete orthogonal factorization preconditioner (1997)