A FAST BJORCK-PEREYRA-TYPE ALGORITHM FOR SOLVING HESSENBERG-QUASISEPARABLE-VANDERMONDE SYSTEMS

A fast O(n(2)) algorithm is derived for solving linear systems where the coefficient matrix is a polynomial-Vandermonde matrix V-R(x) = [r(j-1)(x(i))] with polynomials {r(k)(x)} defined by a Hessenberg matrix with quasiseparable structure. The result generalizes the well-known Bjorck 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 Szego 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 Szego polynomials) several other important classes of polynomials, e. g., defined by banded Hessenberg matrices. Numerical experiments are presented that coincide with previous experiences with Bjorck-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.