Abstract: 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. 

Key words: structured matrix, matrix multiplication, FFT, Cauchy matrix, Toeplitz matrix, distributed parallel