Polynomial Root-Finding and Algebraic Eigenvalue Problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913407959040000 |
|---|---|
| author | Pan, Victor Y. |
| author_facet | Pan, Victor Y. |
| contents | Univariate polynomial root-finding has been studied for four millennia and very intensively in the last decades. Our new near-optimal root-finders approximate all zeros of a polynomial p almost as fast as one accesses its coefficients with the precision required for the solution within a prescribed error bound. Furthermore, our root-finders can be applied to a black box polynomial, defined by an oracle (black box subroutine) for its evaluation rather than by its coefficients. Due to this feature our root-finders support approximation of the eigenvalues of a matrix in a record Las Vegas expected bit operation time and are particularly fast for a polynomial that can be evaluated fast such as the sum of a few shifted monomials or a Mandelbrot-like polynomial defined by a recurrence. Our divide and conquer algorithm of ACM STOC 1995 is the only other known near-optimal polynomial root-finder, but it extensively uses the coefficients, is quite involved, and has never been implemented, while according to extensive numerical experiments with standard test polynomials, already a slower initial implementation of our new root-finders competes with user's choice package of root-finding subroutines MPSolve and supersedes it more and more significantly as the degree of a polynomial grows large. We elaborate upon the design and analysis of our algorithms, comment on their potential heuristic acceleration, and briefly cover polynomial root-finding by means of functional iterations. Our techniques can be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1805_12042 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Polynomial Root-Finding and Algebraic Eigenvalue Problem Pan, Victor Y. Numerical Analysis Univariate polynomial root-finding has been studied for four millennia and very intensively in the last decades. Our new near-optimal root-finders approximate all zeros of a polynomial p almost as fast as one accesses its coefficients with the precision required for the solution within a prescribed error bound. Furthermore, our root-finders can be applied to a black box polynomial, defined by an oracle (black box subroutine) for its evaluation rather than by its coefficients. Due to this feature our root-finders support approximation of the eigenvalues of a matrix in a record Las Vegas expected bit operation time and are particularly fast for a polynomial that can be evaluated fast such as the sum of a few shifted monomials or a Mandelbrot-like polynomial defined by a recurrence. Our divide and conquer algorithm of ACM STOC 1995 is the only other known near-optimal polynomial root-finder, but it extensively uses the coefficients, is quite involved, and has never been implemented, while according to extensive numerical experiments with standard test polynomials, already a slower initial implementation of our new root-finders competes with user's choice package of root-finding subroutines MPSolve and supersedes it more and more significantly as the degree of a polynomial grows large. We elaborate upon the design and analysis of our algorithms, comment on their potential heuristic acceleration, and briefly cover polynomial root-finding by means of functional iterations. Our techniques can be of independent interest. |
| title | Polynomial Root-Finding and Algebraic Eigenvalue Problem |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/1805.12042 |