Abstract

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

Details