Deflation Techniques and Block-Elimination Algorithms for Solving Bordered Singular Systems
Tony Fan-Cheong Chan · SIAM Journal on Scientific and Statistical Computing · 1984
In numerical continuation methods for solving parametrized nonlinear systems, one often has to solve linear systems with matrices of the following form: \[ M = \left[ {\begin{array}{*{20}c} A & b \\ {c^T } & d \\ \end{array} } \right] \] where A may become singular but M is well conditioned. If A has special structures (e.g. sparseness, special data structure, special solver), then direct Gaussian elimination on M with pivoting will destroy the structures in A. An often used method that does exploit structures in A is the block-elimination (BE) algorithm which involves solving two systems with A for each system with M. In this paper, we show that the BE algorithm may become unstable and inaccurate when A is nearly singular. We then propose a stable variant which employs deflation techniques for solving the two systems with A. The deflation techniques can be viewed as working in coordinate systems orthogonal to the approximate null vectors of A, enabling an accurate representation of the solution to be computed. The extra work amounts to a few (e.g. 2) more backsolves with A. Backward error bounds and numerical results are presented.