Solving Mixed Sparse-Dense Linear Least-Squares Problems by Preconditioned Iterative Methods
Solving Mixed Sparse-Dense Linear Least-Squares Problems by Preconditioned Iterative Methods
复制标题
DOI：
10.1137/16m1108339
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
J. Scott;M. Tuma
中科院分区：
文献类型：
--
作者：
J. Scott;M. Tuma
大型线性最小二乘问题的有效解是具有挑战性的，其中系统矩阵$A$包含具有非常不同密度的行。以前的工作集中在直接方法上，其中$A$有一些相对密集的行。这些行最初被忽略，使用稀疏直接求解器计算稀疏部分的因式分解，然后更新解以考虑忽略的密集行。在一些实际应用中，密集行的数量可能非常大，对于非常大的问题，使用直接求解器可能是不可行的。我们建议使用不完全因子分解预条件结合大小等于密集行数的密集矩阵的因子分解，在共轭梯度方法中单独处理被识别为密集的行。通过实际应用中的大规模问题的数值实验，说明了该方法的有效性。结果表明，我们可以有效地解决问题。
The efficient solution of large linear least-squares problems in which the system matrix $A$ contains rows with very different densities is challenging. Previous work has focused on direct methods for problems in which $A$ has a few relatively dense rows. These rows are initially ignored, a factorization of the sparse part is computed using a sparse direct solver, and then the solution is updated to take account of the omitted dense rows. In some practical applications the number of dense rows can be significant, and for very large problems, using a direct solver may not be feasible. We propose processing rows that are identified as dense separately within a conjugate gradient method using an incomplete factorization preconditioner combined with the factorization of a dense matrix of size equal to the number of dense rows. Numerical experiments on large-scale problems from real applications are used to illustrate the effectiveness of our approach. The results demonstrate that we can efficiently solve prob...