Fast Computation of the Zeros of a Polynomial via Factorization of the Companion Matrix | Zendy

Jared L. Aurentz | Zendy; Raf Vandebril | Zendy; David S. Watkins | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Fast Computation of the Zeros of a Polynomial via Factorization of the Companion Matrix

Author(s) -

Jared L. Aurentz,

Raf Vandebril,

David S. Watkins

Publication year - 2013

Publication title -

siam journal on scientific computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.674

H-Index - 147

eISSN - 1095-7197

pISSN - 1064-8275

DOI - 10.1137/120865392

Subject(s) - companion matrix , mathematics , eigenvalues and eigenvectors , matrix polynomial , polynomial , residual , computation , matrix (chemical analysis) , factorization , qr decomposition , algorithm , polynomial matrix , matrix decomposition , characteristic polynomial , incomplete lu factorization , condition number , algebra over a field , pure mathematics , mathematical analysis , physics , materials science , quantum mechanics , composite material

A new fast algorithm for computing the zeros of a polynomial in $O(n^{2})$ time using $O(n)$ memory is developed. The eigenvalues of the Frobenius companion matrix are computed by applying a nonunitary analogue of Francis's implicitly shifted $QR$ algorithm to a factored form of the matrix. The algorithm achieves high speed and low memory use by preserving the factored form. It also provides a residual and an error estimate for each root. Numerical tests confirm the high speed of the algorithm.status: publishe

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research