Sparse Exact Factorization Update
Sparse Exact Factorization Update
复制标题
稀疏精确分解更新
DOI：
10.1109/ia354616.2021.00012
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Moreno-Centeno, Erick
中科院分区：
文献类型：
--
作者：
Chen, Jinhao;Davis, Timothy A.;Lourenco, Christopher;Moreno-Centeno, Erick
为了满足日益增长的对扩展或精确精度求解器的需求，最近开发了一种基于保整高斯消元(IPGE)的高效框架，该框架包括密集/稀疏LU/Cholesky分解和用于列和/或行替换的密集LU/Cholesky分解更新。在本文中，我们讨论了我们正在进行的开发稀疏LU/Cholesky列/行替换更新和稀疏RANK-L更新/下载的工作。我们首先介绍了基于IPGE的精确分解框架的一些基本背景。然后给出了我们提出的算法，以及一些实现和数据结构细节。最后，我们给出了一些实验结果，展示了我们的更新算法的性能。具体地说，我们展示了更新这些精确的分解通常比从头开始(重新)分解矩阵的速度快10到100倍。
To meet the growing need for extended or exact precision solvers, an efficient framework based on Integer-Preserving Gaussian Elimination (IPGE) has been recently developed which includes dense/sparse LU/Cholesky factorizations and dense LU/Cholesky factorization updates for column and/or row replacement. In this paper, we discuss our on-going work developing the sparse LU/Cholesky column/row-replacement update and the sparse rank-l update/downdate. We first present some basic background for the exact factorization framework based on IPGE. Then we give our proposed algorithms along with some implementation and data-structure details. Finally, we provide some experimental results showcasing the performance of our update algorithms. Specifically, we show that updating these exact factorizations can be typically 10x to 100x faster than (re-)factorizing the matrices from scratch.