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