The Singular Value Decomposition: Anatomy of Optimizing an Algorithm for Extreme Scale
The Singular Value Decomposition: Anatomy of Optimizing an Algorithm for Extreme Scale
复制标题
DOI：
10.1137/17m1117732
复制
发表时间：
2018-12-01
期刊：
影响因子：
10.2
通讯作者：
Yamazaki, Ichitaro
中科院分区：
文献类型：
--
作者：
Dongarra, Jack;Gates, Mark;Yamazaki, Ichitaro
多年来的奇异值分解或SVD的计算在其实现和算法上都有许多改进的历史。在这里，我们调查了密集矩阵的SVD算法的演变，讨论了变化的动机和绩效影响。密集的SVD方法有两个主要分支：BIDIAGONALITION和JACOBI。 Bidiagonalization方法始于Golub和Reinsch在Algol60中的实施，该方法随后在EIS包装库中移植到Fortran，后来在Linpack库中更有效地实现了当代矢量机。为了解决基于缓存的内存层次结构，将SVD算法重新列出以在Lapack库中使用3级Blas。为了解决新的体系结构，引入了Scalapack来利用分布式计算，并为GPU等加速器开发了岩浆。从算法上讲，开发了鸿沟，征服和MRRR算法以减少操作数量。尽管如此，这些方法仍然是内存绑定的，因此开发了两阶段算法，以减少记忆操作并增加计算强度，并在等离子体，DPLASMA和岩浆中有效实现。 Jacobi方法始于Kogbetliantz的双面方法和Hestenes的单方面方法。他们同样有许多发展，包括并行版和块版本以及提高收敛性的预处理。在本文中，我们通过测试对共同的现代多功能机和分布式计算平台的各种历史和当前实现来研究这些变化的影响。我们表明，算法和实施改进将SVD的速度提高了几个数量级，同时消耗的能量少40倍。
The computation of the singular value decomposition, or SVD, has a long history with many improvements over the years, both in its implementations and algorithmically. Here, we survey the evolution of SVD algorithms for dense matrices, discussing the motivation and performance impacts of changes. There are two main branches of dense SVD methods: bidiagonalization and Jacobi. Bidiagonalization methods started with the implementation by Golub and Reinsch in Algol60, which was subsequently ported to Fortran in the EIS-PACK library, and was later more efficiently implemented in the LINPACK library, targeting contemporary vector machines. To address cache-based memory hierarchies, the SVD algorithm was reformulated to use Level 3 BLAS in the LAPACK library. To address new architectures, ScaLAPACK was introduced to take advantage of distributed computing, and MAGMA was developed for accelerators such as GPUs. Algorithmically, the divide and conquer and MRRR algorithms were developed to reduce the number of operations. Still, these methods remained memory bound, so two-stage algorithms were developed to reduce memory operations and increase the computational intensity, with efficient implementations in PLASMA, DPLASMA, and MAGMA. Jacobi methods started with the two-sided method of Kogbetliantz and the one-sided method of Hestenes. They have likewise had many developments, including parallel and block versions and preconditioning to improve convergence. In this paper, we investigate the impact of these changes by testing various historical and current implementations on a common, modern multicore machine and a distributed computing platform. We show that algorithmic and implementation improvements have increased the speed of the SVD by several orders of magnitude, while using up to 40 times less energy.