University of Maryland DRUM  
University of Maryland 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: http://hdl.handle.net/1903/3674

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
CS-TR-4807
UMIACS
UMIACS-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 Department
Technical Reports from UMIACS

Files in This Item:

File Description SizeFormatNo. of Downloads
tr.pdf423.01 kBAdobe PDF567View/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. -
All Contents