  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.
