DSpace Repository

Fast and backward stable computation of roots of polynomials

Show simple item record

dc.contributor.author Aurentz, Jared L.
dc.contributor.author Mach, Thomas
dc.contributor.author Vandebril, Raf
dc.contributor.author Watkins, David S.
dc.date.accessioned 2017-01-09T07:33:23Z
dc.date.available 2017-01-09T07:33:23Z
dc.date.issued 2015
dc.identifier.citation Aurentz, J. L., Mach, T., Vandebril, R., & Watkins, D. S. (2015). Fast and backward stable computation of roots of polynomials. SIAM Journal on Matrix Analysis and Applications, 36(3), 942-973. DOI: 10.1137/140983434 ru_RU
dc.identifier.uri http://nur.nu.edu.kz/handle/123456789/2225
dc.description.abstract A stable algorithm to compute the roots of polynomials is presented. The roots are found by computing the eigenvalues of the associated companion matrix by Francis's implicitly shifted QR algorithm. A companion matrix is an upper Hessenberg matrix that is unitary-plus-rankone, that is, it is the sum of a unitary matrix and a rank-one matrix. These properties are preserved by iterations of Francis's algorithm, and it is these properties that are exploited here. The matrix is represented as a product of 3n - 1 Givens rotators plus the rank-one part, so only O(n) storage space is required. In fact, the information about the rank-one part is also encoded in the rotators, so it is not necessary to store the rank-one part explicitly. Francis's algorithm implemented on this representation requires only O(n) flops per iteration and thus O(n2) flops overall. The algorithm is described, normwise backward stability is proved, and an extensive set of numerical experiments is presented. The algorithm is shown to be about as accurate as the (slow) Francis QR algorithm applied to the companion matrix without exploiting the structure. It is faster than other fast methods that have been proposed, and its accuracy is comparable or better. ru_RU
dc.language.iso en ru_RU
dc.publisher SIAM Journal on Matrix Analysis and Applications ru_RU
dc.rights Attribution-NonCommercial-ShareAlike 3.0 United States *
dc.rights.uri http://creativecommons.org/licenses/by-nc-sa/3.0/us/ *
dc.subject companion matrix ru_RU
dc.subject eigenvalue ru_RU
dc.subject polynomial ru_RU
dc.subject QR algorithm ru_RU
dc.subject root ru_RU
dc.subject rootfinding ru_RU
dc.subject rotators ru_RU
dc.title Fast and backward stable computation of roots of polynomials ru_RU
dc.type Article ru_RU

Files in this item

The following license files are associated with this item:

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-ShareAlike 3.0 United States Except where otherwise noted, this item's license is described as Attribution-NonCommercial-ShareAlike 3.0 United States

Video Guide

Submission guideSubmission guide

Submit your materials for publication to

NU Repository Drive


My Account