An Algorithm for the Vandermonde Matrix-Vector Multiplication with Reduced Multiplicative Complexity

摘要

In this chapter an algorithm for computing the Vandermonde matrix-vector product is presented. The main idea of constructing this algorithm is based on the using of Winograd's formula for inner product computation. Multiplicative complexity of the proposed algorithm is less than multiplicative complexity of the schoolbook (na?ve) method of calculation. If the schoolbook method requires MN multiplications and M(N?1) additions, the proposed algorithm takes only M + N(M + 1)/2 multiplications at the cost of extra additions compared to the na?ve method. From point of view its hardware realization on VLSI where the implementation cost of multiplier is significantly greater than implementation cost of adder, the new algorithm is generally more efficient than a na?ve algorithm. When the order of the Vandermonde matrix is relatively small, this algorithm will have smaller multiplicative complexity than the well-known "fast" algorithm for the same task.