Algorithm 1021: SPEX Left LU, Exactly Solving Sparse Linear Systems via a Sparse Left-looking Integer-preserving LU Factorization
Algorithm 1021: SPEX Left LU, Exactly Solving Sparse Linear Systems via a Sparse Left-looking Integer-preserving LU Factorization
复制标题
算法 1021：SPEX 左 LU，通过稀疏左视整数保留 LU 分解精确求解稀疏线性系统
DOI：
10.1145/3519024
复制
发表时间：
2022
影响因子：
2.7
通讯作者：
Davis, Timothy A.
中科院分区：
文献类型：
--
作者：
Lourenco, Christopher;Chen, Jinhao;Moreno-Centeno, Erick;Davis, Timothy A.
Spex Left LU是一个精确求解非对称稀疏线性方程组的软件包。作为稀疏精确(SPEX)软件包的一个组成部分，SPEX Left LU可以应用于任何输入矩阵A，其输入项是整数、有理或小数，并为系统提供了一种解决方案，无论是精确还是精确到用户指定的精度。Spex Left LU使用用户指定的填充缩减排序对矩阵A进行预排序，并计算具有特殊性质的左视LU分解，即用于计算LandU矩阵的每个操作都是积分的。该软件包值得注意的其他应用包括对最先进的线性求解器的稳定性和精度进行基准测试，以及确定奇异到双精度矩阵是否确实是奇异的。在计算上，本文评估了几种新的旋转算法在精确算法中的影响，对Linbox中的精确迭代求解器进行了基准测试，并对MatLab稀疏反斜杠的精度进行了基准测试。最重要的是，当迭代求解器在相当大的测试子集(包括容易实例和难实例)上失败时，SPEX Left LU在运行时的性能和稳定性上都优于精确迭代求解器。SPEX Left LU包是用ANSI C编写的，带有一个MATLAB接口，并通过GitHub作为SPEX软件包的一个组件和SuiteSparse的一个组件分发。
SPEX Left LU is a software package for exactly solving unsymmetric sparse linear systems. As a component of the sparse exact (SPEX) software package, SPEX Left LU can be applied to any input matrix,A, whose entries are integral, rational, or decimal, and provides a solution to the system, which is either exact or accurate to user-specified precision. SPEX Left LU preorders the matrixAwith a user-specified fill-reducing ordering and computes a left-looking LU factorization with the special property that each operation used to compute theLandUmatrices is integral. Notable additional applications of this package include benchmarking the stability and accuracy of state-of-the-art linear solvers and determining whether singular-to-double-precision matrices are indeed singular. Computationally, this article evaluates the impact of several novel pivoting schemes in exact arithmetic, benchmarks the exact iterative solvers within Linbox, and benchmarks the accuracy of MATLAB sparse backslash. Most importantly, it is shown that SPEX Left LU outperforms the exact iterative solvers in run time oneasyinstances and in stability as the iterative solver fails on a sizeable subset of the tested (both easy and hard) instances. The SPEX Left LU package is written in ANSI C, comes with a MATLAB interface, and is distributed via GitHub, as a component of the SPEX software package, and as a component of SuiteSparse.