Computing rank‐revealing factorizations of matrices stored out‐of‐core
Computing rank‐revealing factorizations of matrices stored out‐of‐core
复制标题
计算排名——揭示存储在核心之外的矩阵的因式分解
DOI：
10.1002/cpe.7726
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Quintana‐Ortí, G.
中科院分区：
文献类型：
--
作者：
Heavner, N.;Martinsson, P. G.;Quintana‐Ortí, G.
本文描述了用于计算矩阵的显阶分解的高效算法，这些矩阵太大而不适合主存储器(RAM)，而必须存储在速度较慢的外部存储设备上，例如磁盘(核外或内存外)。传统的计算显示秩分解的算法(如列旋转的QR分解和奇异值分解)需要非常密集的通信，因为它们需要许多向量-向量和矩阵-向量运算，当数据不在RAM中时，这些运算变得非常昂贵。随机化允许重新制定新的方法，以便批量处理矩阵的大型连续块。本文描述了两种截然不同的方法。第一种是列枢转的HouseholdQR的阻塞版本，其被组织为“左看”方法，以最小化昂贵的写操作的数量。第二种方法采用UTV因式分解。它被组织为按块的算法，以重叠计算和I/O操作。由于它包含了幂迭代，因此它在揭示数字排名方面要好得多。在几台计算机上进行的数值实验表明，新算法在处理存储在慢速存储设备上的数据时，速度几乎与处理存储在RAM中的数据的传统算法一样快。
This paper describes efficient algorithms for computing rank‐revealing factorizations of matrices that are too large to fit in main memory (RAM), and must instead be stored on slow external memory devices such as disks (out‐of‐core or out‐of‐memory). Traditional algorithms for computing rank‐revealing factorizations (such as the column pivoted QR factorization and the singular value decomposition) are very communication intensive as they require many vector‐vector and matrix‐vector operations, which become prohibitively expensive when data is not in RAM. Randomization allows to reformulate new methods so that large contiguous blocks of the matrix are processed in bulk. The paper describes two distinct methods. The first is a blocked version of column pivoted Householder QR, organized as a “left‐looking” method to minimize the number of the expensive write operations. The second method results employs a UTV factorization. It is organized as an algorithm‐by‐blocks to overlap computations and I/O operations. As it incorporates power iterations, it is much better at revealing the numerical rank. Numerical experiments on several computers demonstrate that the new algorithms are almost as fast when processing data stored on slow memory devices as traditional algorithms are for data stored in RAM.
登录
查看更多内容
DOI：
--
发表时间：
2019
期刊：
arXiv.org
影响因子：
--
作者：
V. Demchik;M. Bacák;Stefan Bordag
通讯作者：
Stefan Bordag
使用 POOCLAPACK 进行并行核外胆斯基分解和 QR 分解
DOI：
--
发表时间：
2001
期刊：
Proceedings, International Parallel and Distributed Processing Symposium (IPDPS)
影响因子：
--
作者：
B. Gunter;Wesley C. Reiley;R. V. D. Geijn
通讯作者：
R. V. D. Geijn
FLAME 方法：从密集线性代数算法到高性能多加速器实现
DOI：
--
发表时间：
2012
期刊：
J. Parallel Distributed Comput.
影响因子：
--
作者：
Francisco D. Igual;E. Chan;E. Quintana;G. Quintana;R. V. D. Geijn;F. V. Zee
通讯作者：
F. V. Zee
影响因子：
14.2
作者：
Martinsson, Per-Gunnar;Tropp, Joel A.
通讯作者：
Tropp, Joel A.
算法1
DOI：
10.7717/peerj-cs.338/table-7
发表时间：
2014
期刊：
The World Wide Web Conference
影响因子：
--
作者：
Henrique de Oliveira Gressler;M. C. Cera
通讯作者：
M. C. Cera