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 period 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.
Click to go back to the publication list
Webpage design by Igor Zilberman