CIMGS: An Incomplete Orthogonal FactorizationPreconditioner
CIMGS: An Incomplete Orthogonal FactorizationPreconditioner
复制标题
DOI：
10.1137/s1064827594268270
复制
发表时间：
1997-03
期刊：
影响因子：
--
通讯作者：
Xiaoge Wang;K. Gallivan;R. Bramley
中科院分区：
文献类型：
--
作者：
Xiaoge Wang;K. Gallivan;R. Bramley
提出了对称正定系统的一种新的预条件，并对其进行了分析和检验。该预条件是基于不完全正交分解的压缩不完全修正Gram—Schmidt （CIMGS）预条件。CIMGS在理论上和经验上都是鲁棒的，对任何满秩矩阵都存在（精确的算法）。在数值上，它比不完全Cholesky分解预条件（IC）和正规方程的完全Cholesky分解更具鲁棒性。理论结果表明，CIMGS分解比完全Cholesky分解具有更好的后向误差特性。对于对称正定m -矩阵，CIMGS诱导了一个规则的分裂，并且随着丢失位置集的减小，可以更好地估计完全Cholesky因子。CIMGS的近似性质介于完全Cholesky分解和不完全Cholesky分解之间。这些理论性质通常在数值上成立，即使矩阵不是m矩阵。当跌落集满足温和且易于验证（或强制）的性质时，CIMGS生成的上三角因子与不完全Cholesky分解生成的上三角因子相同。这样就可以保证IC分解的存在性，仅基于目标稀疏性模式。
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.