Certified topology by values for surface–surface intersection curves: validated eigenvalue criteria and conditioning analysis for Lagrange-basis Bézoutian matrix pencils

The symbolic–numeric framework of Fioravanti and González-Vega (2007) attacks the surface-to-surface intersection (SSI) problem by reducing it to the topology of a plane real algebraic curve whose defining polynomial is known only 'by values' (sampled evaluations), computing resultants, subresultants and discriminants as generalized eigenvalue problems and SVD computations on Bézout matrices built in a Lagrange basis. The framework's reliability, however, rests on numerically unsupported steps: infinite generalized eigenvalues of the oversampled pencil are discarded by an unspecified numerical criterion, numerically coincident eigenvalues and nullspace vectors are merged by geometric clustering, non-general-position inputs are handled by an uncertified random change of coordinates, and the claimed SVD-based 'certificate of topological correctness' has no formal error bounds or conditioning analysis. The direct follow-up literature by the same groups (through 2017) extended the method to arrangements, offsets and hyperelliptic curves while explicitly stating that no practical bound exists to confidently discard infinite eigenvalues. The open problem is to convert this value-based pipeline into a certified algorithm: establish validated, provably grounded criteria (with practical bounds) for separating spurious infinite eigenvalues from genuine large finite ones, certify the clustering step, provide conditioning and forward-error analysis for the structured Bézoutian pencils arising in the Lagrange basis, and treat non-general-position inputs in a certified manner.

Background

In computer-aided design (CAD), the surface-to-surface intersection (SSI) problem asks for the complete intersection curve of two given surfaces; this curve drives Boolean operations, meshing and machining, and errors in its topology (missed branches, wrong connectivity near singularities) are a documented source of the 'watertightness' failures of CAD models. For two rational parametric surfaces, elimination theory reduces the SSI computation to the study of a plane real algebraic curve: intersecting the surfaces can be rephrased as the intersection of two plane curves obtained by resultant-type elimination, and the topology of a plane real algebraic curve $\mathcal{C}=\{f(x,y)=0\}$ is determined by its critical points — the common real zeros of $f$ and its partial derivative $f_y$ — together with the connection of branches between consecutive critical $x$-values.

Classical algorithms perform these eliminations symbolically, but for realistic inputs the expanded (monomial-basis) expressions of resultants and implicit equations suffer severe expression swell and are numerically unstable to convert between bases. The 2007 framework of Fioravanti and González-Vega, developed in companion work with Aruliah, Corless, Díaz-Toca, Rúa, Shakoori and others, is a value-based alternative: it assumes the polynomial $f$ (for instance the implicit equation of a parametrized curve, or the determinant of the Bézoutian matrix polynomial defining an offset curve) is available only through its values, and those of $f_y$, at sample points. Key ingredients are: the Bézout matrix (Bézoutian) of two univariate polynomials, a structured matrix whose rank drop and generalized eigenvalues encode their common roots; the Lagrange basis, in which a polynomial is represented by its values at prescribed interpolation nodes rather than by monomial coefficients (barycentric formulas then give stable evaluation and differentiation by values); and the reduction of root-finding for the elimination polynomials to generalized eigenvalue problems $Ax=\lambda Bx$ (matrix pencils) plus singular value decompositions (SVD, the standard factorization revealing the numerical rank and near-nullspaces of a matrix). For the topology pipeline, the $y$-Bézoutian $B(x)$ of $f$ and $f_y$ is assembled in the Lagrange basis from sampled values; its finite real generalized eigenvalues are the critical $x$-coordinates, the corresponding $y$-coordinates come from nullspaces of $B(\alpha)$, and the branch connection is decided by counting real roots of $f(\gamma,y)=0$ at non-critical ordinates $\gamma$.

Three reliability gaps were present from the start. First, the pencil is oversized relative to the degree of $\det B(x)$ because of oversampling, so it has infinite generalized eigenvalues that must be discarded 'by a numerical criterion', and eigenvalues or nullspace vectors representing the same critical point must be merged by geometric clustering — with no thresholds, stability guarantees, or validated strategy. The 2013 follow-up by Corless, Díaz-Toca, Fioravanti, González-Vega, Rúa and Shakoori records that no practical bound has been established to confidently discard large generalized eigenvalues as infinite, and suggests that such a bound may follow from Hadamard's inequality applied to the companion matrix pencil in the Lagrange basis. Second, correctness is proven only for inputs in general position (the leading coefficient of $f$ in $y$ has no real roots, and each vertical line contains at most one critical point); other inputs are handled by a random linear change of coordinates, without certification. Third, the claimed 'certificate of topological correctness' via SVD-based rank and near-nullspace diagnostics comes with no formal error bounds and no conditioning analysis of the structured pencils, and the cost of the eigenvalue computations on large pencils was left unanalyzed.

