Balanced Incomplete Factorization
Balanced Incomplete Factorization
复制标题
DOI：
10.1137/070696088
复制
发表时间：
2008-06
影响因子：
3.1
通讯作者：
José MarÍn José Mas Rafael Bru-José-MarÍn-José-Mas-Rafael-Bru-102872903;M. T. Uring;Ma
中科院分区：
文献类型：
--
作者：
José MarÍn José Mas Rafael Bru-José-MarÍn-José-Mas-Rafael-Bru-102872903;M. T. Uring;Ma
本文提出了一种新的方阵三角形不完全分解法，它可以同时得到标准的LU或LDL^T因子（正因子）和它们的逆因子（逆因子）.在数学上，我们从基于Sherman-Morrison公式的方法[R. Bru，J. Cerdan，J. Marin，and J. Mas，SIAM J. Sci.计算：25（2003），pp. 701-715]。与鲁棒不完全分解（RIF）算法[M. Benzi和M. Tumma，Numer.线性代数应用，10（2003），pp. 385-400]这里的正因子和逆因子在整个计算中直接相互影响。因此，计算近似因子的算法可以相互平衡因子的下降并以此方式控制它们的调节。对于对称正定的情形，我们给出了不完全$LDL^T$分解的理论和算法，并对实验结果进行了讨论。我们称这种新的近似$LDL^T$分解为平衡不完全分解（BIF）。我们的实验结果证实，这种分解是非常强大的，可能是有用的，在解决困难的病态问题的预处理迭代方法。此外，直接和逆因子的计算的内部耦合导致比RIF更短的设置时间（计算近似分解的时间），RIF是一种类似的和非常高水平的鲁棒性的方法。我们还推导出一般非对称情况下的理论，但不讨论其实现。
In this paper we present a new incomplete factorization of a square matrix into triangular factors in which we get standard $LU$ or $LDL^T$ factors (direct factors) and their inverses (inverse factors) at the same time. Algorithmically, we derive this method from the approach based on the Sherman-Morrison formula [R. Bru, J. Cerdan, J. Marin, and J. Mas, SIAM J. Sci. Comput., 25 (2003), pp. 701-715]. In contrast to the robust incomplete decomposition (RIF) algorithm [M. Benzi and M. Tůma, Numer. Linear Algebra Appl., 10 (2003), pp. 385-400] the direct and inverse factors here directly influence each other throughout the computation. Consequently, the algorithm to compute the approximate factors may mutually balance dropping in the factors and control their conditioning in this way. For the symmetric positive definite case, we derive the theory and present an algorithm for computing the incomplete $LDL^T$ factorization, and we discuss experimental results. We call this new approximate $LDL^T$ factorization the balanced incomplete factorization (BIF). Our experimental results confirm that this factorization is very robust and may be useful in solving difficult ill conditioned problems by preconditioned iterative methods. Moreover, the internal coupling of the computation of direct and inverse factors results in much shorter setup times (times to compute approximate decomposition) than RIF, a method of a similar and very high level of robustness. We also derive and present the theory for the general nonsymmetric case, but do not discuss its implementation.