• Chebyshev polynomials
• Numerical analysis
• Rootfinding

The aim of the thesis is to study methods for computing roots of polynomials and matrix polynomials expressed in the Chebyshev basis, with lower computational cost than the available methods.
Chebyshev polynomials have a fundamental role in approximation theory, in numerical linear algebra and in related applications. A recent application, which is a representative example of their good numerical properties, is the Matlab package ”Chebfun”, which allows to numerically handle smooth functions. The approach used in Chebfun is to interpolate smooth functions at the Chebyshev points and to write the interpolant polynomial in the Chebyshev basis. This technique has good stability properties ad can be done in a fast way by using inverse cosine transforms.
In such a context, finding roots of a polynomial in the Chebyshev basis becomes fundamental.
The main idea used to find the roots of a polynomial is to build a linearization matrix, usually called companion matrix, and find the eigenvalues of that matrix. This is what the Chebfun command roots does for computing the roots of a polynomial expressed in Chebyshev basis. This method computes the roots of a polynomial using O(n^2) memory storage and O(n^3) operations, where n is the polynomial degree.
To reduce this cost, it can be exploited the structure of the companion matrix.
The approach we use in this thesis is to exploit the structure of the companion matrix, for polynomials expressed in the Chebyshev basis, viewed as a symmetric matrix plus a rank-one correction. This fact will allow to design a fast and backward stable rootfinding algorithm based on the QR iteration. In fact, the overall computation cost of this algorithm is O(n^2) arithmetic operations with O(n) memory storage, where n is the degree of the polynomial.