article

Free access

A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane

Author:

Herbert S. WilfAuthors Info & Claims

Journal of the ACM (JACM), Volume 25, Issue 3

Pages 415 - 420

https://doi.org/10.1145/322077.322084

Published: 01 July 1978 Publication History

PDF eReader

References

[1]

GANTMACHER, F R. Apphcat:ons of the Theory of Matr:ces Wlley-lnterscience, New York, 1959, Ch V

Google Scholar

[2]

GARGANTINI, I, AND HENRICI, P Circular arithmetic and the determination of polynomml zeros Numer Math 18 (1972), 305-320

Google Scholar

[3]

HENRICl, P Umformly convergent algorithms for the simultaneous determination of all zeros of a polynomial Studies m Numer Analy 2 (1968), I-8

Google Scholar

[4]

HENRICI, P, AND GARGANTINI, I Uniformly convergent algorithms for the simultaneous determination of all zeros of a polynomial Proc Symp on Constructwe Aspects of the Fundamental Theorem of Algebra, B Dejon and P Henrlcl, Eds, Wdey-lnterscience, London, 1969, pp 77-114

Google Scholar

[5]

HENRIC1, P, AND WATKINS, B O Fmdmg zeros of a polynomial by the Q-D algorithm Comm .4CM 8 (1965), 570-574

Crossref

Google Scholar

[6]

JENKINS, i A, AND TRAUB, J F A three-stage variable-shift iteration for polynomial zeros Numer Math 14 (1970), 252-263

Google Scholar

[7]

JENKINS, M A, AND TRAUB, J F Principles for testing polynomial zerofindmg programs .4 CM Trans Math Software I (1975), 26-34

Crossref

Google Scholar

[8]

LEHMER, D H A machine method for solving polynomial equations j .4CM 8 (1961), 151-162

Crossref

Google Scholar

[9]

NtJENHUlS, A, ANt)WiLF, H S Comb:natorlal Algorithms Academic Press, New York, 1975

Google Scholar

[10]

PINKERT, J R An exact method for finding the roots of a complex polynomial `4CM Trans Math Software 2 (1976), 351-363

Crossref

Google Scholar

[11]

WEYL, H Randbemerkungen zu Hauptproblemen der Mathematik, II Fundamentalsatz der Algebra und Grundlagen der Mathematik Math Z 20 (1924), 131-150

Google Scholar

[12]

WILF, H S Mathematics for the Physscal Sciences Wiley, New York, 1962

Google Scholar

Cited By

View all

Bencs FHuijben JRegts G(2024)Approximating the chromatic polynomial is as hard as computing it exactlycomputational complexity10.1007/s00037-023-00247-833:1Online publication date: 18-Jan-2024
https://doi.org/10.1007/s00037-023-00247-8
Chekhovskoy IMedvedev SVaseva ISedov EFedoruk M(2021)Introducing phase jump tracking - a fast method for eigenvalue evaluation of the direct Zakharov-Shabat problemCommunications in Nonlinear Science and Numerical Simulation10.1016/j.cnsns.2021.10571896(105718)Online publication date: May-2021
https://doi.org/10.1016/j.cnsns.2021.105718
Vieira R(2020)How to count the number of zeros that a polynomial has on the unit circle?Journal of Computational and Applied Mathematics10.1016/j.cam.2020.113169(113169)Online publication date: Aug-2020
https://doi.org/10.1016/j.cam.2020.113169
Show More Cited By

Index Terms

A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane
1. Mathematics of computing
  1. Mathematical analysis
    1. Nonlinear equations
    2. Numerical analysis
      1. Computations on polynomials
      2. Number-theoretic computations

Recommendations

On the zeros of complex Van Vleck polynomials

Polynomial solutions to the generalized Lame equation, the Stieltjes polynomials, and the associated Van Vleck polynomials, have been studied extensively in the case of real number parameters. In the complex case, relatively little is known. Numerical ...
Zeros of exceptional Hermite polynomials

We study the zeros of exceptional Hermite polynomials associated with an even partition λ . We prove several conjectures regarding the asymptotic behaviour of both the regular (real) and the exceptional (complex) zeros. The real zeros are distributed as ...
Interlacing theorems for the zeros of some orthogonal polynomials from different sequences

We study the interlacing properties of the zeros of orthogonal polynomials p"n and r"m, m=n or n-1 where {p"n}"n"="1^~ and {r"m}"m"="1^~ are different sequences of orthogonal polynomials. The results obtained extend a conjecture by Askey, that the zeros ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 25, Issue 3

July 1978

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322077

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1978

Published in JACM Volume 25, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
834
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)5

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bencs FHuijben JRegts G(2024)Approximating the chromatic polynomial is as hard as computing it exactlycomputational complexity10.1007/s00037-023-00247-833:1Online publication date: 18-Jan-2024
https://doi.org/10.1007/s00037-023-00247-8
Chekhovskoy IMedvedev SVaseva ISedov EFedoruk M(2021)Introducing phase jump tracking - a fast method for eigenvalue evaluation of the direct Zakharov-Shabat problemCommunications in Nonlinear Science and Numerical Simulation10.1016/j.cnsns.2021.10571896(105718)Online publication date: May-2021
https://doi.org/10.1016/j.cnsns.2021.105718
Vieira R(2020)How to count the number of zeros that a polynomial has on the unit circle?Journal of Computational and Applied Mathematics10.1016/j.cam.2020.113169(113169)Online publication date: Aug-2020
https://doi.org/10.1016/j.cam.2020.113169
Li WPaulson L(2020)Evaluating Winding Numbers and Counting Complex Roots Through Cauchy Indices in Isabelle/HOLJournal of Automated Reasoning10.1007/s10817-019-09521-364:2(331-360)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1007/s10817-019-09521-3
Li WPaulson LMahboubi AMyreen M(2019)Counting polynomial roots in Isabelle/HOL: a formal proof of the Budan-Fourier theoremProceedings of the 8th ACM SIGPLAN International Conference on Certified Programs and Proofs10.1145/3293880.3294092(52-64)Online publication date: 14-Jan-2019
https://dl.acm.org/doi/10.1145/3293880.3294092
Parno MMarzouk Y(2018)Transport Map Accelerated Markov Chain Monte CarloSIAM/ASA Journal on Uncertainty Quantification10.1137/17M11346406:2(645-682)Online publication date: 10-May-2018
https://doi.org/10.1137/17M1134640
Becker RSagraloff MSharma VYap C(2018)A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iterationJournal of Symbolic Computation10.1016/j.jsc.2017.03.00986(51-96)Online publication date: May-2018
https://doi.org/10.1016/j.jsc.2017.03.009
Choi JNam SCho S(2016)Multi-Human Detection Algorithm Based on an Impulse Radio Ultra-Wideband Radar SystemIEEE Access10.1109/ACCESS.2016.26472264(10300-10309)Online publication date: 2016
https://doi.org/10.1109/ACCESS.2016.2647226
Burr M(2016)Continuous amortization and extensionsJournal of Symbolic Computation10.1016/j.jsc.2016.01.00777:C(78-126)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1016/j.jsc.2016.01.007
Razbani M(2015)Global root bracketing method with adaptive mesh refinementApplied Mathematics and Computation10.1016/j.amc.2015.06.121268:C(628-635)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.amc.2015.06.121
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

On the zeros of complex Van Vleck polynomials

Zeros of exceptional Hermite polynomials

Interlacing theorems for the zeros of some orthogonal polynomials from different sequences

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations