Digital Repository at the University of Maryland (DRUM)  >
College of Computer, Mathematical & Natural Sciences  >
Computer Science  >
Technical Reports from UMIACS 

Please use this identifier to cite or link to this item:

Title: Modified Cholesky Algorithms: A Catalog with New Approaches
Authors: Fang, Haw-ren
O'Leary, Dianne P.
Type: Technical Report
Issue Date: 8-Aug-2006
Series/Report no.: UM Computer Science Department
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)$.
Appears in Collections:Technical Reports from UMIACS
Technical Reports of the Computer Science Department

Files in This Item:

File Description SizeFormatNo. of Downloads
tr.pdf423.01 kBAdobe PDF628View/Open

All items in DRUM are protected by copyright, with all rights reserved.


DRUM is brought to you by the University of Maryland Libraries
University of Maryland, College Park, MD 20742-7011 (301)314-1328.
Please send us your comments