A Gröbner free alternative for polynomial system solving

DOI10.1006/jcom.2000.0571zbMath1003.12005OpenAlexW2130918732MaRDI QIDQ5938584

Grégoire Lecerf, Bruno Salvy, Marc Giusti

Publication date: 27 January 2003

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.2000.0571

zbMATH Keywords

complexity algorithm polynomial systems algebraic varieties Kronecker package Kronecker's representation of geometric resolutions lower total degree complexity Magma Newton-Hensel lifting probabilistic algorithm univariate polynomial univariate rational functions

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Computational aspects in algebraic geometry (14Q99)

Related Items

\(u\)-generation: solving systems of polynomials equation-by-equation, Further perspectives on elimination, Jacobi's bound: Jacobi's results translated in Kőnig's, Egerváry's and Ritt's mathematical languages, A generalization of the Boulier-Buchberger criterion for the computation of characteristic sets of differential ideals, A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers, Complexity results for triangular sets, A probabilistic algorithm for computing data-discriminants of likelihood equations, Deterministic root finding over finite fields using Graeffe transforms, Stable normal forms for polynomial system solving, Solving bivariate systems using rational univariate representations, Generalized polar varieties: geometry and algorithms, Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study, Blind algebraic identification of communication channels: symbolic solution algorithms, Modular equations for hyperelliptic curves, Symbolic computation in hyperbolic programming, Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\), On the complexity exponent of polynomial system solving, Polynomial equation solving by lifting procedures for ramified fibers, Deformation techniques to solve generalised Pham systems, Modular composition modulo triangular sets and applications, Real root finding for low rank linear matrices, The first rational Chebyshev knots, On the complexity of the generalized MinRank problem, Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics, Multistationarity in structured reaction networks, Differential Elimination for Dynamical Models via Projections with Applications to Structural Identifiability, Subresultants and the Shape Lemma, Improved complexity bounds for counting points on hyperelliptic curves, Faster real root decision algorithm for symmetric polynomials, p-adic algorithm for bivariate Gröbner bases, Sparse resultants and straight-line programs, Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization, Foveal detection and approximation for singularities., Rigid continuation paths II. structured polynomial systems, Computing isolated roots of sparse polynomial systems in affine space, A signature-based algorithm for computing the nondegenerate locus of a polynomial system, Real root finding for determinants of linear matrices, On the topology of real algebraic plane curves, A concise proof of the Kronecker polynomial system solver from scratch, An FGLM-like algorithm for computing the radical of a zero-dimensional ideal, Root isolation of zero-dimensional polynomial systems with linear univariate representation, Variant quantifier elimination, A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface, A fast randomized geometric algorithm for computing Riemann-Roch spaces, Computing real radicals and \(S\)-radicals of polynomial systems, Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces, Weak identifiability for differential algebraic systems, Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems, Complexity of triangular representations of algebraic sets, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set, Bit-size estimates for triangular sets in positive dimension, Separating linear forms and rational univariate representations of bivariate systems, A generic position based method for real root isolation of zero-dimensional polynomial systems, Relaxed Hensel lifting of triangular sets, Solving determinantal systems using homotopy techniques, Exact algorithms for semidefinite programs with degenerate feasible set, A probabilistic algorithm to test local algebraic observability in polynomial time, On the bit complexity of polynomial system solving, Homotopy techniques for solving sparse column support determinantal polynomial systems, Multilinear polynomial systems: root isolation and bit complexity, Elimination for generic sparse polynomial systems, Change of order for regular chains in positive dimension, Intrinsic complexity estimates in polynomial optimization, Numerical Decomposition of the Rank-Deficiency Set of a Matrix of Multivariate Polynomials, Certified non-conservative tests for the structural stability of discrete multidimensional systems, Complexity of solving parametric polynomial systems, On solving univariate sparse polynomials in logarithmic time, Deterministic normal position transformation and its applications, On sign conditions over real multivariate polynomials, A parametric representation of totally mixed Nash equilibria, On the complexity of the resolvent representation of some prime differential ideals, Practical and Theoretical Issues for the Computation of Generalized Critical Values of a Polynomial Mapping, Probabilistic algorithms for computing resolvent representations of regular differential ideals, A geometric index reduction method for implicit systems of differential algebraic equations, Properness defects of projection and minimal discriminant variety, Fast multivariate multi-point evaluation revisited, On types of degenerate critical points of real polynomial functions, On computing absolutely irreducible components of algebraic varieties with parameters, Evaluation properties of invariant polynomials, Rational univariate reduction via toric resultants, An algorithm for implicit interpolation, Puiseux Expansions and Nonisolated Points in Algebraic Varieties, Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus, Effective de Rham cohomology — The general case, Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one, Deformation techniques for sparse systems, Unnamed Item, Evaluation techniques for zero-dimensional primary decomposition, Generators of the ideal of an algebraic space curve, Exact Algorithms for Linear Matrix Inequalities, Fast computation of a rational point of a variety over a finite field, Functional programming concepts and straight-line programs in computer algebra, Accelerated tower arithmetic, Degeneracy loci and polynomial equation solving, Computing critical points for invariant algebraic systems, Some speed-ups and speed limits for real algebraic geometry, On the complexity of the \(F_5\) Gröbner basis algorithm, AN APPLICATION OF REGULAR CHAIN THEORY TO THE STUDY OF LIMIT CYCLES, Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity, Systems of rational polynomial equations have polynomial size approximate zeros on the average, Solving parametric systems of polynomial equations over the reals through Hermite matrices

Uses Software

Cites Work