Stable Solvers and Block Elimination for Bordered Systems
Willy J. F. Govaerts · SIAM Journal on Matrix Analysis and Applications · 1991
Linear systems with a fairly well conditioned matrix M of the form \[ \begin{gathered} \begin{pmatrix} A & b \\ c & d \end{pmatrix} \begin{matrix} n \\ 1 \end{matrix}, \\ \begin{matrix} n & 1 \end{matrix} \end{gathered} \] for which a “black-box” solver for A is available, are considered. To solve systems with M, a mixed block elimination algorithm, called BEM, is proposed. It has the following advantages: (1) It is easier to understand and to program than the widely accepted deflated block elimination (DBE) proposed by Chan, yet allows the same broad class of solvers and has comparable accuracy. (2) It requires one less solve with A. (3) It allows a rigorous error analysis that shows why it may fail in exceptional cases (all other black-box methods known to us also fail in these cases). BEM is also compared to iterative refinement of Crout block elimination (BEC) introduced by Pryce and Govaerts. BEC allows a more restricted class of solvers than BEM but is faster in cases where a solver is given not for A but for a matrix close to A, which is often the case in applications like numerical continuation theory.