Discrete geometry for algebraic elimination
algorithmconvergenceGröbner basismultivariate polynomial factorizationpolynomial systemsparse resultanttoric elimination
Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Real polynomials: location of zeros (26C10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of solutions to systems of equations (65H10) Packaged methods for numerical algorithms (65Y15)
This article surveys efficient methods based on the toric (or sparse) resultant for computing all isolated solutions of an arbitrary system of \(n\) polynomials in \(n\) unknowns. The author constructs matrix formulae which yield nontrivial multiples of the resultant thus reducing root-finding to the eigendecomposition of a square matrix or to multivariate polynomial factorization. Other elimination problems treated by resultants include the determination of predicates and the implicitization of parametric varieties. The author describes briefly the main steps in the theory of toric elimination which generalizes the results of the classical theory to polynomials described by their supports, thus exploiting their spareness. Then the construction of toric resultant matrices of Sylvester-type is presented. The solution of arbitrary algebraic system is reduced to numerical linear algebra, thus yielding methods which avoid any issues of convergence. Finally, the author gives examples with the incremental algorithm and attempts a comparison to Gröbner basis software on the systems of the cyclic \(n\)-family. All algorithms discussed are implemented either in Maple and/or in C and are available through the author's webpage. For the entire collection see [Zbl 1008.00013].
- scientific article; zbMATH DE number 5821923
- Discrete geometry and numeration
- scientific article; zbMATH DE number 1436417
- scientific article; zbMATH DE number 1013961
- Discrete geometry
- Discrete geometric analysis
- Discrete geometric analysis
- scientific article; zbMATH DE number 4063111
- scientific article; zbMATH DE number 5165709
- Solutions of systems of algebraic equations and linear maps on residue class rings
- Resultant elimination via implicit equation interpolation
- Algebraic aspects of cut elimination
- Matrices in elimination theory
- Simultaneous elimination by using several tools from real algebraic geometry
- Solving degenerate sparse polynomial systems faster
- Multigraded Sylvester forms, duality and elimination matrices
- Rational univariate reduction via toric resultants
- Matrix methods for solving algebraic systems
- Numerical instability of resultant methods for multidimensional rootfinding
- An output-sensitive algorithm for computing projections of resultant polytopes
- Compact formulae in sparse elimination (extended abstract)
- scientific article; zbMATH DE number 4154416 (Why is no real title available?)
- scientific article; zbMATH DE number 1263401 (Why is no real title available?)
- scientific article; zbMATH DE number 1104295 (Why is no real title available?)
- scientific article; zbMATH DE number 806917 (Why is no real title available?)
- The geometry of multivariate polynomial division and elimination
- Systems of three polynomials with two separated variables
- Toric resultants and applications to geometric modelling
- Toric Sylvester forms
- Sparse discriminants and applications
- Generalised characteristic polynomials
This page was built for publication: Discrete geometry for algebraic elimination
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4418122)
