A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows
A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows
复制标题
用于预处理具有某些密集行的稀疏线性最小二乘问题的 Schur 补法
DOI：
10.1007/s11075-018-0478-2
复制
发表时间：
2018
影响因子：
2.1
通讯作者：
M. Tuma
中科院分区：
文献类型：
--
作者：
J. Scott;M. Tuma
如果系统矩阵A具有一个或多个近似稠密行，则直接求解大规模线性最小二乘问题的稀疏矩阵技术的有效性受到严重限制。在本文中，我们划分A的行为稀疏行和密集行（As和Ad），并应用舒尔补的方法。一个潜在的困难是，约化的正规矩阵AsTAs通常是秩亏的，即使A是满秩的。为了克服这一点，我们建议明确删除空列的作为，然后采用正则化参数，并使用由此产生的Cholesky因素作为预条件的迭代求解器应用到对称的不定减少增广系统。我们考虑移位约化正规矩阵的完全分解和不完全Cholesky分解。数值实验进行了一系列的大型最小二乘问题所产生的实际应用。这些证明了所提出的方法的有效性时，结合稀疏并行直接求解器或一个强大的不完全Cholesky分解算法。
The effectiveness of sparse matrix techniques for directly solving large-scale linear least-squares problems is severely limited if the system matrix A has one or more nearly dense rows. In this paper, we partition the rows of A into sparse rows and dense rows (As and Ad) and apply the Schur complement approach. A potential difficulty is that the reduced normal matrix AsTAs is often rank-deficient, even if A is of full rank. To overcome this, we propose explicitly removing null columns of As and then employing a regularization parameter and using the resulting Cholesky factors as a preconditioner for an iterative solver applied to the symmetric indefinite reduced augmented system. We consider complete factorizations as well as incomplete Cholesky factorizations of the shifted reduced normal matrix. Numerical experiments are performed on a range of large least-squares problems arising from practical applications. These demonstrate the effectiveness of the proposed approach when combined with either a sparse parallel direct solver or a robust incomplete Cholesky factorization algorithm.
DOI：
10.1145/1499096.1499098
发表时间：
2009-03
期刊：
ACM Trans. Math. Softw.
影响因子：
--
作者：
J. Reid;J. Scott
通讯作者：
J. Reid;J. Scott