Matrix vector product for confluent Cauchy-like matrices with applications to confluent rational interpolation

Many important problems in pure and applied mathematics and engineering can be reduced to linear algebra on dense structured matrices. The structure of these dense matrices is understood in the sense that their n2 entries can be "compressed" to a smaller number O(n) of parameters. Operating directly on these parameters allows one to design efficient fast algorithms for these matrices. One of the most prominent matrix problems is that of multiplying a (structured) matrix with a vector. Many fundamental algorithms like convolution, Fast Fourier Transform, Fast Cosine/Sine Transform, and polynomial and rational multipoint evaluation and interpolation can be interpreted as superfast multiplication of a vector by structured matrices (like Toeplitz, DFT, Vandermonde, Cauchy). In this paper, we introduce a novel and fairly general class of structured matrices, which we call confluent Cauchy- like matrices, that contains all the above classes as a special case, and we will des a confluent Cauchy-like matrix by a vector. This is precisely what has been done in this paper

Published in:
Proceedings of the 32nd annual ACM Symposium on Theory of Computing, STOC 2000, 573-581

 Record created 2007-01-26, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)