Sparse Tensors and Subdivision Methods for Finding the Zero Set of Polynomial Equations
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911918221950976 |
|---|---|
| author | Moroz, Guillaume |
| author_facet | Moroz, Guillaume |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_09857 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sparse Tensors and Subdivision Methods for Finding the Zero Set of Polynomial Equations Moroz, Guillaume Computational Geometry Numerical Analysis Symbolic Computation 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. |
| title | Sparse Tensors and Subdivision Methods for Finding the Zero Set of Polynomial Equations |
| topic | Computational Geometry Numerical Analysis Symbolic Computation |
| url | https://arxiv.org/abs/2406.09857 |