A Dataset of Nonlinear Equations for Subdivision

This paper introduces the largest labeled dataset to date for solving zero-dimensional square nonlinear systems using subdivision-based methods, accompanied by a literature survey and demonstrated through solver benchmarking and applications in classifying real roots of parametric systems.

The Gist

Imagine you are trying to find hidden treasure in a massive, foggy forest. You don't know exactly where the treasure is, but you know it's somewhere within a specific boundary. Your goal is to find every single chest of gold without missing any, and without wasting time searching empty bushes.

This paper is about building a giant, organized map of these "treasure hunts" (math problems) to help computers get better at finding the gold.

Here is the breakdown of the paper using simple analogies:

1. The Problem: The "Foggy Forest"

In the world of math, solving complex equations is like navigating that foggy forest. Sometimes the paths are straight lines (easy), but often they are winding, twisting, and full of dead ends (nonlinear equations).

• The Goal: Find all the "roots" (the treasure chests) inside a specific area.
• The Method: The paper focuses on a technique called Subdivision. Imagine you have a huge map of the forest. Instead of walking every inch, you cut the map in half. Then you cut the halves in half again. You keep chopping the map into smaller and smaller squares until the squares are so small they contain only one chest of gold, or you can prove they are empty.

2. The Solution: The "Master Recipe Book"

Before this paper, researchers had scattered notes on how to navigate these forests. Some had a few maps; others had different ones. They didn't know if they were looking at the same forest or different ones.

The authors (a team of researchers from China) decided to build the ultimate library of treasure maps.

• The Collection: They dug through over 1,000 old books and digital archives. They found 451 polynomial maps (straightforward paths) and 130 non-polynomial maps (twisty, tricky paths).
• The Cleanup: They realized many maps were duplicates (like finding the same forest drawn twice). They cleaned the library, removing the copies, leaving them with a pristine collection of 581 unique challenges.
• The Expansion: To make the library even bigger, they invented 48,000 new fake treasure hunts based on real-world problems like robot arms, chemical factories, and satellite orbits.

Total: They now have a massive dataset of nearly 50,000 math problems with the answers already known.

3. The Test Drive: "The Race"

To make sure this library is useful, they put three different "search robots" (computer solvers) through a race to see who could find the treasure fastest and most accurately.

• Robot A (IbexSolve): The current champion. It's fast and uses a "depth-first" strategy (it goes deep down one path before turning back).
• Robot B (RealPaver): The reliable veteran. It's a bit slower but very thorough.
• Robot C (Maple): The old-school scholar. It uses a completely different, very precise method (symbolic math) but gets tired easily on huge forests.

The Results:

• Robot A was generally the fastest.
• Robot B was a close second.
• Robot C was great for small, simple forests but struggled with the huge, complex ones.
• The Surprise: Sometimes, Robot A missed a chest of gold because it got too confident in its pruning (cutting off paths too aggressively). This is a crucial discovery: even the best robots make mistakes in rare cases.

4. Why This Matters: "Training the Next Generation"

Why build a library of 50,000 problems?

1. Benchmarking: It's like a standardized driving test. Now, if a new robot is invented, we can test it against this library to see if it's actually better than the old ones.
2. Machine Learning: This is the most exciting part. The authors used this library to "teach" an AI.
   • The Analogy: Imagine showing a student 10,000 pictures of different forests and telling them, "If the trees look like this, there are 4 chests. If they look like that, there are 12."
   • The AI learned to look at the shape of the problem and guess how many solutions exist before even starting the search. This could make future solvers incredibly fast.

5. The Takeaway

This paper is a gift to the scientific community. It says:

"We have done the hard work of cleaning up the data, solving the problems, and checking the answers. Now, you can use this massive dataset to build better robots, train smarter AIs, and solve the unsolvable."

It turns the chaotic, foggy forest of nonlinear equations into a well-lit, mapped-out park, ready for the next generation of explorers.

Technical Summary

1. Problem Statement

Solving systems of nonlinear equations (both polynomial and transcendental) is a fundamental challenge in fields ranging from robotics to chemical engineering. While subdivision methods (Branch-and-Prune) are recognized as reliable for isolating real roots within bounded regions, their development and optimization lack a comprehensive, large-scale, labeled benchmark dataset. Existing benchmarks are often small, fragmented, or contain duplicates. Furthermore, there is a need to compare subdivision methods against symbolic and homotopy methods systematically, and to explore the application of Machine Learning (ML) to accelerate subdivision heuristics.

2. Methodology

The authors constructed a massive, labeled dataset and conducted extensive empirical evaluations using the following approach:

• Data Collection & Curation:
  • Literature Search: The authors surveyed over 1,000 papers and 300 specific subdivision-related works, alongside existing benchmark suites (IbexSolve, RealPaver, COCONUT, PHCpack, ALIAS).
  • De-duplication: They identified and removed nearly 200 duplicate systems (including those with renamed variables), resulting in a curated set of 581 non-parametric systems (451 polynomial, 130 non-polynomial).
  • Parametric Generation: To expand the dataset, they generated 48,000 zero-dimensional instances from 5 families of parametric systems derived from real-world applications:
    1. Multi-joint Robot Arms (Planar and Spatial, Trigonometric and Polynomial formulations).
    2. Stewart Platform (Parallel robotics).
    3. Kuramoto Model (Coupled oscillators).
    4. Flash Unit (Chemical engineering separation).
    5. Initial Orbit Determination (Astronomy).
