Algorithms for structured matrix-vector product of optimal bilinear complexity

For researchers in fast algorithms and numerical linear algebra, this work provides theoretically optimal algorithms for a broad class of matrix structures, though the practical impact may be limited due to the focus on bilinear complexity rather than total runtime.

This paper presents explicit algorithms for computing structured matrix-vector products (Toeplitz, Hankel, circulant, symmetric, Toeplitz-plus-Hankel, sparse, and multilevel structures) that achieve optimal bilinear complexity, i.e., using a provably minimum number of multiplications.