Algorithm 1022: Efficient Algorithms for Computing a Rank-Revealing UTV Factorization on Parallel Computing Architectures
Algorithm 1022: Efficient Algorithms for Computing a Rank-Revealing UTV Factorization on Parallel Computing Architectures
复制标题
算法 1022：在并行计算架构上计算显示排名的 UTV 分解的高效算法
DOI：
10.1145/3507466
复制
发表时间：
2022
影响因子：
2.7
通讯作者：
Martinsson, P. G.
中科院分区：
文献类型：
--
作者：
Heavner, N.;Igual, F. D.;Quintana-Ortí, G.;Martinsson, P. G.
随机奇异值分解（RSVD）是一种有效计算矩阵近似奇异值分解的方法。建立在支持RSVD的思想基础上，最近提出的算法“randUTV”计算给定矩阵的全因子分解，提供具有接近最优误差的低秩近似。由于randUTV的大部分都是在通信效率方面的操作，如矩阵-矩阵乘法和无枢轴QR分解，因此它比竞争的秩显示因子分解方法（如列枢轴QR）在大多数高性能计算环境中更快。在本文中，将为共享内存和分布式内存计算环境提供优化的randUTV实现。对于共享内存，randUTV在算法方面进行了重新设计，与运行时任务调度器一起，消除了数据同步点的瓶颈，以实现基于纯fork-join方法的标准分块算法的加速。分布式内存实现基于ScaLAPACK库。我们的新代码的性能相比，毫不逊色于竞争的因式分解共享内存和分布式内存架构。
Randomized singular value decomposition (RSVD) is by now a well-established technique for efficiently computing an approximate singular value decomposition of a matrix. Building on the ideas that underpin RSVD, the recently proposed algorithm “randUTV” computes afullfactorization of a given matrix that provides low-rank approximations with near-optimal error. Because the bulk ofrandUTVis cast in terms of communication-efficient operations such as matrix-matrix multiplication and unpivoted QR factorizations, it is faster than competing rank-revealing factorization methods such as column-pivoted QR in most high-performance computational settings. In this article, optimizedrandUTVimplementations are presented for both shared-memory and distributed-memory computing environments. For shared memory,randUTVis redesigned in terms of analgorithm-by-blocksthat, together with a runtime task scheduler, eliminates bottlenecks from data synchronization points to achieve acceleration over the standardblocked algorithmbased on a purely fork-join approach. The distributed-memory implementation is based on the ScaLAPACK library. The performance of our new codes compares favorably with competing factorizations available on both shared-memory and distributed-memory architectures.