COMMUNICATION-OPTIMAL PARALLEL AND SEQUENTIAL QR AND LU FACTORIZATIONS
COMMUNICATION-OPTIMAL PARALLEL AND SEQUENTIAL QR AND LU FACTORIZATIONS
复制标题
DOI：
10.1137/080731992
复制
发表时间：
2012-01-01
影响因子：
3.1
通讯作者：
Langou, Julien
中科院分区：
文献类型：
--
作者：
Demmel, James;Grigori, Laura;Langou, Julien
我们提出了并行和顺序的稠密QR分解算法，它们在执行的通信量方面都是最优的（达到多项对数因子），并且与豪斯霍尔德QR一样稳定。我们通过推导“非斯特拉森式”QR乘法次数的新下界，并将其用于与乘法次数成正比的已知通信下界来证明最优性。我们不仅表明我们的QR算法达到了这些下界（达到多项对数因子），而且现有的LAPACK和ScaLAPACK算法渐近地执行更多的通信。我们推导了LU分解的类似通信下界，并指出文献中最近的LU算法至少达到了其中一些下界。对于高瘦矩阵的顺序和并行QR算法在实践中比一些现有算法（包括LAPACK和ScaLAPACK）有显著的加速，例如，比ScaLAPACK快达6.7倍。针对一般矩形矩阵的并行算法的性能模型预测比ScaLAPACK有显著的加速。
We present parallel and sequential dense QR factorization algorithms that are both optimal (up to polylogarithmic factors) in the amount of communication they perform and just as stable as Householder QR. We prove optimality by deriving new lower bounds for the number of multiplications done by "non-Strassen-like" QR, and using these in known communication lower bounds that are proportional to the number of multiplications. We not only show that our QR algorithms attain these lower bounds (up to polylogarithmic factors), but that existing LAPACK and ScaLAPACK algorithms perform asymptotically more communication. We derive analogous communication lower bounds for LU factorization and point out recent LU algorithms in the literature that attain at least some of these lower bounds. The sequential and parallel QR algorithms for tall and skinny matrices lead to significant speedups in practice over some of the existing algorithms, including LAPACK and ScaLAPACK, for example, up to 6.7 times over ScaLAPACK. A performance model for the parallel algorithm for general rectangular matrices predicts significant speedups over ScaLAPACK.