Dissertations, Theses, and Capstone Projects

Date of Degree

2-2024

Document Type

Dissertation

Degree Name

Ph.D.

Program

Mathematics

Advisor

Victor Pan

Committee Members

Christina Sormani

Vladimir Shpiralin

Subject Categories

Mathematics | Numerical Analysis and Computation

Keywords

polynomial, root-finding, subdivision, complexity, algorithm

Abstract

Univariate polynomial root-finding is a venerated subjects of Mathematics and Computational Mathematics studied for four millenia. In 1924 Herman Weyl published a seminal root-finder and called it an algorithmic proof of the Fundamental Theorem of Algebra. Steve Smale in 1981 and Arnold Schonhage in 1982 proposed to classify such algorithmic proofs in terms of their computational complexity. This prompted extensive research in 1980s and 1990s, culminated in a divide-and-conquer polynomial root-finder by Victor Pan at ACM STOC 1995, which used a near optimal number of bit-operations. The algorithm approximates all roots of a polynomial p almost as fast as one accesses its coefficients with a precision required for the solution within a prescribed error bound. It seemed that there was no room left for any further major progress in the area, but a new research direction was inspired by Anand Louis and Santosh S. Vempala at IEEE FOCS 2016. Unlike all previous efficient polynomial root-finders, their novel method, based on high-order Newton's iterations, involved no coefficients of polynomial p and defined p by oracle (that is, black box subroutine) for its evaluation. Louis and Vempala were motivated by application of their algorithm to fast approximation of an absolutely largest eigenvalue of a symmetric matrix, but we observe other important benefits of black box polynomial root-finders: they are particularly fast for polynomials and are immune to blowing up the coefficient size, which severely limits the efficiency of polynomial root-finders involving coefficients. The root-finder by Louis and Vempala only applies under severe restrictions on the input and output, but devising fast root-finders for more general class of black box polynomials turned out to be hard, and no new progress followed their pioneering work. We found the restrictions in the paper by Louis and Vempala hard to remove based on Newton's iterations, and we do not use these iterations. Working under the supervision of Prof. Pan and jointly with him, we extended Weyl's subdivision method of 1924 to arrive at the second near-optimal root-finder. Unlike its only near-optimal predecessor of 1995, it is a black box polynomial root-finder. Already in its initial implementation it at least competed with user's choice package of root-finding subroutines MPSolve, according to extensive numerical experiments with standard test polynomials. Our auxiliary algorithms and techniques for black box polynomials can be of independent interest.

Download

Share

COinS