Modified Cholesky Algorithms: A Catalog with New Approaches
| dc.contributor.author | Fang, Haw-ren | |
| dc.contributor.author | O'Leary, Dianne P. | |
| dc.date.accessioned | 2006-08-08T17:32:51Z | |
| dc.date.available | 2006-08-08T17:32:51Z | |
| dc.date.issued | 2006-08-08 | |
| dc.description.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)$. | en |
| dc.format.extent | 433166 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/3674 | |
| dc.language.iso | en_US | en |
| dc.relation.ispartofseries | UM Computer Science Department | en |
| dc.relation.ispartofseries | CS-TR-4807 | en |
| dc.relation.ispartofseries | UMIACS | en |
| dc.relation.ispartofseries | UMIACS-TR-2006-27 | en |
| dc.title | Modified Cholesky Algorithms: A Catalog with New Approaches | en |
| dc.type | Technical Report | en |