##
**Numerical stability of methods for solving augmented systems.**
*(English)*
Zbl 0868.65025

Censor, Yair (ed.) et al., Recent developments in optimization theory and nonlinear analysis. AMS/IMU special session on optimization and nonlinear analysis, May 24–26, 1995, Jerusalem, Israel. Providence, RI: American Mathematical Society. Contemp. Math. 204, 51-60 (1997).

Summary: We consider questions of scaling and accuracy of methods for solving the two coupled symmetric linear systems \(Hy+Ax=b\), \(A^Ty=c\), where \(A\in\mathbb{R}^{m\times n}\), \(m\geq n\), and \(H\in \mathbb{R}^{m\times m}\) is symmetric positive definite. Such systems, known in optimization as Karush-Kuhn-Tucker (KKT) systems, are symmetric indefinite and form the kernel in many optimization algorithms. An often used method for solving KKT systems is to compute an \(LDL^T\) factorization of the system matrix, where \(L\) is lower triangular and \(D\) is block-diagonal with \(1\times 1\) and symmetric \(2\times 2\) pivots. The pivots are chosen according to a scheme by J. R. Bunch and L. Kaufman [Math. Comput. 31, 163-179 (1977; Zbl 0355.65023)].

For the standard case, when \(H=I\), we review results from Å. Björck [Pitman Res. Notes Math. Ser. 260, 1-16 (1992; Zbl 0796.65056)] which show that for the above method to be numerically stable a scaling of the (1,1) block is needed. We give a closed expression for the optimal scaling factor, and show that for this scaling the errors in \(x\) and \(y\) are of the same size as from a norm-wise backward stable method. For the case when \(H=D^{-2}\) is diagonal we recommend a diagonal scaling such that rows of \(A\) are equilibrated before a block scaling is performed as in the standard case.

For sparse problems the scaling has to be a compromise between stability and sparsity, since the optimal scaling usually leads to unacceptable fill-in in the factorization. Accuracy of the computed solution can then usually be restored by fixed precision iterative refinement. A different scheme, due to C. C. Paige and M. A. Saunders [SIAM J. Numer. Anal. 12, 617-629 (1975; Zbl 0319.65025)], which uses SYMMLQ with a preconditioner derived from the \(LDL^T\) factorization is also described.

For the entire collection see [Zbl 0861.00014].

For the standard case, when \(H=I\), we review results from Å. Björck [Pitman Res. Notes Math. Ser. 260, 1-16 (1992; Zbl 0796.65056)] which show that for the above method to be numerically stable a scaling of the (1,1) block is needed. We give a closed expression for the optimal scaling factor, and show that for this scaling the errors in \(x\) and \(y\) are of the same size as from a norm-wise backward stable method. For the case when \(H=D^{-2}\) is diagonal we recommend a diagonal scaling such that rows of \(A\) are equilibrated before a block scaling is performed as in the standard case.

For sparse problems the scaling has to be a compromise between stability and sparsity, since the optimal scaling usually leads to unacceptable fill-in in the factorization. Accuracy of the computed solution can then usually be restored by fixed precision iterative refinement. A different scheme, due to C. C. Paige and M. A. Saunders [SIAM J. Numer. Anal. 12, 617-629 (1975; Zbl 0319.65025)], which uses SYMMLQ with a preconditioner derived from the \(LDL^T\) factorization is also described.

For the entire collection see [Zbl 0861.00014].

### MSC:

65F35 | Numerical computation of matrix norms, conditioning, scaling |

65F50 | Computational methods for sparse matrices |

65F05 | Direct numerical methods for linear systems and matrix inversion |

65K05 | Numerical mathematical programming methods |

90C20 | Quadratic programming |