• Solver Execution:
  • The dataset was processed using two state-of-the-art subdivision solvers (IbexSolve and RealPaver) and a symbolic solver (Maple's RootFinding:-Isolate).
  • Constraints: A time limit of 1,000 seconds was imposed. IbexSolve used a bisection tolerance of $10^{-6}$.
  • Labeling: The output includes computation time, the number of certified solutions, suspect (uncertified) regions, and the total number of solution boxes.

3. Key Contributions

1. The Largest Real Dataset: The paper presents the largest known labeled dataset of zero-dimensional nonlinear systems suitable for subdivision methods, containing over 48,000 instances.
2. Rigorous De-duplication and Verification: A significant effort was made to remove duplicates and cross-verify solutions using multiple solvers to ensure data reliability.
3. Comprehensive Benchmarking: The authors provide a systematic comparison of subdivision solvers (IbexSolve vs. RealPaver) and their performance against symbolic methods (Maple) across diverse problem types.
4. Machine Learning Feasibility Study: The dataset was used to train ML models (KNN, SVM, Random Forest) to predict the number of real roots for parametric systems, demonstrating the dataset's utility for AI-driven solver development.
5. Identification of Solver Weaknesses: The study uncovered specific implementation issues and edge cases in leading solvers, particularly regarding linear relaxation and numerical stability.

4. Key Results & Findings

A. Solver Performance Comparison

• IbexSolve vs. RealPaver:
  • Efficiency: IbexSolve is statistically faster than RealPaver overall. On the 581 non-parametric benchmarks, IbexSolve solved 459 instances within the time limit, while RealPaver solved 385.
  • Uniqueness: Neither solver is universally superior. RealPaver outperformed IbexSolve on specific high-dimensional families (e.g., Yamamura and Trigo series).
  • Certification: IbexSolve provides certified uniqueness for solutions, whereas RealPaver (in the tested configuration) primarily outputs boxes meeting precision criteria without always certifying uniqueness.
• Subdivision vs. Symbolic (Maple):
  • Scope: Symbolic methods (Maple) are limited to polynomial systems and struggle with high-dimensional or complex algebraic structures.
  • Performance: On polynomial systems, IbexSolve generally outperformed Maple in speed and coverage. Maple excelled on lower-degree systems with intricate algebraic structures but failed on many high-dimensional instances where subdivision methods succeeded.
  • Consistency: In cases where Maple found more solutions than IbexSolve, the "missing" solutions were located within IbexSolve's "suspect" (uncertified) boxes, often due to root multiplicity ($det(J) \approx 0$).

B. Solver Anomalies and Insights

• Linear Relaxation Issues: The study found that IbexSolve's linear relaxation component (based on floating-point LP) can occasionally lead to over-aggressive pruning, causing the solver to miss certified solutions. Disabling this component restored correct results in specific Kuramoto and Robot Arm instances.
• Tolerance Sensitivity: Counter-intuitively, relaxing the bisection tolerance from $10^{-6}$ to $10^{-3}$ allowed IbexSolve to certify more instances within the time limit. This suggests that tighter tolerances consume excessive computational budget on propagation, leaving insufficient resources for final certification.
• Inconsistencies: In a few robot arm cases, trigonometric and polynomial formulations of the same problem yielded inconsistent certified counts, highlighting solver instability.

C. Machine Learning Application

• Using the Kuramoto model dataset (10,000 instances), the authors trained models to predict the number of real roots based on parameters.
• K-Nearest Neighbors (KNN) achieved the highest accuracy (93.3%), significantly outperforming SVM (55.1%) and Random Forest (89.8%). This demonstrates the dataset's potential for training heuristics to guide subdivision strategies.

5. Significance

• Benchmarking Standard: This dataset establishes a new gold standard for evaluating subdivision solvers, allowing researchers to objectively compare algorithms on a diverse, real-world scale.
• AI for Scientific Computing: By providing labeled data on root counts and solver behaviors, the dataset enables the development of ML-based strategies to optimize subdivision heuristics (e.g., node selection, bisection direction), potentially overcoming the limitations of human-designed heuristics.
• Solver Improvement: The identification of specific failure modes (e.g., linear relaxation bugs, tolerance trade-offs) provides actionable feedback for developers of subdivision solvers like IbexSolve and RealPaver.
• Methodological Insight: The work clarifies the trade-offs between subdivision, symbolic, and homotopy methods, suggesting that hybrid or feature-driven approaches may be necessary for robust general-purpose solving.

In conclusion, this paper not only delivers a critical resource for the computational mathematics community but also bridges the gap between traditional numerical methods and modern machine learning techniques for solving nonlinear equations.