Sparse Tensors and Subdivision Methods for Finding the Zero Set of Polynomial Equations - INRIA - Institut National de Recherche en Informatique et en Automatique Access content directly
Conference Papers Year : 2024

Sparse Tensors and Subdivision Methods for Finding the Zero Set of Polynomial Equations

Abstract

Finding the solutions to a system of multivariate polynomial equations is a fundamental problem in mathematics and computer science. It involves evaluating the polynomials at many points, often chosen from a grid. In most current methods, such as subdivision, homotopy continuation, or marching cube algorithms, polynomial evaluation is treated as a black box, repeating the process for each point. We propose a new approach that partially evaluates the polynomials, allowing us to efficiently reuse computations across multiple points in a grid. Our method leverages the Compressed Sparse Fiber data structure to efficiently store and process subsets of grid points. We integrated our amortized evaluation scheme into a subdivision algorithm. Experimental results show that our approach is efficient in practice. Notably, our software \texttt{voxelize} can successfully enclose curves defined by two trivariate polynomial equations of degree $100$, a problem that was previously intractable.
Fichier principal
Vignette du fichier
casc_2024_moroz.pdf (608.5 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-04611464 , version 1 (13-06-2024)

Identifiers

  • HAL Id : hal-04611464 , version 1

Cite

Guillaume Moroz. Sparse Tensors and Subdivision Methods for Finding the Zero Set of Polynomial Equations. Computer Algebra in Scientific Computing, Sep 2024, Rennes, France. ⟨hal-04611464⟩
21 View
11 Download

Share

Gmail Mastodon Facebook X LinkedIn More