Certified and efficient interval-iterative computation of piecewise algebraic varieties: tolerance selection, sharp Jacobian enclosures, partition-aware subdivision, convergence analysis, and singular midpoint Jacobians

Wang and Zhang (2008) gave a certified interval-iterative algorithm for computing all real roots of a zero-dimensional piecewise algebraic variety (PAV), the common zero set of multivariate spline functions defined piecewise over a partition of a region. The method combines a Krawczyk-type interval operator, an epsilon-deviation solution concept that couples certified inclusion with membership in a specific partition cell, and tensor-Bézier (Bernstein) coefficient bounds for interval Jacobian enclosures. The method leaves five unresolved gaps: no principled rule for the tolerance epsilon; Jacobian bounds that are conservative because Bernstein coefficients over the minimal containing rectangle ignore non-rectangular cell geometry; generic bisection instead of partition-aware subdivision; no convergence-rate or cost analysis (the single numerical example required about one thousand iterations); and fallback bisection whenever the midpoint Jacobian is singular. No post-2008 work is known to close any of these five gaps in the piecewise setting: later work replaced the interval-iterative approach with symbolic-elimination and homotopy pipelines, or moved to uncertified hybrid iteration for B-spline intersections. The problem of completing the certified interval-iterative computation of PAVs, with a principled accuracy-cost guarantee, tighter cell-restricted enclosures, partition-aware subdivision, a termination and cost analysis, and certified singular-midpoint treatment, remains open.

Background

A multivariate spline is a function on a region that is a polynomial on each cell of a finite partition of the region, with the polynomial pieces glued with a prescribed smoothness across shared cell boundaries; the space of splines of degree $k$ and smoothness $C^r$ on a partition $\Delta$ is written $S_k^r(\Delta)$. Because curves and surfaces in computer-aided geometric design (CAGD) are routinely represented piecewise in this way, the classical notion of an algebraic variety (the common zero set of a system of polynomials) has a piecewise analogue: the piecewise algebraic variety (PAV) $z(f_1,\dots,f_n)$ of a system of multivariate splines is the set of their common real zeros (Wang and Zhu, 2004; Wang, 2008). A PAV is zero-dimensional when it consists of isolated points. Computing all real points of a zero-dimensional PAV is the piecewise counterpart of finding all real roots of a polynomial system and underlies practical tasks such as intersecting two spline curves or surfaces; Grandine (1989) treated the univariate case of computing zeros of spline functions.

For ordinary polynomial systems, interval arithmetic provides a standard certification route. Interval arithmetic computes with intervals that rigorously contain the exact values, so a function can be evaluated over a whole box at once. Building on the existence test of Moore (1977) and interval forms of Newton's method, the Krawczyk operator assigns to a box $X$ the box

$$K(X) = m(X) - [m(F'(X))]^{-1} f(m(X)) + \left(I - [m(F'(X))]^{-1} F'(X)\right)(X - m(X)),$$

where $m(X)$ is the midpoint vector, $F'(X)$ is an interval enclosure of the Jacobian of $f=(f_1,\dots,f_n)$ on $X$, $[m(F'(X))]^{-1}$ is the inverse of the midpoint Jacobian, and $I$ is the identity matrix. If $K(X)\cap X=\emptyset$ then $X$ contains no root; if $K(X)\subset X$ then $X$ contains a root (and under a further contraction condition, exactly one). Both conclusions are rigorous despite floating-point arithmetic.

Wang and Zhang (2008) adapted this machinery to zero-dimensional PAVs, overcoming two piecewise-specific obstacles. First, a search box may overlap several cells, on which the spline system is given by different polynomials, and a floating-point approximate root may fall on the wrong side of a cell boundary; they therefore defined an epsilon-deviation solution with respect to a cell $\delta$: a box $X^*$ satisfying the Krawczyk inclusion $K(X^*)\subset X^*$, having all coordinate widths below a prescribed tolerance $\varepsilon>0$, and whose midpoint $m(X^*)$ lies in $\delta$. The midpoint is then a certified approximate root with a certified cell assignment. Second, the Krawczyk operator needs an interval enclosure $F'(X)$ of the Jacobian; the exact extrema of the polynomial partial derivatives over a non-rectangular cell would require solving constrained nonlinear optimization problems, which is expensive. Instead, each partial derivative is expressed in tensor-Bézier (Bernstein) form over the minimal axis-aligned rectangle containing the cell's intersection with the box, and the extreme Bernstein coefficients are taken as bounds. The resulting Algorithm 6.1 is a branch-and-prune loop: test whether the current box is an epsilon-deviation solution; if not, discard it when $K(X)\cap X=\emptyset$ (a proven exclusion criterion); otherwise intersect with the Krawczyk image and bisect, with bisection also used whenever the midpoint Jacobian is singular so that its inverse is unavailable. On the paper's example, two cubic splines in $S_3^1(\Delta)$ on a four-cell triangulation with $\varepsilon=0.001$, the method needed on the order of one thousand iterations to produce two epsilon-deviation solutions.

