A Gröbner free alternative for polynomial system solving

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

Marc Giusti, Grégoire Lecerf, Bruno Salvy

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

68W40: Analysis of algorithms

68W30: Symbolic computation and algebraic computation

13P10: Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

14Q99: Computational aspects in algebraic geometry

Related Items

Modular equations for hyperelliptic curves, Unnamed Item, A probabilistic algorithm to test local algebraic observability in polynomial time, On computing absolutely irreducible components of algebraic varieties with parameters, A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers, Deterministic root finding over finite fields using Graeffe transforms, Solving bivariate systems using rational univariate representations, Modular composition modulo triangular sets and applications, On the complexity of the generalized MinRank problem, Computing isolated roots of sparse polynomial systems in affine space, Root isolation of zero-dimensional polynomial systems with linear univariate representation, Variant quantifier elimination, Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces, A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set, 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, Polynomial equation solving by lifting procedures for ramified fibers, Deformation techniques to solve generalised Pham systems, The first rational Chebyshev knots, On the topology of real algebraic plane curves, A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, Bit-size estimates for triangular sets in positive dimension, A geometric index reduction method for implicit systems of differential algebraic equations, Properness defects of projection and minimal discriminant variety, Evaluation properties of invariant polynomials, An algorithm for implicit interpolation, Blind algebraic identification of communication channels: symbolic solution algorithms, Real root finding for determinants of linear matrices, On sign conditions over real multivariate polynomials, A parametric representation of totally mixed Nash equilibria, Probabilistic algorithms for computing resolvent representations of regular differential ideals, Deformation techniques for sparse systems, Evaluation techniques for zero-dimensional primary decomposition, Generators of the ideal of an algebraic space curve, Foveal detection and approximation for singularities., Some speed-ups and speed limits for real algebraic geometry, On solving univariate sparse polynomials in logarithmic time, Functional programming concepts and straight-line programs in computer algebra, Systems of rational polynomial equations have polynomial size approximate zeros on the average, Complexity results for triangular sets, Elimination for generic sparse polynomial systems, Intrinsic complexity estimates in polynomial optimization, Complexity of solving parametric polynomial systems, Degeneracy loci and polynomial equation solving, On the complexity of the \(F_5\) Gröbner basis algorithm, Stable normal forms for polynomial system solving, Generalized polar varieties: geometry and algorithms, Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study, Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\), A concise proof of the Kronecker polynomial system solver from scratch, Change of order for regular chains in positive dimension, On the complexity of the resolvent representation of some prime differential ideals, Rational univariate reduction via toric resultants, A probabilistic algorithm for computing data-discriminants of likelihood equations, Puiseux Expansions and Nonisolated Points in Algebraic Varieties, Exact Algorithms for Linear Matrix Inequalities, AN APPLICATION OF REGULAR CHAIN THEORY TO THE STUDY OF LIMIT CYCLES, Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity, Fast computation of a rational point of a variety over a finite field, Numerical Decomposition of the Rank-Deficiency Set of a Matrix of Multivariate Polynomials, Practical and Theoretical Issues for the Computation of Generalized Critical Values of a Polynomial Mapping

Uses Software

Cites Work