Out-of-Core Implementations of Cholesky Factorization: Loop-Based versus Recursive Algorithms
Out-of-Core Implementations of Cholesky Factorization: Loop-Based versus Recursive Algorithms
复制标题
Cholesky 分解的核外实现：基于循环与递归算法
DOI：
10.1137/06067256x
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
N. Béreux
中科院分区：
文献类型：
--
作者：
N. Béreux
我们比较，在相同的框架，外的核心实现的Cholesky分解算法。候选实现是经典的块左看的变体和最近的递归公式。这两个都已经实现了真实的正定矩阵：前者在并行核外线性代数包（POOCLAPACK）库和后者在可扩展核外线性代数计算（SOLAR）库。我们进行理论分析的输入/输出（I/O）操作所需的每个变量的量。我们考虑左看算法的替代方案：一个瓦片和两个瓦片的方法。我们表明，当主内存是有限的，一个瓦片的方法产生较少的I/O量。然后，我们表明，左看的实现需要更少的I/O量比递归的变体。我们已经实现了复杂的矩阵，我们的数值实验报告。
We compare, in the same framework, out-of-core implementations of the Cholesky factorization algorithm. The candidate implementations are the classical blocked left-looking variant and a more recent recursive formulation. Both have been implemented for real positive definite matrices: the former in the parallel out-of-core linear algebra package (POOCLAPACK) library and the latter in the scalable out-of-core linear algebra computations (SOLAR) library. We perform a theoretical analysis of the amount of input/output (I/O) operations required by each variant. We consider alternatives for the left-looking algorithm: the one-tile and two-tiles approaches. We show that when main memory is restricted, the one-tile approach yields less I/O volume. We then show that the left-looking implementation requires less I/O volume than the recursive variant. We have implemented all for complex matrices, and we report on numerical experiments.