A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers

DOI10.1016/J.JCO.2015.11.009zbMATH Open1352.68299OpenAlexW2215141910MaRDI QIDQ272196FDOQ272196

Authors: Esmaeil Mehrabi, Éric Schost 

Publication date: 20 April 2016

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

Full work available at URL: https://doi.org/10.1016/j.jco.2015.11.009

Recommendations

• On the complexity exponent of polynomial system solving
• On the bit complexity of solving bilinear polynomial systems
• On the bit complexity of polynomial system solving
• A Gröbner free alternative for polynomial system solving
• scientific article; zbMATH DE number 1859217

zbMATH Keywords

algorithmcomplexitybivariate system

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Pseudo-random numbers; Monte Carlo methods (11K45)

Cites Work

• ISOLATE
• Powers of tensors and fast matrix multiplication
• Title not available (Why is that?)
• Sharp estimates for the arithmetic Nullstellensatz
• Nearest multivariate system with given root multiplicities
• On the asymptotic and practical complexity of solving bivariate systems over the reals
• Probabilistic algorithm for testing primality
• Riemann's hypothesis and tests for primality
• Solving zero-dimensional systems through the rational univariate representation
• Isolated points, duality and residues
• Straight-line programs in geometric elimination theory
• Computing parametric geometric resolutions
• PRIMES is in P
• Quadratic Newton iteration for systems with multiplicity
• On the complexity of computing with zero-dimensional triangular sets
• On the complexity of computing with planar algebraic curves
• An improved upper complexity bound for the topology computation of a real algebraic plane curve
• Newton's method with deflation for isolated singularities of polynomial systems
• On the computational power of pushdown automata
• PARDI!
• Change of order for bivariate triangular sets
• Rational univariate representations of bivariate systems and applications
• Separating linear forms for bivariate systems
• On the complexity of solving bivariate systems
• Title not available (Why is that?)
• Fast polynomial factorization and modular composition
• Solving bivariate systems using rational univariate representations
• Improved algorithm for computing separating linear forms for bivariate systems
• Modular composition modulo triangular sets and applications
• Fast Algorithms for Manipulating Formal Power Series
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sharp estimates for triangular sets
• Title not available (Why is that?)
• An elimination method for solving bivariate polynomial systems: eliminating the usual drawbacks
• On the complexity of solving a bivariate polynomial system
• Lifting techniques for triangular decompositions
• Computing the multiplicity structure in solving polynomial systems
• Computing the multiplicity structure from geometric involutive form
• Title not available (Why is that?)
• Computer Algebra in Scientific Computing
• Products of binomial coefficients and unreduced Farey fractions
• On solving systems of bivariate polynomials
• Deflation algorithm for the multiple roots of a system of nonlinear equations
• A Gröbner free alternative for polynomial system solving
• Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
• Bit-size estimates for triangular sets in positive dimension
• Topology and arrangement computation of semi-algebraic planar curves

Cited In (7)

• Multilinear polynomial systems: root isolation and bit complexity
• Fast computation of generic bivariate resultants
• p-adic algorithm for bivariate Gröbner bases
• Uniform Determinantal Representations
• Lexicographic Gröbner bases of bivariate polynomials modulo a univariate one
• An \(\mathfrak{m}\)-adic algorithm for bivariate Gröbner bases
• Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology

Uses Software

• Kronecker
• ISOLATE

This page was built for publication: A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q272196)