Multilinear polynomial systems: root isolation and bit complexity

DOI10.1016/j.jsc.2020.06.005zbMath1475.13051OpenAlexW2955135083MaRDI QIDQ1994888

Ioannis Z. Emiris, Angelos Mantzaflaris, Elias P. Tsigaridas

Publication date: 18 February 2021

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-02099556/file/emt-bhomo-jsc.pdf

zbMATH Keywords

rational univariate representationmultilinear polynomialprimitive elementbit complexityresultant matrixCayley-Koszul complexDMM separation bound

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Solving polynomial systems; resultants (13P15)

Related Items (2)

The Canny-Emiris conjecture for the sparse resultant ⋮ Koszul-Type Determinantal Formulas for Families of Mixed Multilinear Systems

Uses Software

• Kronecker
• mctoolbox
• ISOLATE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers
• Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Generalised characteristic polynomials
• Tate resolutions for Segre embeddings
• Solving zero-dimensional systems through the rational univariate representation
• Multigraded resultants of Sylvester type
• Fast algorithms for zero-dimensional polynomial systems using duality
• Symbolic and numeric methods for exploiting structure in constructing resultant matrices
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• Improved algorithms for computing determinants and resultants
• On the complexity of computing determinants
• New technique for decoding codes in the rank metric and its cryptography applications
• Multihomogeneous resultant formulae by means of complexes
• On the bit-complexity of sparse polynomial and series multiplication
• Separation bounds for polynomial systems
• Accelerated approximation of the complex roots and factors of a univariate polynomial
• Computing multihomogeneous resultants using straight-line programs
• Output-Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication
• Modern Computer Algebra
• The DMM bound
• A New Index Calculus Algorithm with Complexity $$L(1/4+o(1))$$ in Small Characteristic
• On the Bit Complexity of Solving Bilinear Polynomial Systems
• Root counts of semi-mixed systems, and an application to counting nash equilibria
• Singular Zeros of Polynomial Systems
• Cryptanalysis of MinRank
• Calculating Discriminants by Higher Direct Images
• Sharp estimates for triangular sets
• Accuracy and Stability of Numerical Algorithms
• Resultants and Chow forms via exterior syzygies
• Sparse Rational Univariate Representation
• Bilinear Systems with Two Supports
• Supersparse black box rational function interpolation
• Deflation and certified isolation of singular zeros of polynomial systems
• Multihomogeneous resultant formulae for systems with scaled support
• Nearly optimal computations with structured matrices
• A Gröbner free alternative for polynomial system solving
• Explicit formulas for the multivariate resultant.

This page was built for publication: Multilinear polynomial systems: root isolation and bit complexity