A Fast Björck–Pereyra-Type Algorithm for Solving Hessenberg-Quasiseparable-Vandermonde Systems
Tom Bella, Yuli Eidelman, Israel Gohberg, I. Koltracht, Vadim Olshevsky · SIAM Journal on Matrix Analysis and Applications · 2009
A fast $\mathcal{O}(n^2)$ algorithm is derived for solving linear systems where the coefficient matrix is a polynomial-Vandermonde matrix $V_R(x)=\left[r_{j-1}(x_i)\right]$ with polynomials $\{r_k(x)\}$ defined by a Hessenberg matrix with quasiseparable structure. The result generalizes the well-known Björck–Pereyra algorithm for classical Vandermonde systems involving monomials. It also generalizes the algorithms of Reichel–Opfer for $V_R(x)$ involving Chebyshev polynomials of Higham for $V_R(x)$ involving real orthogonal polynomials, and a recent algorithm of the authors for $V_R(x)$ involving Szegö polynomials. The new algorithm applies to a fairly general new class of $(H,k)$-quasiseparable polynomials (Hessenberg, order k quasiseparable) that includes (along with the above mentioned classes of real orthogonal and Szegö polynomials) several other important classes of polynomials, e.g., defined by banded Hessenberg matrices. Numerical experiments are presented that coincide with previous experiences with Björck–Pereyra-type algorithms giving better forward error than Gaussian elimination, and this accuracy is consistent with the so-called Chan–Foulser conditioning of the system.