Modified Cholesky factorization

A simpler procedure that may result in a suitable value of / is to apply a modified Cholesky factorization as follows ... 

We assume that the function value and gradient are evaluated together in an operations (additions and multiplications), where n is the problem size and a is a problem-dependent number. The Hessian can then be computed in (a/2)n(n + 1) operations. When a sparse preconditioner M is used, we denote its number of nonzeros by m and the number of nonzeros in its Cholesky factor, L, by /. (We assume here that M either is positive-definite or is factored by a modified Cholesky factorization.) Thus M can be computed in about (a/2)nm operations. As discussed in the previous section, it is advantageous to reorder the variables a priori to minimize the fill-in for M. Alternatively, a precon-... 

E. Eskow and R. B. Schnabel, Software for a New Modified Cholesky Factorization. Computer Science Department Technical Report CU-CS-443-89, University of Colorado, Boulder, 1989. 

T. Schlick, SMM ]. Sci. Statist. Comput., in press. Modified Cholesky Factorizations for Sparse Preconditioners. 

The Gill-Murray modified Newton s method uses a Cholesky factorization of the Hessian matrix (Gill and Murray, 1974). The method is described in detail by Scales (1985). 

When the preconditioner is constructed from a natural separability of the problem into terms of differing complexity, it may not necessarily be positive-definite, as required for straightforward implementation of PCG. A very useful technique for optimization has been a replacement of the standard Cholesky factorization of positive-definite systems by a modified Cholesky (MC) al-gorithm.5 137139 The MC process detects indefiniteness during the factorization itself and produces a decomposition for... 

If B has been factorized with the modified Cholesky method B = LiDiLf... 

---