Preconditioning of Linear Least Squares by Robust Incomplete Factorization for Implicitly Held Normal Equations
Preconditioning of Linear Least Squares by Robust Incomplete Factorization for Implicitly Held Normal Equations
复制标题
隐式保持正规方程的鲁棒不完全因式分解线性最小二乘法的预处理
DOI：
10.1137/16m105890x
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Tuma
中科院分区：
文献类型：
--
作者：
J. Scott;M. Tuma
一个大型的稀疏线性最小二乘问题对应的标准方程的有效解是极具挑战性的。鲁棒不完全因子分解（RIF）预条件代表了一种方法，它具有计算正规方程矩阵的不完全l ^T因子分解而不必形成正规矩阵本身的重要特征。Benzi和Tůma的正确实现已在许多研究中使用，但经验表明，在某些情况下，它的计算速度可能很慢，并且其内存需求是未知的。这里提出了一种新的左看变体，它采用符号预处理步骤来取代通过常规矩阵的条目进行潜在的昂贵搜索。这涉及到一个随计算进行而计算的有向无环图（DAG）。提出了一种廉价而有效的剪枝算法来限制DAG中的边数。在实际应用中出现的问题被用来比较……
The efficient solution of the normal equations corresponding to a large sparse linear least squares problem can be extremely challenging. Robust incomplete factorization (RIF) preconditioners represent one approach that has the important feature of computing an incomplete $LL^T$ factorization of the normal equations matrix without having to form the normal matrix itself. The right-looking implementation of Benzi and Tůma has been used in a number of studies but experience has shown that in some cases it can be computationally slow and its memory requirements are not known a priori. Here a new left-looking variant is presented that employs a symbolic preprocessing step to replace the potentially expensive searching through entries of the normal matrix. This involves a directed acyclic graph (DAG) that is computed as the computation proceeds. An inexpensive but effective pruning algorithm is proposed to limit the number of edges in the DAG. Problems arising from practical applications are used to compare th...
通过识别基矩阵来预处理线性最小二乘问题
影响因子：
3.1
作者：
Arioli M
通讯作者：
Arioli M