Modified Cholesky algorithms: A catalog with new approaches (Q948963)

In multivariate optimization, Newton-like methods generate a descent direction by solving \(Ax=-g\), with \(A\) a symmetric positive definite matrix. This can be done by Cholesky factorization. When \(A\) is not positive definite, \(A\) is replaced by \(A+E\). This symmetric perturbation \(E\) should be chosen as small as possible to make \(A+E\) positive definite, yet reasonably well conditioned, and the complexity of the resulting generalized Cholesky algorithm should only increase with a small multiple of \(n^2\) where \(n\) is the size of the matrix. Possible Cholesky-type factorizations are of the form \(LDL^T\) (\(D\) is diagonal), \(LBL^T\) (\(B\) is block diagonal with block size 1 or 2), or \(LTL^T\) (\(T\) is tridiagonal). Several algorithms from the literature are recalled and five new variations are proposed. All of them are carefully analysed, checked against the previously mentioned design criteria and tested numerically on a large set of matrices.