A Revised Modified Cholesky Factorization Algorithm
A Revised Modified Cholesky Factorization Algorithm
复制标题
DOI：
10.1137/s105262349833266x
复制
发表时间：
1999-04
期刊：
影响因子：
--
通讯作者：
Bobby Schnabel;E. Eskow
中科院分区：
文献类型：
--
作者：
Bobby Schnabel;E. Eskow
一种改进的Cholesky分解算法最初由Gill和Murray提出，并经过Gill、Murray和Wright的改进，被广泛用于优化算法中。自1990年引入以来，Schnabel和Eskow的另一种改进的Cholesky分解也得到了广泛的应用。与Gill- Murray- Wright算法相比，Schnabel- Eskow算法具有较小的摄动先验界（为了保证正确定性而加入），并且具有一定的计算优势，特别是对于大型问题。然而，Schnabel- Eskow算法的用户报告了两种不同情况下的案例，在这两种情况下，它对原始矩阵的修改比Gill- Murray- Wright方法所做的要大得多。本文报告了对Schnabel- Eskow算法的一个简单修改，该算法似乎纠正了该方法所有已知的计算困难，而不会损害其理论性质或在任何其他情况下的计算行为。在新的计算测试中，新算法对原始矩阵所做的修改几乎总是比Gill- Murray- Wright算法所做的修改要小，有时甚至小得多。新算法允许摄动矩阵更病态，但这似乎适用于潜在问题是病态的已知环境。
A modified Cholesky factorization algorithm introduced originally by Gill and Murray and refined by Gill, Murray, and Wright is used extensively in optimization algorithms. Since its introduction in 1990, a different modified Cholesky factorization of Schnabel and Eskow has also gained widespread usage. Compared with the Gill--Murray--Wright algorithm, the Schnabel--Eskow algorithm has a smaller a priori bound on the perturbation, added to ensure positive definiteness, and some computational advantages, especially for large problems. Users of the Schnabel--Eskow algorithm, however, have reported cases from two different contexts where it makes a far larger modification to the original matrix than is necessary and than is made by the Gill--Murray--Wright method. This paper reports on a simple modification to the Schnabel--Eskow algorithm that appears to correct all the known computational difficulties with the method, without harming its theoretical properties or its computational behavior in any other cases. In new computational tests, the modifications to the original matrix made by the new algorithm appear virtually always to be smaller than those made by the Gill--Murray--Wright algorithm, sometimes by significant amounts. The perturbed matrix is allowed to be more ill-conditioned with the new algorithm, but this seems to be appropriate in the known contexts where the underlying problem is ill-conditioned.