f4.hpp File Reference

F4GB — the inner-loop Faugère F4 Groebner-basis algorithm. More...

#include "interface/m2-types.h"
#include "f4-types.hpp"
#include "f4/moninfo.hpp"
#include "f4/f4-spairs.hpp"
#include "interface/computation.h"
#include "m2tbb.hpp"
#include "memblock.hpp"
#include "monhashtable.hpp"
#include "newdelete.hpp"
#include "MemoryBlock.hpp"
#include <ctime>

Go to the source code of this file.

Classes
class	F4GB
	Commutative F4 Groebner-basis driver: degree-by-degree Macaulay matrix construction plus row-reduction over a coefficient ring. More...
struct	F4GB::MacaulayMatrixStats
	Per-degree counters describing the shape and density of the Macaulay matrix that F4GB just built. More...

Detailed Description

F4GB — the inner-loop Faugère F4 Groebner-basis algorithm.

Note

AI-generated documentation. Verify against the source before relying on it.

Declares F4GB, the (non-templated) core class implementing Faugere's linear-algebra GB algorithm. Each outer iteration picks the next degree from F4SPairSet mSPairSet, asks for the batch of S-pairs at that degree, computes their S-polynomials, collects every monomial appearing in those polynomials and the tail reducers (interned through MonomialHashTable<MonomialInfo> to assign column indices), builds a Macaulay matrix (coefficient_matrix *mat) whose rows are S-polynomials plus reducers and whose columns are the collected monomials in the chosen order, reduces it to row-echelon form (gauss_reduce, with an optional follow-up tail_reduce), and extracts as new basis elements those echelon rows whose leading column was previously unrepresented (is_new_GB_row / new_GB_elements / insert_gb_element). Members carry the current basis (gb_array mGroebnerBasis), the generators (gb_array mGenerators), the MonomialInfo* describing the packed-monomial encoding, and a MonomialLookupTable mLookupTable mapping (monom, Computations) to its GB index.

Coefficient-ring polymorphism is handled at runtime through const VectorArithmetic* mVectorArithmetic, not via template parameters — the long source-level comment listing "Template parameters include: coefficient ring arithmetic, packed_monomial, exponents, varpower_monomial, MonomialLookupTable" describes the would-be template surface but F4GB is monomorphic; the refactored gb-f4/ engine is the home of the templated-arithmetic version. When compiled WITH_TBB, an mtbb::task_arena mScheduler and mNumThreads field drive a parallel Gaussian-elimination path (mParallelGaussTime vs mSerialGaussTime). The top-level dispatcher f4-computation.hpp is where M2 user calls land before delegating here.

See also

f4-computation.hpp

f4-spairs.hpp

moninfo.hpp

Definition in file f4.hpp.