Dissertations, Theses, and Capstone Projects

Date of Degree

2-2026

Document Type

Doctoral Dissertation

Degree Name

Doctor of Philosophy

Program

Computer Science

Advisor

Victor Pan

Committee Members

Liang Zhao

Theodore Brown

WonGeun Kim

Subject Categories

Numerical Analysis and Scientific Computing | Theory and Algorithms

Keywords

polynomial root-finding, black box polynomials, symbolic-numeric computing, complexity, polynomial zeros, root-squaring

Abstract

Univariate polynomial root-finding has been studied for four millennia and very intensively in the last decades. Our {\em black box root-finder} involves no coefficients and works for a black box polynomial, defined by an oracle (that is, black box subroutine) for its evaluation. Such root-finders have various benefits, e.g., are particularly efficient where a polynomial can be evaluated fast, say, is a sum of a small number of shifted monomials (x-c)^a.

Our root-finder approximates all d complex zeros of a dth degree polynomial p(x) (aka roots of equation p(x)=0) by using Las Vegas expected number of bit-operations within a factor of b of the theoretical lower bound. When extended with disc compression techniques to get an acceleration by a factor of b/\log(b), the algorithm achieves near-optimal complexity.  That is, the resulting root-finder is expected to run almost as fast as one accesses the coefficients with a precision required for the solution within a prescribed error bound.

We also introduce an algorithm for DLG root-squaring that circumvents the classical numerical instability of the recursive iterations. By applying root-squaring to Newton's Inverse Ratios rather than coefficients, we enable the fast estimation of extremal root radii for black box polynomials. This technique provides a highly efficient exclusion test for determining whether a fixed disc on the complex plane contains any roots.

Historically the only known near-optimal polynomial root-finder was presented by V. Pan at ACM STOC 1995. It is quite involved and has never been implemented, while already in its initial implementation our new root-finder competed with user's choice package of root-finding subroutines MPSolve, according to extensive numerical experiments with standard test polynomials. Furthermore we readily extend our black box root-finder to approximation of the eigenvalues of a matrix in record expected bit operation time, which is an extension not supported by the root-finder of STOC 1995. More recently, the framework for reaching the theoretical lower bound for polynomial root-finding was further advanced by V. Pan at SODA 2024, providing the basis for the near-optimal extension of our work via disc compression.

Download

Share

COinS