Skip to main content
Article
A Fast Schur–Euclid-Type Algorithm for Quasiseparable Polynomials
Special Sessions in Applications of Computer Algebra (2015)
  • Sirani M. Perera, Embry–Riddle Aeronautical University
  • Vadim Olshevsky, University of Connecticut
Abstract
In this paper, a fast O(n2) algorithm is presented for computing recursive triangular factorization of a Bezoutian matrix associated with quasiseparable polynomials via a displacement equation. The new algorithm applies to a fairly general class of quasiseparable polynomials that includes real orthogonal, Szegö polynomials, and several other important classes of polynomials, e.g., those defined by banded Hessenberg matrices. While the algorithm can be seen as a Schur-type for the Bezoutian matrix it can also be seen as a Euclid-type for quasiseparable polynomials via factorization of a displacement equation. The process, i.e., fast Euclid-type algorithm for quasiseparable polynomials or Schur-type algorithm for Bezoutian associated with quasiseparable polynomials, is carried out with the help of a displacement equation satisfied by Bezoutian and Confederate matrices leading to O(n2) complexity.
Keywords
  • Quasiseparable Matrices,
  • Bezoutians,
  • Euclid Algorithm,
  • Schur Algorithm,
  • Fast Algorithms,
  • Displacement Structure
Publication Date
July 20, 2015
DOI
10.1007/978-3-319-56932-1_24
Citation Information
Sirani M. Perera and Vadim Olshevsky. "A Fast Schur–Euclid-Type Algorithm for Quasiseparable Polynomials" Special Sessions in Applications of Computer Algebra (2015) p. 341 - 383
Available at: http://works.bepress.com/sirani-perera/9/