Loading...
Please wait, while we are loading the content...
A traub–like algorithm for hessenberg-quasiseparable-vandermonde.
| Content Provider | CiteSeerX |
|---|---|
| Abstract | matrices of arbitrary order T.Bella ∗ , Y.Eidelman † , I.Gohberg † , V.Olshevsky ∗ , E.Tyrtyshnikov ‡ and P.Zhlobich ∗ Abstract. 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 quasiseparable 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 Szegö polynomials, as well as new subclasses. We derive a fast O(n 2) Traub–like algorithm to invert the associated (H, m)–quasiseparable–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 of 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. 1. Introduction. Polynomial–Vandermonde |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Szeg Polynomial Quasiseparable Case Real Orthogonal Polynomial Traub Algorithm New Class Hessenberg Order Quasiseparable Polynomial Corresponding Hessenberg Matrix E.t Yrtyshnikov Quasiseparable Vandermonde Matrix Fast Algorithm I.g Ohberg General Class Important Special Case Vandermonde Matrix Y.e Idelman Polynomial Vandermonde Arbitrary Matrix P.z Hlobich Abstract Original Version Minor Modification Quasiseparable Polynomial Recent Result Quasiseparable Structure Arbitrary Order T.b Ella V.o Lshevsky Quasiseparable Matrix New Traub Special Vandermonde Structure Gaussian Elimination Fast Traub Algorithm Preliminary Numerical Experiment High Accuracy New Subclass Polynomial Vandermonde Matrix |
| Content Type | Text |
| Resource Type | Article |
