We consider the computation of roots of polynomials expressed in the Chebyshev basis. We extend the QR iteration presented in [Y. Eidelman, L. Gemignani, and I. Gohberg, Numer. Algorithms, 47 (2008), pp. 253-273] introducing an aggressive early deflation strategy, and showing that the rank-structure allows one to parallelize the algorithm, avoiding data dependencies which would be present in the unstructured QR. We exploit the particular structure of the colleague linearization to achieve quadratic complexity and linear storage requirements. The (unbalanced) QR iteration used for Chebyshev rootfinding does not guarantee backward stability on the polynomial coefficients, unless the vector of coefficients satisfy ||p|| ≈ 1, a hypothesis which is almost never verified for polynomials approximating smooth functions. Even though the presented method is mathematically equivalent to the unbalanced QR algorithm, we show that exploiting the rank structure allows one to guarantee a small backward error on the polynomial, up to an explicitly computable amplification factor γ1(p), which depends on the polynomial under consideration. We show that this parameter is almost always of moderate size, making the method accurate on several numerical tests, in contrast with what happens in the unstructured unbalanced QR.

Rank-structured qr for chebyshev rootfinding

Casulli A.;Robol L.
2021-01-01

Abstract

We consider the computation of roots of polynomials expressed in the Chebyshev basis. We extend the QR iteration presented in [Y. Eidelman, L. Gemignani, and I. Gohberg, Numer. Algorithms, 47 (2008), pp. 253-273] introducing an aggressive early deflation strategy, and showing that the rank-structure allows one to parallelize the algorithm, avoiding data dependencies which would be present in the unstructured QR. We exploit the particular structure of the colleague linearization to achieve quadratic complexity and linear storage requirements. The (unbalanced) QR iteration used for Chebyshev rootfinding does not guarantee backward stability on the polynomial coefficients, unless the vector of coefficients satisfy ||p|| ≈ 1, a hypothesis which is almost never verified for polynomials approximating smooth functions. Even though the presented method is mathematically equivalent to the unbalanced QR algorithm, we show that exploiting the rank structure allows one to guarantee a small backward error on the polynomial, up to an explicitly computable amplification factor γ1(p), which depends on the polynomial under consideration. We show that this parameter is almost always of moderate size, making the method accurate on several numerical tests, in contrast with what happens in the unstructured unbalanced QR.
2021
Casulli, A.; Robol, L.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1120973
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact