Digital Repository at the University of Maryland
 Please use this identifier to cite or link to this item: http://hdl.handle.net/1903/3674

 Title: Modified Cholesky Algorithms: A Catalog with New Approaches Authors: Fang, Haw-renO'Leary, Dianne P. Type: Technical Report Issue Date: 8-Aug-2006 Series/Report no.: UM Computer Science DepartmentCS-TR-4807UMIACSUMIACS-TR-2006-27 Abstract: Given an $n \times 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 Newton-like downhill search direction for an optimization problem, the goals are to compute the modification without much additional cost and to keep $A+E$ well-conditioned and close to $A$. Gill, Murray and Wright introduced a stable algorithm, with a bound of $\|E\|_2=O(n2)$. 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 worst-case cost $O(n3)$ higher than the standard Cholesky factorization, We present a new approach using an $LTL^T$ factorization, with $T$ tridiagonal, that guarantees a modification cost of at most $O(n2)$. URI: http://hdl.handle.net/1903/3674 Appears in Collections: Technical Reports of the Computer Science DepartmentTechnical Reports from UMIACS

Files in This Item: