Use of Iterative Refinement in the Solution of Sparse Linear Systems

TLDR

For dense linear systems, Gaussian elimination with iterative refinement (IR) typically yields higher accuracy than elimination alone, but at the cost of roughly doubled storage and extra computation, whereas for sparse matrices the accuracy advantage remains but the additional overhead is still a concern. This study experimentally demonstrates that applying IR to sparse matrix techniques can simultaneously reduce both storage requirements and computation time, a benefit not seen with dense matrices. The authors introduce a drop‑tolerance T and a stability factor u > 1 to selectively discard small entries and relax partial‑pivoting, thereby preserving sparsity while allowing IR to recover any accuracy lost by large T or u values. Experiments show that although large T or u can produce inaccurate factorizations, the iterative refinement step restores precision, leading to the conclusion that IR is a viable option in many sparse‑system solvers.

Abstract

It is well known that if Gaussian elimination with iterative refinement (IR) is used in the solution of systems of linear algebraic equations $Ax = b$ whose matrices are dense, then the accuracy of the results will usually be greater than the accuracy obtained by the use of Gaussian elimination without iterative refinement (DS). However, both more storage (about $100\% $, because a copy of matrix A is needed) and more computing time (some extra time is needed to perform the iterative process) must be used with IR. Normally, when the matrix is sparse the accuracy of the solution computed by some sparse matrix technique and IR will still be greater. In this paper it is verified (by many numerical experiments) that the use of sparse matrix techniques with IR may also result in a reduction of both the computing time and the storage requirements (this will never happen when IR is applied for dense matrices). Two parameters, a drop-tolerance $T \geqq 0$ and a stability factor $u > 1$, are introduced in the efforts to achieve such a reduction. By the use of positive values for T some “small” elements are dropped. By the use of $u > 1$ the stability requirements in the popular partial pivoting (where $u = 1$) are relaxed in an attempt to preserve the sparsity of matrix A. The use of a large T and/or a large u leads to an inaccurate factorization, but the accuracy lost is normally regained in the iterative process. Many examples are given in order to compare the use of IR with large values for T and/or u and the use of DS (where both T and u must be small) in the solution of systems whose matrices are large and sparse. The main conclusion is that iterative refinement may effectively be used as an option in many packages for the solution of sparse linear systems.