Fast Approximate Computations with Cauchy Matrices and Polynomials
This work provides a practical speedup for fundamental polynomial computations in numerical computing, which are widely used in scientific computing and engineering.
The paper presents new numerical algorithms for multipoint polynomial evaluation and interpolation that run in nearly linear arithmetic time, fixing a discrepancy where previous numerical methods had quadratic cost. The algorithms achieve this by transforming Vandermonde matrices into Cauchy matrices and approximating them with hierarchically semiseparable matrices, then applying the Fast Multipole Method.
Multipoint polynomial evaluation and interpolation are fundamental for modern symbolic and numerical computing. The known algorithms solve both problems over any field of constants in nearly linear arithmetic time, but the cost grows to quadratic for numerical solution. We fix this discrepancy: our new numerical algorithms run in nearly linear arithmetic time. At first we restate our goals as the multiplication of an n-by-n Vandermonde matrix by a vector and the solution of a Vandermonde linear system of n equations. Then we transform the matrix into a Cauchy structured matrix with some special features. By exploiting them, we approximate the matrix by a generalized hierarchically semiseparable matrix, which is a structured matrix of a different class. Finally we accelerate our solution to the original problems by applying Fast Multipole Method to the latter matrix. Our resulting numerical algorithms run in nearly optimal arithmetic time when they perform the above fundamental computations with polynomials, Vandermonde matrices, transposed Vandermonde matrices, and a large class of Cauchy and Cauchy-like matrices. Some of our techniques may be of independent interest.