A Traub-like Algorithm for Hessenbergquasiseparable- Vandermonde Matrices of Arbitrary Order
Tom Bella, Vadim Olshevsky, Pavel Zhlobich, Yuli Eidelman, Israel Gohberg, E. E. Tyrtyshnikov · Birkhäuser Basel eBooks · 2010
Although Gaussian elimination uses O(n 3) operations to invert an arbitrary matrix, matrices with a special Vandermonde structure can be inverted in only O(n 2) operations by the fast Traub algorithm. The original version of Traub algorithm was numerically unstable although only a minor modification of it yields a high accuracy in practice. The Traub algorithm has been extended from Vandermonde matrices involving monomials to polynomial-Vandermonde matrices involving real orthogonal polynomials, and the Szegö polynomials. In this paper we consider a new more general class of polynomials that we suggest to call Hessenberg order m quasisseparable polynomials, or (H, m)-quasiseparable polynomials. The new class is wide enough to include all of the above important special cases, e.g., monomials, real orthogonal polynomials and the Szcgö polynomials, as well as new subclasses. We derive a fast O(n 2) Traub-like algorithm to invert the associated (H, m)-quasisseparable-Vandermonde matrices. The class of quasiseparable matrices is garnering a lot of attention recently; it has been found to be useful in designing a number fo fast algorithms. The derivation of our new Traub-like algorithm is also based on exploiting quasiseparable structure of the corresponding Hessenberg matrices. Preliminary numerical experiments are presented comparing the algorithm to standard structure ignoring methods. This paper extends our recent results in [6] from the (H,0)-and (H,1)-quasiseparable cases to the more general (H, m)-quasiseparable case.