Modified Cholesky Factorizations for Sparse Preconditioners

In large-scale unconstrained optimization problems, preconditioned conjugate gradient techniques are often used to solve the Newton equations approximately. In certain applications, “natural” sparse preconditioners can be derived from the structure of the problem and can accelerate convergence significantly. Since these preconditioners are not necessarily positive definite, modified Cholesky (MC) factorizations can be applied to construct related positive definite preconditioners. This paper describes such an adaptation of two MC techniques–GMW (Gill–Murray–Wright) and SE (Schnabel–Eskow)–in a truncated Newton minimization method. This paper then analyzes their effects on three interesting test problems of moderate size. The preliminary results suggest that the two MC algorithms perform quite differently in practice. Trends can be noted for sparse problems that differ from the dense case. Differences in the size of the modifications and in their variances throughout the minimization are observed and related to problem structure and minimization progress. These differences suggest that, for the minimization method examined, SE may be advantageous for highly nonlinear functions, while GMW may be more effective for functions that are well approximated by locally convex quadratic models.