论文标题
以$ε$准确的奇异系统的迭代精致近似概括性逆向奇异系统
Approximate Generalized Inverses with Iterative Refinement for $ε$-Accurate Preconditioning of Singular Systems
论文作者
论文摘要
我们引入了一类新的预处理，以使柔性转基因剂找到最小二乘解决方案，并可能是大规模稀疏，不对称，奇异且潜在不一致的系统的伪内溶液。我们基于一个新的观察结果开发预处理，该观察值将概括（即$ \ boldsymbol {a}^{g} \ in \ {\ boldsymbol {\ boldsymbol {g} \ boldsymbol {a} a} \ boldsymbol {a} \ boldsymbol {g}预处理的Krylov子空间以单步收敛。然后，我们使用混合不完整分解（HIF）有效地计算了近似概括的逆（AGI），该分解将多级不完整的LU与级别浏览QR结合在其最终的Schur补体中。我们定义了$ε$ - 准确性和AGI稳定性的标准，以确保对一致系统的预处理循环的收敛。对于不一致的系统，我们会以迭代性改进为HIFIR加固HIF，从而可以准确地计算空空间向量。通过结合两种技术，我们获得了一个称为Pipit的新求解器，用于获得具有低维无空间空间的系统的伪变性溶液。我们证明了HIF和HIFIR的鲁棒性，并表明它们通过多达一百万个未知数的系统的数量级来提高先前的最新水平状态的准确性和效率。
We introduce a new class of preconditioners to enable flexible GMRES to find a least-squares solution, and potentially the pseudoinverse solution, of large-scale sparse, asymmetric, singular, and potentially inconsistent systems. We develop the preconditioners based on a new observation that generalized inverses (i.e., $\boldsymbol{A}^{g}\in\{\boldsymbol{G}\mid\boldsymbol{A}\boldsymbol{G}\boldsymbol{A}=\boldsymbol{A}\}$) enable the preconditioned Krylov subspaces to converge in a single step. We then compute an approximate generalized inverse (AGI) efficiently using a hybrid incomplete factorization (HIF), which combines multilevel incomplete LU with rank-revealing QR on its final Schur complement. We define the criteria of $ε$-accuracy and stability of AGI to guarantee the convergence of preconditioned GMRES for consistent systems. For inconsistent systems, we fortify HIF with iterative refinement to obtain HIFIR, which allows accurate computations of the null-space vectors. By combining the two techniques, we then obtain a new solver, called PIPIT, for obtaining the pseudoinverse solutions for systems with low-dimensional null spaces. We demonstrate the robustness of HIF and HIFIR and show that they improve both accuracy and efficiency of the prior state of the art by orders of magnitude for systems with up to a million unknowns.
