A Class of Incomplete Orthogonal Factorization Methods. I: Methods and Theories
A Class of Incomplete Orthogonal Factorization Methods. I: Methods and Theories
复制标题
DOI：
10.1023/a:1021913700691
复制
发表时间：
1999
影响因子：
1.5
通讯作者：
Z. Bai;I. Duff;A. Wathen
中科院分区：
文献类型：
--
作者：
Z. Bai;I. Duff;A. Wathen
针对大型稀疏非对称矩阵，提出了一类基于给定旋转的不完全正交分解方法。这些方法包括：不完全给定正交化（IGO-method）及其推广（GIGO-method），它按位置从不完全正交因子和上三角因子中删除条目；阈值不完全给定正交化（TIGO(τ)-方法），该方法根据条目的大小动态丢弃条目；以及它的推广（GTIGO(τ,p)-方法），它根据它们的大小和位置动态地下降条目。理论分析表明，对于一般非奇异矩阵，这些方法可以产生非奇异稀疏不完全上三角因子和完全正交因子或稀疏非奇异不完全正交因子。因此，这些方法可以潜在地为求解大型线性方程稀疏系统的Krylov子空间方法生成有效的前置条件。此外，上三角因子是最小二乘问题正规方程矩阵的不完全Cholesky分解前条件。
We present a class of incomplete orthogonal factorization methods based on Givens rotations for large sparse unsymmetric matrices. These methods include: Incomplete Givens Orthogonalization (IGO-method) and its generalisation (GIGO-method), which drop entries from the incomplete orthogonal and upper triangular factors by position; Threshold Incomplete Givens Orthogonalization (TIGO(τ)-method), which drops entries dynamically by their magnitudes; and its generalisation (GTIGO(τ,p)-method), which drops entries dynamically by both their magnitudes and positions. Theoretical analyses show that these methods can produce a nonsingular sparse incomplete upper triangular factor and either a complete orthogonal factor or a sparse nonsingular incomplete orthogonal factor for a general nonsingular matrix. Therefore, these methods can potentially generate efficient preconditioners for Krylov subspace methods for solving large sparse systems of linear equations. Moreover, the upper triangular factor is an incomplete Cholesky factorization preconditioner for the normal equations matrix from least-squares problems.