ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Matrix Structures and Univariate Polynomial Rootfinding

Thu 17:30–18:00, Room AV 91.12
Computing roots of polynomials in Chebyshev basis via the Cayley transform
Thomas Mach (KU Leuven)
Joint work with Jared L. Aurentz (University of Oxford); Raf Vandebril (KU Leuven); David S. Watkins (Washington State University)

The roots of a polynomial in Chebyshev basis can be computed by finding the eigenvalues of the colleague matrix. The colleague matrix is of symmetric-plus-rank-1 form; that is the sum of a symmetric matrix and a rank-1 matrix. We will show that the Cayley transformation can be used to transform this matrix to unitary-plus-rank-1 form. The unitary-plus-rank-1 eigenvalue problem is solved using the companion QR algorithm [1].

We will demonstrate that the transformation to unitary-plus-rank-1 form is fast. We will present some examples showing that the roots are computed accurately.

  1. J. L. Aurentz, T. Mach, R. Vandebril, and D. S. Watkins, Fast and backward stable computation of roots of polynomials, SIAM Journal on Matrix Analysis and Applications, 36 (2015), pp. 942–973.