A Gröbner free alternative for polynomial system solving

DOI10.1006/jcom.2000.0571zbMath1003.12005MaRDI 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

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

Symbolic computation in hyperbolic programming, An FGLM-like algorithm for computing the radical of a zero-dimensional ideal, Modular equations for hyperelliptic curves, A fast randomized geometric algorithm for computing Riemann-Roch spaces, Effective de Rham cohomology — The general case, Unnamed Item, A probabilistic algorithm to test local algebraic observability in polynomial time, On computing absolutely irreducible components of algebraic varieties with parameters, Differential Elimination for Dynamical Models via Projections with Applications to Structural Identifiability, Subresultants and the Shape Lemma, Faster real root decision algorithm for symmetric polynomials, p-adic algorithm for bivariate Gröbner bases, Rigid continuation paths II. structured polynomial systems, A signature-based algorithm for computing the nondegenerate locus of a polynomial system, 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, Sparse resultants and straight-line programs, Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization, Complexity of triangular representations of algebraic sets, On the bit complexity of polynomial system solving, 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, Homotopy techniques for solving sparse column support determinantal polynomial systems, Multilinear polynomial systems: root isolation and bit complexity, Certified non-conservative tests for the structural stability of discrete multidimensional systems, Deterministic normal position transformation and its applications, Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one, Computing critical points for invariant algebraic systems, Solving parametric systems of polynomial equations over the reals through Hermite matrices, A generalization of the Boulier-Buchberger criterion for the computation of characteristic sets of differential ideals, Real root finding for low rank linear matrices, Computing real radicals and \(S\)-radicals of polynomial systems, Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems, Solving determinantal systems using homotopy techniques, Exact algorithms for semidefinite programs with degenerate feasible set, Elimination for generic sparse polynomial systems, Intrinsic complexity estimates in polynomial optimization, Complexity of solving parametric polynomial systems, Fast multivariate multi-point evaluation revisited, On types of degenerate critical points of real polynomial functions, Counting points on hyperelliptic curves with explicit real multiplication in arbitrary genus, Accelerated tower arithmetic, 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}\), Multistationarity in structured reaction networks, Improved complexity bounds for counting points on hyperelliptic curves, 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, On the complexity exponent of polynomial system solving, Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics, Weak identifiability for differential algebraic systems, 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, Further perspectives on elimination, Jacobi's bound: Jacobi's results translated in Kőnig's, Egerváry's and Ritt's mathematical languages

Uses Software

• Kronecker
• Magma
• Projective Noether
• ISOLATE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On computing the determinant in small parallel time using a small number of processors
• Definability and fast quantifier elimination in algebraically closed fields
• Lectures on results on Bezout's theorem. Notes by D. P. Patil
• Deforestation: Transforming programs to eliminate trees
• Solving systems of algebraic equations by a general elimination method
• Cauchy index computation
• Exact solution of linear equations using p-adic expansions
• The complexity of partial derivatives
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• Fast multiplication of polynomials over fields of characteristic 2
• Solving zero-dimensional systems through the rational univariate representation
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Lower bounds for diophantine approximations
• The Magma algebra system. I: The user language
• Converting bases with the Gröbner walk
• Straight-line programs in geometric elimination theory
• The Projective Noether Maple Package: Computing the dimension of a projective variety
• On the representation of rational functions of bounded complexity
• Bounds of traces in complete intersections and degrees in the Nullstellensatz
• On the intrinsic complexity of the arithmetic Nullstellensatz
• On the efficiency of effective Nullstellensätze
• On the computational power of pushdown automata
• Fast multiplication of large numbers
• Fast computation of continued fraction expansions.
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• An algorithm for division of powerseries
• Fast polynomial transform algorithms for digital convolution
• Appendix: The Magma language
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• The fundamental theorem of algebra and complexity theory
• Fast computation of GCDs
• Fast Parallel Matrix Inversion Algorithms
• Le rôle des structures de données dans les problèmes d'élimination
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Sur la complexité du principe de Tarski-Seidenberg
• On the time-space complexity of geometric elimination procedures