Adjacent certified routes exist but do not fill these gaps: exact symbolic–numeric algorithms compute the topology of planar algebraic curves with full guarantees from exact coefficient data (Berberich, Emeliyanenko, Kobel, Sagraloff, 2013), and validated numerical methods certify the topology of resultant and discriminant curves — exactly the projection curves arising in SSI — using subresultant deflation and interval-arithmetic separation criteria (Imbach, Moroz, Pouget, 2017). Both require different data models or machinery and leave the conditioning and threshold questions of the value-based Lagrange-basis Bézoutian pipeline, and the black-box evaluation setting it was designed for, unanswered.

Problem Statement

Turn the value-based symbolic–numeric topology pipeline of Fioravanti and González-Vega — which computes the topology of the plane algebraic curves arising in surface-to-surface intersection and offset computations from sampled polynomial values via Lagrange-basis Bézoutian matrix pencils, generalized eigenvalue problems and SVD — into a certified algorithm by resolving its explicitly unresolved reliability issues, which jointly serve one objective: a provably correct topological output for value-only inputs.

Specifically, for a squarefree real bivariate polynomial $f(x,y)$ (or a curve defined as $\det\mathbf{B}(x,y)=0$ for a Bézoutian matrix polynomial, as for offsets and SSI eliminants) available only through values of $f$ and $f_y$ at prescribed sampling nodes, consider the associated matrix pencil: the pencil built from the $y$-Bézoutian $B(x)$ of $f$ and $f_y$ in the Lagrange basis at the sampling nodes, which is deliberately oversized relative to $\deg\det B(x)$ because of oversampling and therefore carries infinite generalized eigenvalues alongside the finite real ones, which are exactly the critical $x$-coordinates. Then:

1. Establish a validated criterion, required to carry a proven practical bound, for deciding which computed generalized eigenvalues of the oversampled pencil are infinite (spurious, artifacts of oversampling) and which are genuine, possibly large, finite critical $x$-coordinates; no such practical bound existed as of the 2013 follow-up. The criterion must come with stability guarantees under finite-precision arithmetic and input perturbation.

2. Certify the geometric clustering step that merges numerically close eigenvalues and near-nullspace vectors representing the same critical point, so that distinct critical points are provably neither merged nor split.

3. Provide a conditioning and forward-error analysis of the structured matrix pencils arising from Bézoutians in the Lagrange basis, quantifying how errors from barycentric differentiation by values, from the alternating binomial-sized sums in the by-values resultant formula, and from finite-precision linear algebra propagate to the computed critical points and to the branch-connection decisions that determine the output topology; make the SVD-based 'certificate of topological correctness' a formal one.

4. Handle inputs not in general position (leading coefficient in $y$ with real roots, or several critical points on a vertical line, including simultaneous singularities) in a certified way, replacing or justifying the heuristic of a random linear change of coordinates, and certifying the finite-precision reliability of genericity decisions.

Items (1)-(4) jointly serve one objective, a provably correct topological output for value-only inputs, and each item removes a distinct failure mode that can invalidate that output.

The interplay of sampling density, numerical rank detection, and topology accuracy, and the development of structure-exploiting eigensolvers and complexity bounds for the large pencils, form part of the context of the same certification objective.

References

