ApCoCoALib:PPMonoidModSquares

From ApCoCoAWiki

User documentation for files PPMonoidModSquares.C and PPMonoidModSquares.H

About

These files contain a PPMonoid for 0/1 problems. This PPMonoid computes in T^n/(x_i^2 - x_i), therefore for each indeterminate x we have x^2 = x. If you are only looking for solutions in {0,1} you can use this PPMonoid instead of a default PPMonoid (e.g. PPMonoidEnv).

The result is then the same, as if you would have added the polynomial x^2 - x for each indeterminate to your system, but the computation is faster.

Another issue is, that 'termorderings' are not really termorderings here. for example we have 1 < x but x*1 = x = x^x = x*x and therefor not x*1 < x*x. In the same way there are natural problems with respect to graduations


The interface to the PPMonoid works as follows:

CoCoA::PPMonoid NewPPMonoidModSquares(const std::vector<CoCoA::symbol>& IndetNames,const FastSquareFreeOrderings ord = Lex );

This method creates a new PPMonoidModSquares with the given symbols and a term ordering (either Lex,DegRevLex or DegLex)


Maintainer documentation for files PPMonoidModSquares.C and PPMonoidModSquares.H

The method ComputeDivMask is strange and has to be changed in the future most likely if CoCoA::DivMaskRule is changed. Also there should be more constructurs / NewPPMonoidModSquares functions implemented to allow more options there. Also the support for graduations is minimal. Only the std-Deg is computed! This might be problematic.

Bugs, Shortcomings and other ideas

Currently only three termorderings are supported. There is some room for more term orderings implemented in the same efficient way. Modulo x^2 -x a lot of term orderings are isomorphic, although the representing matrices differ. also a lex term ordering with z<x<y (or other permutations or similar variations of DegLex and DegRevLex) can be implemented in the same way. Also the implementation can be speed up, by using bit-fields or vector (for mac os x, using the accelerate framework), especially if more than 64 indeterminates are used. Also there might be some bugs left and I do not know how a polynomial ring based on this PPMonoid reacts to algorithms like Buchberger-Moeller, FGLM or BBasis.