Bordered augmented linear systems in numerical continuation and bifurcation (Q911231)

We present the algorithm GMBE to solve a block linear system \[ \begin{matrix} \begin{matrix} n \\ m \\ l \end{matrix} & \left[\begin{matrix} A_{11} & A_{12} & A_{13} \\ 0 & A_{22} & A_{23} \\ A_{31} & A_{32} & A_{33} \end{matrix}\right] & \left[\begin{matrix} x_1 \\ x_2 \\x_3 \end{matrix}\right] \\ & \begin{matrix} \;n\;& \;m\;& \;l\;\end{matrix} & l \end{matrix} = \begin{matrix} \left[\begin{matrix} f_1 \\ f_2 \\ f_3 \end{matrix}\right] & \begin{matrix} n \\ m \\ l \end{matrix} \\ l \end{matrix}, \] or \[ Mz=h \] which appears in numerical computation of turning points and symmetry-breaking bifurcation. GMBE principally uses 1 solver with \(A^ T_{11}\) and \(A^ T_{22}\) each and 2 solvers with \(A_{11}\) and \(A_{22}\) each. M must be well-conditioned but \(A_{11}\) and \(A_{22}\) may be arbitrarily ill-conditioned, in fact singular to machine precision. The error analysis requires that the solvers for \(A_{11}\), \(A_{22}\), \(A^ T_{11}\) and \(A^ T_{22}\) are stable (in the sense of backward projection of the errors) and that the solvers for \(A_{11}\), \(A_{22}\) are bounded (in a sense to be made precise). Both properties are typically possessed in practice by solvers based on either direct or iterative methods. GMBE is the first algorithm that solves \(Mz=h\) by using the solvers for \(A_{11}\) etc. as `black boxes' and does not require prior computation of the left and right singular vectors of \(A_{11}\), \(A_{22}\).