Implementation of the Schnabel & Eskow Modified Cholesky Factorization in the Context of a Truncated-Newton Optimization Method

We report our experience with an application of the new modified Cholesky Factorization of Schnabel & Eskow in the context of nonlinear optimization. We have implemented a modified version of the new factorization for sparse symmetric linear systems, without pivoting, and have incorporated it into the framework of a large-scale truncated Newton minimization package. In our truncated Newton algorithm, we use the preconditioned linear conjugate gradient method to solve iteratively and approximately for the Newton search direction. The MCF is used here  to guarantee that the effective preconditioner is positive definite. Details of the implementation are provided, and performance comparisons with the Gill, Murray and Wright modified Cholesky factorization for sample problems are reported. Our preliminary results demonstrate that the two modified Cholesky factorizations perform quite differently in practice in our truncated Newton context. A clear difference in timing of the modification (i.e., first nonzero increment), in addition to differences in numerical values, suggests that the Schnabel & Eskow strategy may work better for highly indefinite systems while the Gill, Murray and Wright strategy may be more effective for nearly positive definite systems. As a consequence, the new factorization may be especially useful for minimization of highly nonlinear functions by Newton methods.

Click to go back to the publication list

Webpage design by Igor Zilberman