Juan Xu

Juan Xu, Huilong Lai, Yingying Cheng et al.

In this paper, we report on the largest labelled dataset constructed so far for solving zero-dimensional square nonlinear systems with subdivision-based methods. A brief, non-exhaustive survey with emphasis on the literature from the past two decades is also provided to accompany with the dataset. The value of the dataset has been demonstrated through benchmarking several solvers as well as being used for learning to classify the real roots of nonlinear parametric systems.

Juan Xu, Chee Yap

We describe a new algorithm \texttt{Miranda} for isolating the simple zeros of a function $\boldsymbol{f}:{\mathbb R}^n\to{\mathbb R}^n$ within a box $B_0\subseteq {\mathbb R}^n$. The function $\boldsymbol{f}$ 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.