2019/05/09 by Juan Xu, Xu, Juan, Chee Yap +1 · 1 citation
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #FOS: Mathematics #Numerical Analysis (math.NA) #Numerical Methods and Algorithms #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.1905.03505
openalex publication_date 2019/05/09 · openalex created_date 2019/05/16 · openalex updated_date 2026/08/01
We describe a new algorithm Miranda for isolating the simple zeros of a function \boldsymbolf:\mathbb Rn→\mathbb Rn within a box B0⊆ \mathbb Rn. The function \boldsymbolf and its partial derivatives must have interval forms, but need not be polynomial. Our subdivision-based algorithm is "effective" in the sense that our algorithmic description also specifies the numerical precision hat is sufficient to certify an implementation with any standard BigFloat number type. The main predicate is the Moore-Kioustelides (MK) test, based on Miranda's Theorem (1940). Although the MK test is well-known, this paper appears to be the first synthesis of this test into a complete root isolation algorithm. We provide a complexity analysis of our algorithm based on intrinsic geometric parameters of the system. Our algorithm and complexity analysis are developed using 3 levels of description (Abstract, Interval, Effective). This methodology provides a systematic pathway for achieving effective subdivision algorithms in general.