面向结构矩阵的可扩展并行矩阵乘算法框架

A scalable parallel structured matrix multiplication algorithm framework

结构矩阵在科学计算和工程应用中具有重要作用,例如Cauchy、Toeplitz、Vandermonde和Hankel矩阵等。虽然这些矩阵都是稠密的,但只需要O(n)个参数(生成元)就可以表示,其中n为矩阵的维数。提出了面向结构矩阵的可扩展并行矩阵乘算法框架,利用矩阵生成元显式地构造各进程的局部矩阵块,从而减少通信开销;同时利用矩阵块的数值低秩性,进一步降低计算开销。因此,该算法框架可同时降低计算量和通信量,适用于Cannon、Fox和PUMMA等矩阵乘算法。在天河2巨型机上进行了大量的数值测试,测试结果表明,该算法可获得相对ScaLAPACK中的PDGEMM函数的8.96倍加速。

Structured matrices play an important role in scientific computing and engineering applications,such as Cauchy,Toeplitz,Vandermonde,and Hankel matrices.Although these matrices are dense,they can be expressed with only O(n)parameters(generators),where n is the dimension of the matrix.The core idea of the algorithm in this paper is to use matrix generators to explicitly construct local matrix blocks of each process,thereby reducing communication overhead.Additionally,by leveraging the numerical low-rank property of these matrix blocks.This paper further minimize computational overhead.Consequently,the proposed parallel structured matrix multiplication algorithm framework can simultaneously reduce both computational and communication costs,making it suitable for matrix multiplication algorithms like Cannon,Fox,and PUMMA.Extensive numerical tests were conducted on the Tianhe-2 supercomputer,and the results demonstrate that the proposed algorithm achieves an 8.96×speedup compared to the PDGEMM function in ScaLAPACK.