Box-bisection for solving second-degree systems and the problem of clustering
Alexander P. Morgan, Vadim Shapiro · ACM Transactions on Mathematical Software · 1987
Box-bisection is a method for solving nonlinear systems. Space is subdivided into boxes of smaller and smaller diameter, and each subbox is tested for the existence of solutions by a test that either eliminates it from further consideration or marks it for subdivision. Simple bisection uses a test for the exclusion of subboxes, but no test that guarantees the existence of a unique solution in a subbox. Using this simple bisection, we show that the passed boxes tend to cluster in geometrical configura- tions whose number is stable under subdivision. This implies for many problems that the work required to do simple bisection may be prohibitive. However, improvements may be possible by grouping clusters and dynamically redefining the box proportions. The restriction to second-degree systems is sufficient to display this behavior.