Displacement-structure approach to polynomial Vandermonde and related matrices (Q1362652)

Polynomial Vandermonde matrices \(V ( v_{ij})= (q_j(x_i))\) have columns with polynomial values of one fixed polynomial \(q_j\) at varying arguments and rows with varying polynomials evaluated at one fixed argument \(x_i\). While the standard Vandermonde matrix is highly ill-conditioned, three-term recurrence polynomial Vandermonde matrices contain the discrete cosine and sine transform matrices for example. All such three-term Vandermonde matrices can be inverted and linear systems with them can be solved in \(O(n^2)\) operations, compared to the standard \(O(n^3)\). This known complexity result is generalized to all polynomial Vandermonde matrices and is proved via the theory of displacement structure.