NCF4.hpp File Reference

NCF4 — non-commutative F4 Gröbner-basis driver building a per-degree Macaulay matrix. More...

#include "m2tbb.hpp"
#include "NCAlgebras/FreeMonoid.hpp"
#include "MemoryBlock.hpp"
#include "NCAlgebras/Range.hpp"
#include "NCAlgebras/Word.hpp"
#include "NCAlgebras/OverlapTable.hpp"
#include "NCAlgebras/WordTable.hpp"
#include "NCAlgebras/SuffixTree.hpp"
#include "NCAlgebras/FreeAlgebra.hpp"
#include "VectorArithmetic.hpp"
#include "Polynomial.hpp"
#include "newdelete.hpp"
#include <deque>
#include <iosfwd>
#include <map>
#include <unordered_map>
#include <tuple>
#include <utility>
#include <vector>

Go to the source code of this file.

Classes
class	NCF4
	Non-commutative F4 Groebner-basis driver: builds a per-degree Macaulay matrix from overlaps and reduces it in bulk. More...
struct	NCF4::PreRow
	Symbolic description of one row before it is materialised in the matrix: a left * (something) * right triple. More...
struct	NCF4::Row
	A materialised row of the Macaulay matrix: parallel coefficient and monomial arrays. More...
struct	NCF4::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	NCF4::NCF4Stats
	Per-thread counters tracking how much work the F4 reduction did. More...

Detailed Description

NCF4 — non-commutative F4 Gröbner-basis driver building a per-degree Macaulay matrix.

Note

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

Declares the F4-style alternative to the one-overlap-at-a-time NCGroebner reduction loop. Each iteration collects every overlap of the current degree from OverlapTable mOverlapTable, assembles a Macaulay matrix whose rows are the overlap polynomials plus their tail-reducers (drawn from mGroebner, the original inputs mInput, and previously-built reducer rows — corresponding to the three PreRowType flavours ReducerPreRow / OverlapPreRow / PreviousReducerPreRow) and whose columns are the distinct monomials seen in any row sorted by the non-commutative monomial order, then row-reduces the whole matrix via mVectorArithmetic. Echelon rows whose leading column was not already a basis-element leading column become new GB elements (added to mGroebner); their overlaps feed the next degree. Two RowsVector matrices (mRows/mPreviousRows) and a third mOverlaps track current vs prior cohorts so PreviousReducerPreRow references can be resolved without rebuilding from scratch.

Monomial / word storage is owned by an internal pair of MemoryBlocks (mMonomialSpace / mPreviousMonomialSpace). Word divisibility uses the live WordTable (the commented-out SuffixTree mWordTable; alternative remains available as a swap-in experiment). m2tbb.hpp is included for the column-monomial mtbb::unordered_map MonomialHash, the PreRowFeeder = mtbb::feeder<PreRow> worker queue, and a held mtbb::task_arena mScheduler ready for the parallel matrix-build path; the explicit comment "only used in parallelBuildF4Matrix, which is currently not used" flags that the parallel build is dormant scaffolding, and the concurrent_vector row / column container choices are commented out in favour of std::vector for now.

See also

NCGroebner.hpp

FreeAlgebra.hpp

OverlapTable.hpp

WordTable.hpp

SuffixTree.hpp

VectorArithmetic.hpp

Definition in file NCF4.hpp.