Computing syzygies in finite dimension using fast linear algebra

DOI10.1016/J.JCO.2020.101502zbMath1467.13051arXiv1912.01848OpenAlexW2993822074MaRDI QIDQ2192678

Vincent Neiger, Éric Schost

Publication date: 17 August 2020

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

Full work available at URL: https://arxiv.org/abs/1912.01848

zbMATH Keywords

complexityGröbner basissyzygiesfast linear algebra

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Syzygies, resolutions, complexes and commutative rings (13D02) Numerical linear algebra (65F99)

Related Items (3)

p-adic algorithm for bivariate Gröbner bases ⋮ Fast amortized multi-point evaluation ⋮ Guessing Gröbner bases of structured ideals of relations of sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extension of the Berlekamp-Massey algorithm to N dimensions
• Recursiveness in matrix rational interpolation problems
• A general module theoretic framework for vector M-Padé and matrix rational interpolation
• Matrix multiplication via arithmetic progressions
• Fast algorithms for the characteristic polynomial
• Recurrence relations in Padé-Hermite approximation
• A theorem on refining division orders by the reverse lexicographic order
• Fast projection methods for minimal design problems in linear system theory
• The computation of non-perfect Padé-Hermite approximants
• A reliable method for computing M-Padé approximants on arbitrary staircases
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Solving a multivariable congruence by change of term order
• Gröbner basis solutions of constrained interpolation problems
• Sparse FGLM algorithms
• Fast computation of approximant bases in canonical form
• Gröbner bases of ideals defined by functionals with an application to ideals of projective points
• Canonical forms for polynomial and quadratic differential operators
• Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences
• Computing minimal interpolation bases
• Fraction-Free Computation of Matrix Rational Interpolants and Matrix GCDs
• Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences
• Guessing Linear Recurrence Relations of Sequence Tuplesand P-recursive Sequences with Linear Algebra
• Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts
• Sub-cubic change of ordering for Gröbner basis
• Powers of tensors and fast matrix multiplication
• A recursive algorithm for Padé-Hermite approximations
• A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
• The Big Mother of all Dualities: Möller Algorithm
• A Polynomial-Division-Based Algorithm for Computing Linear Recurrence Relations
• Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices
• Invariant Description of Linear, Time-Invariant Controllable Systems

This page was built for publication: Computing syzygies in finite dimension using fast linear algebra