These limitations of the method define the present problem: (i) the tolerance $\varepsilon$ is an input with no rule or theoretical criterion for choosing it to balance certification accuracy against computational cost; (ii) the Bernstein-coefficient bounds are conservative - over a triangular cell they are computed on a strictly larger rectangle, so they can substantially overestimate the true cell-restricted range of the derivatives and slow convergence; (iii) generic bisection may be suboptimal, and subdivision that respects the partition could be more efficient; (iv) no convergence-rate or total-cost analysis is given, and no argument shows that, under the conservative enclosures, the inclusion test must eventually succeed (or the emptiness test eventually apply) after finitely many bisections; (v) singular or near-singular midpoint Jacobians are handled only by immediate bisection, with no more sophisticated certified treatment in the piecewise setting.

Problem Statement

Complete the certified interval-iterative computation of real roots of zero-dimensional piecewise algebraic varieties, addressing the five open gaps of the method introduced by Wang and Zhang (2008).

Setting. A partition $\Delta=\{\delta_1,\dots,\delta_T\}$ of a region $\Omega\subset\mathbb{R}^n$ into cells is given, together with multivariate splines $f_1,\dots,f_n$ whose restriction to each cell is a known polynomial; the zero-dimensional piecewise algebraic variety $z(f_1,\dots,f_n)$ is the set of common real zeros in $\Omega$. The certified iterative scheme of the source paper applies the Moore form of the Krawczyk operator $K(X)$ with interval Jacobian enclosures obtained from tensor-Bézier coefficients over minimal containing rectangles, accepts a box as an $\varepsilon$-deviation solution when $K(X^*)\subset X^*$, all coordinate widths of $X^*$ are below $\varepsilon$, and the midpoint of $X^*$ lies in a partition cell, and otherwise prunes via the emptiness test $K(X)\cap X=\emptyset$ or bisects.

Address the following five gaps of the method with an algorithm of this certified interval-iterative type, together with its analysis. The five gaps are independent improvement directions within the same certified interval-iterative framework.

(1) Tolerance rule. An explicit rule or theoretical criterion for selecting $\varepsilon$, with a stated guarantee relating $\varepsilon$ to the certified accuracy of each reported root and a characterization of how the choice trades certification accuracy against computational cost, replacing the current user-guessed constant.

(2) Sharp cell-restricted enclosures. Interval enclosures of the Jacobian (or of the spline pieces) that are provably tighter than the tensor-Bézier-coefficient bounds over minimal containing rectangles on the non-rectangular cells where the two bounds differ - as a property of the construction, exploiting the actual cell geometry, rather than a pointwise demonstration on a single example - while remaining computable without solving a full constrained nonlinear optimization problem per cell.

(3) Partition-aware subdivision. A subdivision strategy that exploits the partition structure, with a justified efficiency benefit over generic bisection.

(4) Convergence and cost analysis. Verifiable conditions under which the algorithm terminates and enumerates all real roots of the variety (completeness) - in particular, whether and when the Krawczyk inclusion test must eventually succeed and the emptiness test eventually apply under the chosen enclosures - together with bounds or calibrated estimates of iteration and bisection counts as functions of the piecewise degrees, the number of cells, and the dimension, addressing the cost observed on large or high-degree piecewise systems.

