A New Modified Cholesky Factorization
A New Modified Cholesky Factorization
复制标题
DOI：
10.1137/0911064
复制
发表时间：
1990-11
期刊：
影响因子：
--
通讯作者：
Bobby Schnabel;E. Eskow
中科院分区：
文献类型：
--
作者：
Bobby Schnabel;E. Eskow
Gill 和 Murray 改进的 Cholesky 分解在优化算法中发挥着重要作用。给定一个对称但不一定是正定矩阵 A，它计算 $A + E$ 的 Cholesky 分解，其中如果 A 是安全正定的，则 $E = 0$，否则 E 是选择使 $A + E$ 正定的对角矩阵。因式分解的成本仅比标准 Cholesky 因式分解多 $n^2$ 运算的一小部分。提出了一种具有这些相同属性的新算法，但 $||E||_\infty $ 的理论界限要小得多。它基于两种新技术，即使用 Gerschgorin 界限选择 E 的元素，以及监控正定性的新方法。在对不定矩阵的大量计算测试中，新的分解实际上总是产生比现有方法更小的 $||E||_\infty $ 值，而不会损害 $A + E$ 的条件。在某些情况下，改进是显着的。新的因式分解已经在优化算法中发挥了作用。
The modified Cholesky factorization of Gill and Murray plays an important role in optimization algorithms. Given a symmetric but not necessarily positive-definite matrix A, it computes a Cholesky factorization of $A + E$, where $E = 0$ if A is safely positive-definite, and E is a diagonal matrix chosen to make $A + E$ positive-definite otherwise. The factorization costs only a small multiple of $n^2 $ operations more than the standard Cholesky factorization. A new algorithm that has these same properties, but for which the theoretical bound on $||E||_\infty $ is substantially smaller, is presented. It is based upon two new techniques, the use of Gerschgorin bounds in selecting the elements of E, and a new way of monitoring positive definiteness. In extensive computational tests on indefinite matrices, the new factorization virtually always produces smaller values of $||E||_\infty $ than the existing method, without impairing the conditioning of $A + E$. In some cases the improvements are substantial. The new factorization has already been useful in optimization algorithms.