COMPLEXITY OF MULTIPLICATION WITH VECTORS FOR STRUCTURED MATRICES

Fast algorithms for computing the product with a vector are presented for a number of classes of matrices whose properties relate to the pro perties of Toeplitz, Vandermonde, or Cauchy matrices (these matrices a re defined using the concept of displacement of a matrix) and also for their inverses. All the actions which are not dependent upon the coor dinates of the input vector are singled out in a separate preprocessin g stage. The proposed algorithms are based on new representations of t hese matrices, involving factor circulants.