Fast Algorithms with Preprocessing for Matrix-Vector Multiplication Problems

AbstractIn this paper the problem of complexity of multiplication of a matrix with a vector is studied for Toeplitz, Hankel, Vandermonde, and Cauchy matrices and for matrices connected with them (i.e., for transpose, inverse, and transpose to inverse matrices). The proposed algorithms have complexities of at most O(n log2n) flops and in a number of cases they improve the known estimates. In these algorithms, in a separate preprocessing phase, are singled out all the actions on the preparation of a given matrix which aimed at the reduction of the complexity of the second stage of computations directly connected with multiplication by an arbitrary vector. Effective algorithms for computing the Vandermonde determinant and the determination of a Cauchy matrix are given