1. Mario Fioravanti, Laureano Gonzalez-Vega. Mixing symbolic and numerical approaches for the surface-to-surface intersection problem. PAMM — Proc. Appl. Math. Mech. 7(1):1022205–1022206, 2007. DOI 10.1002/pamm.200700884. https://doi.org/10.1002/pamm.200700884
2. D. A. Aruliah, Robert M. Corless, Laureano Gonzalez-Vega, Azar Shakoori. Geometric applications of the Bezout matrix in the Lagrange basis. In: Proc. Int. Workshop on Symbolic-Numeric Computation (SNC 2007), ACM, pp. 55–64, 2007. DOI 10.1145/1277500.1277511. https://doi.org/10.1145/1277500.1277511
3. Mario Fioravanti, Laureano Gonzalez-Vega, Ioana Necula. Computing the intersection of two ruled surfaces by using a new algebraic approach. Journal of Symbolic Computation 41(11):1187–1205, 2006. DOI 10.1016/j.jsc.2005.02.008. https://doi.org/10.1016/j.jsc.2005.02.008
4. Robert M. Corless, Gema M. Diaz-Toca, Mario Fioravanti, Laureano Gonzalez-Vega, Ignacio F. Rua, Azar Shakoori. Computing the topology of a real algebraic plane curve whose defining equations are available only 'by values'. Computer Aided Geometric Design 30:675–706, 2013. DOI 10.1016/j.cagd.2013.04.003. https://doi.org/10.1016/j.cagd.2013.04.003
5. Gema M. Diaz-Toca, Mario Fioravanti, Laureano Gonzalez-Vega, Azar Shakoori. Using implicit equations of parametric curves and surfaces without computing them: Polynomial algebra by values. Computer Aided Geometric Design 30:116–139, 2013. DOI 10.1016/j.cagd.2012.06.006. https://doi.org/10.1016/j.cagd.2012.06.006
6. Mario Fioravanti, Laureano Gonzalez-Vega, Jorge Caravantes. Computing the topology of an arrangement of parametric or implicit algebraic curves in the Lagrange basis. ACM Communications in Computer Algebra 49(2):53, 2015. DOI 10.1145/2815111.2815127. https://doi.org/10.1145/2815111.2815127
7. Jorge Caravantes, Gema Maria Diaz-Toca, Mario Fioravanti, Laureano Gonzalez-Vega, Ioana Necula. An algebraic framework for computing the topology of offsets to rational curves. Computer Aided Geometric Design 52–53:28–47, 2017. DOI 10.1016/j.cagd.2017.03.007. https://doi.org/10.1016/j.cagd.2017.03.007
8. Eric Berberich, Pavel Emeliyanenko, Alexander Kobel, Michael Sagraloff. Exact symbolic–numeric computation of planar algebraic curves. Theoretical Computer Science 491:1–32, 2013. DOI 10.1016/j.tcs.2013.04.014. https://doi.org/10.1016/j.tcs.2013.04.014
9. Rémi Imbach, Guillaume Moroz, Marc Pouget. A certified numerical algorithm for the topology of resultant and discriminant curves. Journal of Symbolic Computation 80:285–306, 2017. DOI 10.1016/j.jsc.2016.03.011. https://doi.org/10.1016/j.jsc.2016.03.011 (preprint arXiv:1412.3290, https://arxiv.org/abs/1412.3290, titled "Numeric certified algorithm for the topology of resultant and discriminant curves")
10. L. Busé, M. Elkadi, A. Galligo. Intersection and self-intersection of surfaces by means of Bezoutian matrices. Computer Aided Geometric Design 25:53–68, 2008. DOI 10.1016/j.cagd.2007.07.001. https://doi.org/10.1016/j.cagd.2007.07.001
11. Xiaohong Jia, Kai Li, Jinsan Cheng. Computing the Intersection of Two Rational Surfaces Using Matrix Representations. Computer-Aided Design 150:103303, 2022. DOI 10.1016/j.cad.2022.103303. https://doi.org/10.1016/j.cad.2022.103303
12. Leili Rafiee Sevyeri, Robert M. Corless. Approximate GCD in Lagrange bases. In: 2020 22nd International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), pp. 40–47, 2020. DOI 10.1109/SYNASC51798.2020.00018. https://doi.org/10.1109/SYNASC51798.2020.00018
13. Jing Yang, Wei Yang. A Basis-Preserving Algorithm for Computing the Bézout Matrix of Newton Polynomials. Journal of Systems Science and Complexity 39:1366–1386, 2026. DOI 10.1007/s11424-026-4184-1. https://doi.org/10.1007/s11424-026-4184-1 (preprint arXiv:2404.18117, https://arxiv.org/abs/2404.18117)
14. Laureano Gonzalez-Vega, Alexandre Trocado. Tools for analyzing the intersection curve between two quadrics through projection and lifting. Journal of Computational and Applied Mathematics 393:113522, 2021. DOI 10.1016/j.cam.2021.113522. https://doi.org/10.1016/j.cam.2021.113522
15. Kai Li, Jieyin Yang, Xiaohong Jia. Advances and challenges in surface–surface intersection computation — An overview. Computer-Aided Design 193:104039, 2026. DOI 10.1016/j.cad.2026.104039. https://doi.org/10.1016/j.cad.2026.104039