Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices

DOI10.1145/1993886.1993908zbMath1323.68596OpenAlexW2166998199MaRDI QIDQ5254161

Chenqi Mou, Jean-Charles Faugère

Publication date: 9 June 2015

Published in: Proceedings of the 36th international symposium on Symbolic and algebraic computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1993886.1993908

zbMATH Keywords

Gröbner basessparse matrixFGLM algorithmWiedemann algorithmzero-dimensional idealsBMS algorithmchange of ordering

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Related Items (13)

Polynomial-division-based algorithms for computing linear recurrence relations ⋮ Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences ⋮ The point decomposition problem over hyperelliptic curves, Toward efficient computation of discrete logarithms in even characteristic ⋮ Solving rank-constrained semidefinite programs in exact arithmetic ⋮ On the complexity of the generalized MinRank problem ⋮ In-depth comparison of the Berlekamp-Massey-Sakata and the Scalar-FGLM algorithms: the adaptive variants ⋮ Elimination ideal and bivariate resultant over finite fields ⋮ Computing syzygies in finite dimension using fast linear algebra ⋮ Real root finding for determinants of linear matrices ⋮ Sparse FGLM algorithms ⋮ Using symmetries in the index calculus for elliptic curves discrete logarithm ⋮ Guessing Gröbner bases of structured ideals of relations of sequences ⋮ A fast algorithm for multivariate Hermite interpolation

Uses Software

• FGb
• Magma
• SINGULAR

This page was built for publication: Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices