multivariate root finding with search space decomposition and randomisation
The paper presents a method for multivariate root finding that uses adaptive search space decomposition by generalised quad-trees and non-linear Lagrange polynomials to interpolate the function inside the tree nodes. The method applies randomisation to achieve robustness. Selection of start points for the Newton-Raphson like search is based on a heuristic rating of the decomposition cells. The algorithm tunes out found roots to find all solutions. Although aimed at geometric constraint solving, where functions are only partially defined and no derivatives are available, the root finding method is applicable to a wider range of problems.
root finding randomised search spatial data structures