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

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