(5) Singular midpoint Jacobians. A certified treatment of boxes in which the midpoint Jacobian $m(F'(X))$ is singular or nearly singular - existence, uniqueness, or exclusion arguments other than immediate bisection - within the piecewise spline setting.

The certified character must be preserved: every reported root carries a machine-checkable inclusion certificate together with its partition-cell assignment, and the algorithm returns all real roots of the variety, not a subset. The five components are individually motivated improvement directions within the same certified interval-iterative framework; the shared objective is a principled, efficient, fully certified solver for piecewise algebraic varieties.

References

1. Wang, Renhong; Zhang, Xiaolei (2008). Interval iterative algorithm for computing the piecewise algebraic variety. Computers & Mathematics with Applications 56(2), 565-571. DOI: 10.1016/j.camwa.2008.01.036. https://doi.org/10.1016/j.camwa.2008.01.036
2. Zhang, Xiaolei; Wang, Renhong (2009). Isolating the real roots of the piecewise algebraic variety. Computers & Mathematics with Applications 57(4), 565-570. DOI: 10.1016/j.camwa.2008.09.053. https://doi.org/10.1016/j.camwa.2008.09.053
3. Wu, Jinming; Zhang, Xiaolei (2011). An Algorithm for Isolating the Real Solutions of Piecewise Algebraic Curves. Journal of Applied Mathematics, vol. 2011, Article 658282. DOI: 10.1155/2011/658282. https://doi.org/10.1155/2011/658282
4. Wu, Jinming; Zhang, Xiaolei (2011). Real root isolation of zero-dimensional piecewise algebraic variety. Journal of Applied Mathematics & Informatics 29(1-2), 135-143. DOI: 10.14317/jami.2011.29.1_2.135. https://doi.org/10.14317/jami.2011.29.1_2.135; zbMATH: https://zbmath.org/5989771
5. Wu, Jinming (2012). Real intersection points of piecewise algebraic curves. Applied Mathematics Letters 25(10), 1299-1303. DOI: 10.1016/j.aml.2011.11.032. https://doi.org/10.1016/j.aml.2011.11.032
6. Lai, YiSheng; Wang, RenHong; Wu, JinMing (2009). Real zeros of the zero-dimensional parametric piecewise algebraic variety. Science in China Series A: Mathematics 52(4), 817-832. DOI: 10.1007/s11425-008-0141-9. https://doi.org/10.1007/s11425-008-0141-9
7. Lai, Yisheng; Wang, Renhong; Wu, Jinming (2011). Solving parametric piecewise polynomial systems. Journal of Computational and Applied Mathematics 236, 924-936. DOI: 10.1016/j.cam.2011.05.008. https://doi.org/10.1016/j.cam.2011.05.008
8. Wu, Jinming; Wang, Renhong; Zhang, Xiaolei (2015). Real root classification of parametric spline functions. Applied Mathematics and Computation 250, 212-220. DOI: 10.1016/j.amc.2014.10.094. https://doi.org/10.1016/j.amc.2014.10.094
9. Wu, Jinming; Gong, Dianxuan; Zhang, Xiaolei (2015). An upper bound of the Bezout number for piecewise algebraic curves. Journal of Computational and Applied Mathematics 273, 214-224. DOI: 10.1016/j.cam.2014.06.015. https://doi.org/10.1016/j.cam.2014.06.015
10. Ji, Zhenyi; Wu, Wenyuan; Feng, Yong; Li, Yi; Qin, Xiao Lin (2016). Numerical Method for Real Root Isolation of Semi-Algebraic System and its Applications. Journal of Computational and Theoretical Nanoscience 13(1), 803-811. DOI: 10.1166/JCTN.2016.4878 (preprint arXiv:1303.5503). https://doi.org/10.1166/JCTN.2016.4878
11. Breiding, Paul; Rose, Kemal; Timme, Sascha (2023). Certifying Zeros of Polynomial Systems Using Interval Arithmetic. ACM Transactions on Mathematical Software 49(1), 1-14. DOI: 10.1145/3580277 (preprint arXiv:2011.05000). https://doi.org/10.1145/3580277
12. Wang, Yongao; Lyu, Hangting; Chen, Xiaodiao (2024). An Efficient Method for Computing the Intersection bewteen Two B-Spline Curves. Journal of Computer-Aided Design & Computer Graphics 36(5), 687-700. DOI: 10.3724/sp.j.1089.2024.19869. https://doi.org/10.3724/sp.j.1089.2024.19869
13. Wang, Ren-Hong (2008). Recent researches on multivariate spline and piecewise algebraic variety. Journal of Computational and Applied Mathematics 221(2), 460-471. DOI: 10.1016/j.cam.2007.10.056. https://doi.org/10.1016/j.cam.2007.10.056
14. Wang, Renhong; Zhu, Chungang (2004). Piecewise algebraic varieties. Progress in Natural Science 14(7), 568-572. DOI: 10.1080/10020070412331343961. https://doi.org/10.1080/10020070412331343961
15. Grandine, Thomas A. (1989). Computing zeroes of spline functions. Computer Aided Geometric Design 6, 129-136. DOI: 10.1016/0167-8396(89)90016-2. https://doi.org/10.1016/0167-8396(89)90016-2
16. Moore, R. E. (1977). A Test for Existence of Solutions to Nonlinear Systems. SIAM Journal on Numerical Analysis 14, 611-615. DOI: 10.1137/0714040. https://doi.org/10.1137/0714040