Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation
V Olshevsky, A Shokrollahi - Proceedings of the thirty-second annual …, 2000 - dl.acm.org
Proceedings of the thirty-second annual ACM symposium on Theory of computing, 2000•dl.acm.org
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 nz entries can be" compressed" to a smaller number O (n)
of parameters. Operating directly on these paxameters 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 …
to linear algebra on dense structured matrices. The structure of these dense matrices is
understood in the sense that their nz entries can be" compressed" to a smaller number O (n)
of parameters. Operating directly on these paxameters 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 …
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 nz entries can be" compressed" to a smaller number O (n) of parameters. Operating directly on these paxameters 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 study a fairly general class of structured matrices, which we suggest to call confluent Cauchy-like matrices, that contains all the above classes as a special case. We design a new superfast algorithm for multiplication of matrices from our class with vectors. Our algorithm can be regarded as a generalization of all the above mentioned fast matrix-vector multiplication algorithms. Though this result is of interest by itself, its study was motivated by the following application. In a recent paper [18] the authors derived a superfast algorithm for solving the classical tangential Nevanlinna-Pick problem (rational matrix interpolation with norm constrains). Interpolation problems of Nevanlinnv,-Piek type appear in several important applications (see, eg,[4]), and it is desirable to derive efficient algorithms for several similar problems. Though the method of [18] can be applied to compute solutions for certain other important interpolation problems (eg, of Caratheodory-Fejer), the solution for the most general confluent tangential interpolation problems cannot be easily derived from [18]• Deriving new algorithms requires to design a special fast algorithm to multiply a confluent Canchy-like matrix by a vector. This is precisely what has