NCF4 Class Reference

Non-commutative F4 Groebner-basis driver: builds a per-degree Macaulay matrix from overlaps and reduces it in bulk. More...

#include <NCF4.hpp>

Inheritance diagram for NCF4:

Classes
struct	PreRow
	Symbolic description of one row before it is materialised in the matrix: a left * (something) * right triple. More...
struct	Row
	A materialised row of the Macaulay matrix: parallel coefficient and monomial arrays. More...
struct	Column
	A column of the Macaulay matrix: the monomial that names it plus the row currently acting as its pivot (or -1 if none). More...
struct	NCF4Stats
	Per-thread counters tracking how much work the F4 reduction did. More...

Public Member Functions
	NCF4 (const FreeAlgebra &A, const ConstPolyList &input, int hardDegreeLimit, int strategy, int numThreads)
	~NCF4 ()
const FreeAlgebra &	freeAlgebra () const
const PolyList &	currentValue () const
void	compute (int softDegreeLimit)
void	displayF4Matrix (std::ostream &o) const
void	displayFullF4Matrix (std::ostream &o) const
void	displayF4MatrixSize (std::ostream &o) const

Private Types
enum	PreRowType { ReducerPreRow , OverlapPreRow , PreviousReducerPreRow }
using	ColumnsVector = std::vector<Column>
using	RowsVector = std::vector<Row,gc_allocator<Row>>
using	PreRowFeeder = mtbb::feeder<PreRow>
using	MonomialHash = mtbb::unordered_map<Word,std::pair<int,int>,MonomHash,MonomHashEqual>

Private Member Functions
void	process (const std::deque< Overlap > &overlapsToProcess)
void	buildF4Matrix (const std::deque< Overlap > &overlapsToProcess)
void	parallelBuildF4Matrix (const std::deque< Overlap > &overlapsToProcess)
void	labelAndSortF4Matrix ()
void	reduceF4Matrix ()
void	parallelReduceF4Matrix ()
Word	createOverlapLeadWord (const Overlap &o)
auto	isOverlapNecessary (const Overlap &o) -> bool
auto	checkOldOverlaps (Word &newLeadWord) -> void
void	matrixReset ()
void	addToGroebnerBasis (Poly *toAdd)
void	updateOverlaps (const Poly *toAdd)
auto	overlapHeft (Overlap o) const -> int
auto	insertNewOverlaps (std::vector< Overlap > &newOverlaps) -> void
void	reducedRowToPoly (Poly *result, const RowsVector &rows, const ColumnsVector &cols, int i) const
PolyList	newGBelements () const
void	processPreRow (PreRow r, RowsVector &rowsVector, MemoryBlock &memoryBlock, PreRowFeeder *feeder)
void	processPreRow (PreRow r, RowsVector &rowsVector)
void	processWordInPreRow (Word &w, PreRowFeeder *feeder)
void	preRowsFromOverlap (const Overlap &o)
std::pair< bool, PreRow >	findDivisor (Word w)
void	autoreduceByLastElement ()
ring_elem	getCoeffOfMonom (const Poly &f, const Monom &m) const
template<typename LockType>
void	generalReduceF4Row (int index, int first, int firstcol, NCF4Stats &ncF4Stats, ElementArray &dense, bool updateColumnIndex, LockType &lock)
void	reduceF4Row (int index, int first, int firstcol, NCF4Stats &ncF4Stats, ElementArray &dense)
void	parallelReduceF4Row (int index, int first, int firstcol, NCF4Stats &ncF4Stats, ElementArray &dense, mtbb::queuing_mutex &lock)
std::pair< bool, int >	findPreviousReducerPrefix (const Word &w)
std::pair< bool, int >	findPreviousReducerSuffix (const Word &w)
void	clearRows (RowsVector &rowsVector)
void	processPreviousF4Matrix ()

Private Attributes
const FreeAlgebra &	mFreeAlgebra
const ConstPolyList	mInput
WordTable	mWordTable
OverlapTable	mOverlapTable
PolyList	mGroebner
bool	mIsGraded
MemoryBlock	mMonomialSpace
MemoryBlock	mPreviousMonomialSpace
MonomEq	mMonomEq
MonomHashEqual	mMonomHashEqual
MonomHash	mMonomHash
MonomialHash	mColumnMonomials
MonomialHash	mPreviousColumnMonomials
std::vector< PreRow >	mReducersTodo
std::vector< PreRow >	mOverlapsTodo
ColumnsVector	mColumns
ColumnsVector	mPreviousColumns
RowsVector	mRows
RowsVector	mPreviousRows
RowsVector	mOverlaps
int	mFirstOverlap
const VectorArithmetic *	mVectorArithmetic
int	mNumThreads
bool	mIsParallel
mtbb::task_arena	mScheduler
std::vector< MemoryBlock * >	mMemoryBlocks
std::vector< MemoryBlock * >	mPreviousMemoryBlocks
mtbb::queuing_mutex	mColumnMutex

Additional Inherited Members
Static Public Member Functions inherited from our_new_delete
static void *	operator new (size_t size)
static void *	operator new[] (size_t size)
static void	operator delete (void *obj)
static void	operator delete[] (void *obj)
static void *	operator new (size_t size, void *existing_memory)
static void *	operator new[] (size_t size, void *existing_memory)
static void	operator delete (void *obj, void *existing_memory)
static void	operator delete[] (void *obj, void *existing_memory)

Detailed Description

Non-commutative F4 Groebner-basis driver: builds a per-degree Macaulay matrix from overlaps and reduces it in bulk.

Note

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

Replaces the one-overlap-at-a-time NCGroebner loop with the F4 pattern. Each degree, the driver pulls every overlap of that degree from mOverlapTable, builds rows from the overlaps plus their tail-reducers (drawn from mGroebner, the original mInput, or mRows — the three PreRowType flavours), labels the columns by the distinct monomials seen, sorts them under the non-commutative monomial order, then echelon-reduces via mVectorArithmetic. Echelon rows whose leading column is new become new GB elements and feed the next degree's overlaps.

Monomial / word storage is owned by an internal MemoryBlock pair (mMonomialSpace / mPreviousMonomialSpace); divisibility uses mWordTable. TBB scaffolding (PreRowFeeder, mScheduler) is wired up but the parallel build path is currently dormant.

Definition at line 103 of file NCF4.hpp.

---

The documentation for this class was generated from the following files:

• Macaulay2/e/NCAlgebras/NCF4.hpp
• Macaulay2/e/NCAlgebras/NCF4.cpp