We present a new O(
n3) algorithm for computing the SVD of an
n ×
n polynomial Vandermonde matrix
VP = [
Pi−1(
xj)] to high relative accuracy in O(
n3) time. The
Pi are orthonormal
polynomials, deg
Pi =
i, and
xj are complex nodes. The small singular values of
VP can be arbitrarily smaller than the largest ones, so that traditional algorithms typically compute them with no relative accuracy at all.
We show that the singular values, even the tiniest ones, are usually well-conditioned functions of the data xj, justifying this computation.
We also explain how this theory can be extended to other polynomial Vandermonde matrices, involving polynomials that are not orthonormal or even orthogonal.