ApCoCoALib:FGLM

User documentation for files FGLM.C and FGLM.H

About

Let K be a field, P = K[x_1, ..., x_n], I a zero-dimensional Ideal in P and G a Groebner basis of I w.r.t. a term ordering. The FGLM algorithm lets you convert G into a Groebner basis G' w.r.t. to another term ordering.

Currently there is one function to apply the FGLM algorithm to a given Groebner basis:

 FGLMBasisConversion(NewGB, OldGB, NewOrdering, SolveMethod)

OldGB and NewGB are std::vector objects. OldGB must be a list of Groebner basis polynomials, NewTermOrdering is the target term ordering. NewGB will contain the computed Groebner basis polynomials w.r.t. NewTermOrdering. Note: The elements of NewGB will belong to a different polynomial ring than the elements of OldGB! The parameter SolveMethod indicates which algorithm will be used for the internal solving of linear equation systems. See LESystemSolver.txt for possible choices of this parameter.

Maintainer documentation for files FGLM.C and FGLM.C

The implementation of the FGLM algorithm is a straight forward implementation. The linear independency checks during the main loop require some book keeping to make it possible to create linear equation systems in matrix form. For this book keeping, an object "MatrixMap" of type map<PPMonoidElem, struct MatrixMapEntry> and a structure "MatrixMapEntry" are used. In each loop, the coefficients of the monomials of the remainders that have been computed in the loops before are used as matrix components. These coefficients are stored in the MatrixMap object alongside with a corresponding variable index that is used to find the correct position within the matrix. The coefficients of the monomials of the remainder computed in the current loop influence the right hand side of the linear equation system. The right hand side components are also stored in the MatrixMap object. After a matrix M and a vector b are created out of the information in the MatrixMap object and M*x = b is solved, the right hand side components are reset to zero. If the current remainders are not linearly dependent, the MatrixMap object needs to be updated.

Bugs, Shortcomings and other ideas

The bottlenecks detected so far regarding computation speed are the LESystemSolver calls and the extension of the QBGenerator if no new basis polynomial is found during the main loop. The linear independency checks also make it necessary to create a lot of different (dense) matrices during the main loop.