Deflated Decomposition of Solutions of Nearly Singular Systems

When solving the linear system $Ax = b$, where A may be nearly singular and b is not consistent with A, one is often interested in computing a deflated solution, i.e., a unique solution to a nearby singular but consistent system Aₛ xd = b. Kelley [14], [15] has considered deflated solutions with Aₛ corresponding to setting a small pivot of the LU-factorization of A to zero. Stewart [22] proposed an iterative algorithm for computing a deflated solution with Aₛ corresponding to setting the smallest singular value of A to zero. Kelley’s approach explicitly uses submatrices of the LU-factors whereas Stewart’s approach is implicit in that it only involves solving systems with A. In this paper, we generalize the concept of a deflated solution to that of a deflated decomposition, which expresses the solution x in terms of xd and the null vectors of Aₛ. We treat such decompositions in a uniform framework that includes the approaches of Kelley and Stewart and introduce some new deflated solutions based on the LU-factorization. Moreover, we prove some results that relate the different kinds of deflated solutions. In particular, we prove that the difference between one of the LU-based deflated solutions and the SVD-based deflated solution tends to zero as A tends to exactly singular. In addition, we present noniterative implicit algorithms for computing the LU-based decompositions. Numerical results verifying the accuracy and stability of the algorithms are presented.