Method for Verifying Solutions of Sparse Linear Systems with General Coefficients

This paper proposes a verification method for sparse linear systems $Ax=b$ with general and nonsingular coefficients. A verification method produces the error bound for a given approximate solution. Conventional methods use one of two approaches. One approach is to verify the computed solution of the normal equation ATAx=ATb by exploiting symmetric and positive definiteness; however, the condition number of ATA is the square of that for A. The other approach uses an approximate inverse matrix of the coefficient; however, the approximate inverse may be dense even if A is sparse. Here, we propose a method for the verification of solutions of sparse linear systems based on LDLT decomposition. The proposed method can reduce the fill-in and is applicable to many problems. Moreover, an efficient iterative refinement method is proposed for obtaining accurate solutions.