  


Modified Cholesky Algorithms: A Catalog with New Approaches
Fang Hawren (hrfangcs.umd.edu) Abstract: Given an n by n symmetric possibly indefinite matrix A, a modified Cholesky algorithm computes a factorization of the positive definite matrix A+E, where E is a correction matrix. Since the factorization is often used to compute a Newtonlike downhill search direction for an optimization problem, the goals are to compute the modification without much additional cost and to keep A+E wellconditioned and close to A. Gill, Murray and Wright introduced a stable algorithm, with a bound of E_2=O(n^2). An algorithm of Schnabel and Eskow further guarantees E_2=O(n). We present variants that also ensure E_2=O(n). Mor\'{e} and Sorensen and Cheng and Higham used the block LBL^T factorization with blocks of order 1 or 2. Algorithms in this class have a worstcase cost O(n^3) higher than the standard Cholesky factorization. We present two new algorithms using an LTL^T factorization, with T tridiagonal, that guarantees a modification cost of at most O(n^2). Keywords: Cholesky factorization, modified Cholesky algorithms, modified Newton methods Category 1: Nonlinear Optimization Citation: University of Maryland CS Technical Report CSTR4807, August 2006. Download: [Postscript][PDF] Entry Submitted: 09/02/2006 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  