#include <cmr/series_parallel.h>
#include "env_internal.h"
#include "hashtable.h"
#include "sort.h"
#include "listmatrix.h"
#include <stdint.h>
#include <time.h>

Classes
struct	ElementData
	Element specific data for the enumeration of 3-separations. More...

Enumerations
enum	ElementType { ELEMENT_TYPE_NONE , ELEMENT_TYPE_1 , ELEMENT_TYPE_2 , ELEMENT_TYPE_3 , ELEMENT_TYPE_NORMAL , REMOVED = 0 , ZERO = 1 , BLOCK = 2 , OTHER = 3 }

Functions
CMR_ERROR	CMRspStatsInit (CMR_SP_STATISTICS *stats)
	Initializes all statistics for series-parallel computations. More...

CMR_ERROR	CMRspStatsPrint (FILE stream, CMR_SP_STATISTICS stats, const char *prefix)
	Prints statistics for series-parallel computations. More...

char *	CMRspReductionString (CMR_SP_REDUCTION reduction, char *buffer)

static void	unlinkNonzero (ListMat8Nonzero *nonzero)
	Removes the given nonzero from the linked-list representation. More...

static CMR_ERROR	createElementData (CMR cmr, ElementData *pelementData, size_t size)
	Allocates and initializes element data (on the stack). More...

static CMR_ERROR	createHashVector (CMR cmr, long long *phashVector, size_t size)

static CMR_ERROR	calcNonzeroCountHashFromMatrix (CMR cmr, CMR_CHRMAT matrix, ListMat8 listmatrix, ElementData rowData, ElementData columnData, long long hashVector)
	Scan the matrix to compute the number of nonzeros and the hash of each row and each column. More...

static CMR_ERROR	calcBinaryHashFromListMatrix (CMR cmr, ListMat8 listmatrix, ElementData rowData, ElementData columnData, long long *hashVector)
	Scan the matrix to compute the number of nonzeros and the hash of each row and each column. More...

static CMR_ERROR	initializeQueueHashtableFromMatrix (CMR cmr, CMR_LISTHASHTABLE hashtable, ListMat8Element listmatrixElements, ElementData data, size_t sizeData, CMR_ELEMENT queue, size_t pqueueEnd, bool isRow)
	Scans the matrix initially in order to add all rows or columns either to the queue or to the hashtable. More...

static CMR_ERROR	initializeQueueHashtableFromListMatrix (CMR cmr, CMR_LISTHASHTABLE hashtable, ListMat8 listmatrix, ElementData data, CMR_ELEMENT queue, size_t pqueueEnd, bool isRow)
	Adds all rows or columns of the list representation of the matrix either to the queue or to the hashtable. More...

static size_t	findCopy (ListMat8Element listData, ElementData data, CMR_LISTHASHTABLE *hashtable, size_t index, bool isRow, bool support)
	Checks whether the row/column at `index` is a (negated) copy of a row/column stored in the hashtable. More...

static CMR_ERROR	processNonzero (CMR cmr, CMR_LISTHASHTABLE hashtable, long long hashChange, size_t index, ListMat8Element indexListData, ElementData indexData, CMR_ELEMENT queue, size_t pqueueEnd, size_t queueMemory, bool isRow)
	Processes the deletion of a nonzero from the linked-list representation. More...

static CMR_ERROR	reduceListMatrix (CMR cmr, ListMat8 listmatrix, ElementData rowData, ElementData columnData, CMR_LISTHASHTABLE rowHashtable, CMR_LISTHASHTABLE columnHashtable, long long entryToHash, CMR_ELEMENT queue, size_t pqueueStart, size_t pqueueEnd, size_t queueMemory, CMR_SP_REDUCTION reductions, size_t maxNumReductions, size_t pnumReductions, size_t pnumRowReductions, size_t pnumColumnReductions)
	Carry out the actual reduction algorithm after all data structures are initialized. More...

static CMR_ERROR	extractNonbinarySubmatrix (CMR cmr, ListMat8 listmatrix, ElementData rowData, ElementData columnData, CMR_LISTHASHTABLE rowHashtable, CMR_LISTHASHTABLE columnHashtable, CMR_ELEMENT queue, size_t pqueueStart, size_t pqueueEnd, size_t queueMemory, CMR_SUBMAT *pviolatorSubmatrix)
	Try to find an \( M_2 \)-submatrix for a ternary SP-reduced matrix in list representation. More...

static CMR_ERROR	breadthFirstSearch (CMR cmr, int currentBFS, ListMat8Element rowListData, ListMat8Element columnListData, ElementData rowData, ElementData columnData, CMR_ELEMENT queue, size_t queueMemory, CMR_ELEMENT sources, size_t numSources, CMR_ELEMENT targets, size_t numTargets, size_t pfoundTarget, size_t pnumEdges)

static CMR_ERROR	extractRemainingSubmatrix (CMR cmr, CMR_CHRMAT matrix, size_t numRowReductions, size_t numColumnReductions, ListMat8 listmatrix, CMR_SUBMAT *preducedSubmatrix)
	Extract remaining submatrix. More...

static CMR_ERROR	createFullRemainingMatrix (CMR cmr, CMR_CHRMAT matrix, CMR_SUBMAT **preducedSubmatrix)
	Create full matrix as remaining submatrix. More...

static CMR_ERROR	extractWheelSubmatrix (CMR cmr, ListMat8 listmatrix, ElementData rowData, ElementData columnData, CMR_ELEMENT queue, size_t queueMemory, size_t numReducedRows, size_t numReducedColumns, CMR_SUBMAT pwheelSubmatrix, CMR_SEPA *pseparation)
	Searches for a wheel-submatrix; may also encounter and return a 2-separation. More...

static CMR_ERROR	decomposeBinarySeriesParallel (CMR cmr, CMR_CHRMAT matrix, CMR_SP_REDUCTION reductions, size_t maxNumReductions, size_t pnumReductions, CMR_SUBMAT preducedSubmatrix, CMR_SUBMAT pviolatorSubmatrix, CMR_SEPA *pseparation, CMR_SP_STATISTICS stats, double timeLimit)

CMR_ERROR	CMRspTestBinary (CMR cmr, CMR_CHRMAT matrix, bool pisSeriesParallel, CMR_SP_REDUCTION reductions, size_t pnumReductions, CMR_SUBMAT preducedSubmatrix, CMR_SUBMAT pviolatorSubmatrix, CMR_SP_STATISTICS stats, double timeLimit)
	Finds all series-parallel reductions for the binary `matrix` \( A \). More...

CMR_ERROR	CMRspDecomposeBinary (CMR cmr, CMR_CHRMAT matrix, bool pisSeriesParallel, CMR_SP_REDUCTION reductions, size_t maxNumReductions, size_t pnumReductions, CMR_SUBMAT preducedSubmatrix, CMR_SUBMAT pviolatorSubmatrix, CMR_SEPA pseparation, CMR_SP_STATISTICS stats, double timeLimit)
	Finds all series-parallel reductions for the binary `matrix` \( A \). More...

static CMR_ERROR	decomposeTernarySeriesParallel (CMR cmr, CMR_CHRMAT matrix, CMR_SP_REDUCTION reductions, size_t maxNumReductions, size_t pnumReductions, CMR_SUBMAT preducedSubmatrix, CMR_SUBMAT pviolatorSubmatrix, CMR_SEPA *pseparation, CMR_SP_STATISTICS stats, double timeLimit)

CMR_ERROR	CMRspTestTernary (CMR cmr, CMR_CHRMAT matrix, bool pisSeriesParallel, CMR_SP_REDUCTION reductions, size_t pnumReductions, CMR_SUBMAT preducedSubmatrix, CMR_SUBMAT pviolatorSubmatrix, CMR_SP_STATISTICS stats, double timeLimit)
	Finds all series-parallel reductions for the ternary `matrix` \( A \). More...

CMR_ERROR	CMRspDecomposeTernary (CMR cmr, CMR_CHRMAT matrix, bool pisSeriesParallel, CMR_SP_REDUCTION reductions, size_t maxNumReductions, size_t pnumReductions, CMR_SUBMAT preducedSubmatrix, CMR_SUBMAT pviolatorSubmatrix, CMR_SEPA pseparation, CMR_SP_STATISTICS stats, double timeLimit)
	Finds all series-parallel reductions for the ternary `matrix` \( A \). More...

Variables
static char	seriesParallelStringBuffer [32]

Enumeration Type Documentation

◆ ElementType

enum ElementType

Enumerator
ELEMENT_TYPE_NONE	Row/column does not belong to the submatrix.
ELEMENT_TYPE_1	Row/column is a source/target of type 1.
ELEMENT_TYPE_2	Row/column is a source/target of type 2.
ELEMENT_TYPE_3	Row/column is a source/target of type 3.
ELEMENT_TYPE_NORMAL	Row/column belongs to the submatrix.
REMOVED
ZERO
BLOCK
OTHER

Function Documentation

◆ breadthFirstSearch()

static CMR_ERROR breadthFirstSearch	(	CMR *	cmr,
		int	currentBFS,
		ListMat8Element *	rowListData,
		ListMat8Element *	columnListData,
		ElementData *	rowData,
		ElementData *	columnData,
		CMR_ELEMENT *	queue,
		size_t	queueMemory,
		CMR_ELEMENT *	sources,
		size_t	numSources,
		CMR_ELEMENT *	targets,
		size_t	numTargets,
		size_t *	pfoundTarget,
		size_t *	pnumEdges
	)

static

Parameters

cmr	CMR environment.
currentBFS	Number of this execution of breadth-first search.
rowListData	Row data.
columnListData	Column data.
rowData	Row data.
columnData	Column data.
queue	Queue.
queueMemory	Memory for queue.
sources	Array of source nodes.
numSources	Number of source nodes.
targets	Array of target nodes.
numTargets	Number of target nodes.
pfoundTarget	Pointer for storing the index of the target node found.
pnumEdges	Pointer for storing the number of traversed edges.

◆ calcBinaryHashFromListMatrix()

static CMR_ERROR calcBinaryHashFromListMatrix	(	CMR *	cmr,
		ListMat8 *	listmatrix,
		ElementData *	rowData,
		ElementData *	columnData,
		long long *	hashVector
	)

static

Scan the matrix to compute the number of nonzeros and the hash of each row and each column.

Parameters

cmr	CMR environment.
listmatrix	List matrix.
rowData	Other row element data.
columnData	Other column element data.
hashVector	Hash vector.

◆ calcNonzeroCountHashFromMatrix()

static CMR_ERROR calcNonzeroCountHashFromMatrix	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		ListMat8 *	listmatrix,
		ElementData *	rowData,
		ElementData *	columnData,
		long long *	hashVector
	)

static

Scan the matrix to compute the number of nonzeros and the hash of each row and each column.

Parameters

cmr	CMR environment.
matrix	Matrix.
listmatrix	List matrix representation.
rowData	Other row element data.
columnData	Other column element data.
hashVector	Hash vector.

◆ CMRspDecomposeBinary()

CMR_ERROR CMRspDecomposeBinary	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisSeriesParallel,
		CMR_SP_REDUCTION *	reductions,
		size_t	maxNumReductions,
		size_t *	pnumReductions,
		CMR_SUBMAT **	preducedSubmatrix,
		CMR_SUBMAT **	pviolatorSubmatrix,
		CMR_SEPA **	pseparation,
		CMR_SP_STATISTICS *	stats,
		double	timeLimit
	)

Finds all series-parallel reductions for the binary matrix \( A \).

Let \( A \in \{0,1\}^{m \times n} \) with \( k \) nonzeros.

Denote by \( A' \) the (maximum) SP-reduced submatrix of \( A \). If premainingSubmatrix is not NULL, then the rows and columns of \( A' \) are stored.

If pviolatorSubmatrix is not NULL and matrix is not binary series-parallel, then a wheel-submatrix is stored (unless a 2-separation is found; see below). Note that the row/column indices refer to \( A \).

If pseparation is not NULL and during the search for a wheel-submatrix a 2-separation that does not correspond to an SP reduction is found then such a 2-separation is returned and the algorithm terminates without returning a wheel-submatrix. Note that *pseparation then contains row/column indices relative to \( A' \).

The running time is \( \mathcal{O} (m + n + k) \) assuming no hashtable collisions.

Parameters

cmr	CMR environment.
matrix	Sparse char matrix.
pisSeriesParallel	Pointer for storing the result.
reductions	Array for storing the SP-reductions. If not `NULL`, it must have capacity at least number of rows + number of columns.
maxNumReductions	Maximum number of SP-reductions. Stops when this would be exceeded.
pnumReductions	Pointer for storing the number of SP-reductions; stores `SIZE_MAX` if **< `maxNumReductions` was exceeded.
preducedSubmatrix	Pointer for storing the SP-reduced submatrix (may be `NULL`).
pviolatorSubmatrix	Pointer for storing a wheel-submatrix (may be `NULL`).
pseparation	Pointer for storing a 2-separation (may be `NULL`).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRspDecomposeTernary()

CMR_ERROR CMRspDecomposeTernary	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisSeriesParallel,
		CMR_SP_REDUCTION *	reductions,
		size_t	maxNumReductions,
		size_t *	pnumReductions,
		CMR_SUBMAT **	preducedSubmatrix,
		CMR_SUBMAT **	pviolatorSubmatrix,
		CMR_SEPA **	pseparation,
		CMR_SP_STATISTICS *	stats,
		double	timeLimit
	)

Finds all series-parallel reductions for the ternary matrix \( A \).

Let \( A \in \{-1,0,+1\}^{m \times n} \) with \( k \) nonzeros.

Denote by \( A' \) the (maximum) SP-reduced submatrix of \( A \). If premainingSubmatrix is not NULL, then the rows and columns of \( A' \) are stored.

If pviolatorSubmatrix is not NULL and matrix is not ternary series-parallel, then a signed wheel- or \( M_2 \)-submatrix is stored (unless a 2-separation is found; see below). Note that the row/column indices refer to \( A \).

If pseparation is not NULL and during the search for a signed wheel-submatrix a 2-separation that does not correspond to an SP reduction is found then such a 2-separation is returned and the algorithm terminates without returning a signed wheel- or \( M_2 \)-submatrix. Note that *pseparation then contains row/column indices relative to \( A' \).

The running time is \( \mathcal{O} (m + n + k) \) assuming no hashtable collisions.

See also: CMRsubmatZoomSubmat() for turning *pviolatorSubmatrix into a submatrix of the SP-reduced submatrix.

Parameters

cmr	CMR environment.
matrix	Sparse char matrix.
pisSeriesParallel	Pointer for storing the result.
reductions	Array for storing the SP-reductions. If not `NULL`, it must have capacity at least number of rows + number of columns.
maxNumReductions	Maximum number of SP-reductions. Stops when this would be exceeded.
pnumReductions	Pointer for storing the number of SP-reductions; stores `SIZE_MAX` if **< `maxNumReductions` was exceeded.
preducedSubmatrix	Pointer for storing the SP-reduced submatrix (may be `NULL`).
pviolatorSubmatrix	Pointer for storing a signed wheel- or \( M_2 \)-submatrix (may be `NULL`).
pseparation	Pointer for storing a 2-separation (may be `NULL`).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRspReductionString()

char* CMRspReductionString	(	CMR_SP_REDUCTION	reduction,
		char *	buffer
	)

Prints the series-parallel reduction to buffer.

Parameters

reduction	Series-parallel reduction.
buffer	Buffer to write to. If `NULL`, a static one is used which will be overwritten in the next call. Otherwise, it must hold at least 51 bytes.

◆ CMRspStatsInit()

CMR_ERROR CMRspStatsInit ( CMR_SP_STATISTICS * stats )

Initializes all statistics for series-parallel computations.

Parameters

stats Pointer to statistics.

◆ CMRspStatsPrint()

CMR_ERROR CMRspStatsPrint	(	FILE *	stream,
		CMR_SP_STATISTICS *	stats,
		const char *	prefix
	)

Prints statistics for series-parallel computations.

Parameters

stream	File stream to print to.
stats	Pointer to statistics.
prefix	Prefix string to prepend to each printed line (may be `NULL`).

◆ CMRspTestBinary()

CMR_ERROR CMRspTestBinary	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisSeriesParallel,
		CMR_SP_REDUCTION *	reductions,
		size_t *	pnumReductions,
		CMR_SUBMAT **	preducedSubmatrix,
		CMR_SUBMAT **	pviolatorSubmatrix,
		CMR_SP_STATISTICS *	stats,
		double	timeLimit
	)

Finds all series-parallel reductions for the binary matrix \( A \).

Let \( A \in \{-1,0,1\}^{m \times n} \) with \( k \) nonzeros.

Denote by \( A' \) the (maximum) SP-reduced submatrix of \( A \). If premainingSubmatrix is not NULL, then the rows and columns of \( A' \) are stored.

If pviolatorSubmatrix is not NULL and matrix is not binary series-parallel, then a wheel-submatrix is stored.

The running time is \( \mathcal{O} (m + n + k) \) assuming no hashtable collisions.

Parameters

cmr	CMR environment.
matrix	Sparse char matrix.
pisSeriesParallel	Pointer for storing the result.
reductions	Array for storing the SP-reductions. If not `NULL`, it must have capacity at least number of rows + number of columns.
pnumReductions	Pointer for storing the number of SP-reductions.
preducedSubmatrix	Pointer for storing the SP-reduced submatrix (may be `NULL`).
pviolatorSubmatrix	Pointer for storing a wheel-submatrix (may be `NULL`).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ CMRspTestTernary()

CMR_ERROR CMRspTestTernary	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisSeriesParallel,
		CMR_SP_REDUCTION *	reductions,
		size_t *	pnumReductions,
		CMR_SUBMAT **	preducedSubmatrix,
		CMR_SUBMAT **	pviolatorSubmatrix,
		CMR_SP_STATISTICS *	stats,
		double	timeLimit
	)

Finds all series-parallel reductions for the ternary matrix \( A \).

Let \( A \in \{-1,0,+1\}^{m \times n} \) with \( k \) nonzeros.

Denote by \( A' \) the (maximum) SP-reduced submatrix of \( A \). If premainingSubmatrix is not NULL, then the rows and columns of \( A' \) are stored.

If pviolatorSubmatrix is not NULL and matrix is not ternary series-parallel, then a signed wheel- or \( M_2 \)-submatrix is stored.

The running time is \( \mathcal{O} (m + n + k) \) assuming no hashtable collisions.

Parameters

cmr	CMR environment.
matrix	Sparse char matrix.
pisSeriesParallel	Pointer for storing the result.
reductions	Array for storing the SP-reductions. If not `NULL`, it must have capacity at least number of rows + number of columns.
pnumReductions	Pointer for storing the number of SP-reductions.
preducedSubmatrix	Pointer for storing the SP-reduced submatrix (may be `NULL`).
pviolatorSubmatrix	Pointer for storing a signed wheel- or \( M_2 \)-submatrix (may be `NULL`).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ createElementData()

static CMR_ERROR createElementData	(	CMR *	cmr,
		ElementData **	pelementData,
		size_t	size
	)

static

Allocates and initializes element data (on the stack).

Parameters

cmr	CMR environment.
pelementData	Pointer for storing the element data.
size	Number of elements.

◆ createFullRemainingMatrix()

static CMR_ERROR createFullRemainingMatrix	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_SUBMAT **	preducedSubmatrix
	)

static

Create full matrix as remaining submatrix.

Parameters

cmr	CMR environment.
matrix	Matrix.
preducedSubmatrix	Pointer for storing the reduced submatrix.

◆ createHashVector()

static CMR_ERROR createHashVector	(	CMR *	cmr,
		long long **	phashVector,
		size_t	size
	)

static

Parameters

cmr	CMR environment.
phashVector	Pointer for storing the hash vector.
size	Size of hash vector.

◆ decomposeBinarySeriesParallel()

static CMR_ERROR decomposeBinarySeriesParallel	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_SP_REDUCTION *	reductions,
		size_t	maxNumReductions,
		size_t *	pnumReductions,
		CMR_SUBMAT **	preducedSubmatrix,
		CMR_SUBMAT **	pviolatorSubmatrix,
		CMR_SEPA **	pseparation,
		CMR_SP_STATISTICS *	stats,
		double	timeLimit
	)

static

Parameters

cmr	CMR environment.
matrix	Sparse char matrix.
reductions	Array for storing the SP-reductions. Must have capacity at least number of **< rows + number of columns.
maxNumReductions	Maximum number of SP-reductions. Stops when this would be exceeded.
pnumReductions	Pointer for storing the number of SP-reductions.
preducedSubmatrix	Pointer for storing the SP-reduced submatrix (may be `NULL`).
pviolatorSubmatrix	Pointer for storing a wheel-submatrix (may be `NULL`).
pseparation	Pointer for storing a 2-separation (may be `NULL`).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ decomposeTernarySeriesParallel()

static CMR_ERROR decomposeTernarySeriesParallel	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_SP_REDUCTION *	reductions,
		size_t	maxNumReductions,
		size_t *	pnumReductions,
		CMR_SUBMAT **	preducedSubmatrix,
		CMR_SUBMAT **	pviolatorSubmatrix,
		CMR_SEPA **	pseparation,
		CMR_SP_STATISTICS *	stats,
		double	timeLimit
	)

static

Parameters

cmr	CMR environment.
matrix	Sparse char matrix.
reductions	Array for storing the SP-reductions. Must have capacity at least number of **< rows + number of columns.
maxNumReductions	Maximum number of SP-reductions. Stops when this would be exceeded.
pnumReductions	Pointer for storing the number of SP-reductions.
preducedSubmatrix	Pointer for storing the SP-reduced submatrix (may be `NULL`).
pviolatorSubmatrix	Pointer for storing a wheel-submatrix (may be `NULL`).
pseparation	Pointer for storing a 2-separation (may be `NULL`).
stats	Pointer to statistics (may be `NULL`).
timeLimit	Time limit to impose.

◆ extractNonbinarySubmatrix()

static CMR_ERROR extractNonbinarySubmatrix	(	CMR *	cmr,
		ListMat8 *	listmatrix,
		ElementData *	rowData,
		ElementData *	columnData,
		CMR_LISTHASHTABLE *	rowHashtable,
		CMR_LISTHASHTABLE *	columnHashtable,
		CMR_ELEMENT *	queue,
		size_t *	pqueueStart,
		size_t *	pqueueEnd,
		size_t	queueMemory,
		CMR_SUBMAT **	pviolatorSubmatrix
	)

static

Try to find an \( M_2 \)-submatrix for a ternary SP-reduced matrix in list representation.

Parameters

cmr	CMR environment.
listmatrix	List matrix.
rowData	Row data.
columnData	Column data.
rowHashtable	Row hashtable.
columnHashtable	Column hashtable.
queue	Queue.
pqueueStart	Pointer to start of queue.
pqueueEnd	Pointer to end of queue.
queueMemory	Memory allocated for queue.
pviolatorSubmatrix	Pointer for storing the submatrix if an \( M_2 \)-submatrix is found.

◆ extractRemainingSubmatrix()

static CMR_ERROR extractRemainingSubmatrix	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		size_t	numRowReductions,
		size_t	numColumnReductions,
		ListMat8 *	listmatrix,
		CMR_SUBMAT **	preducedSubmatrix
	)

static

Extract remaining submatrix.

Parameters

cmr	CMR environment.
matrix	Matrix.
numRowReductions	Number of row SP reductions.
numColumnReductions	Number of column SP reductions.
listmatrix	List matrix.
preducedSubmatrix	Pointer for storing the reduced submatrix.

◆ extractWheelSubmatrix()

static CMR_ERROR extractWheelSubmatrix	(	CMR *	cmr,
		ListMat8 *	listmatrix,
		ElementData *	rowData,
		ElementData *	columnData,
		CMR_ELEMENT *	queue,
		size_t	queueMemory,
		size_t	numReducedRows,
		size_t	numReducedColumns,
		CMR_SUBMAT **	pwheelSubmatrix,
		CMR_SEPA **	pseparation
	)

static

Searches for a wheel-submatrix; may also encounter and return a 2-separation.

Parameters

cmr	CMR environment.
listmatrix	List matrix.
rowData	Row element data.
columnData	Column element data.
queue	Queue memory.
queueMemory	Size of `queue`.
numReducedRows	Number of rows in reduced matrix.
numReducedColumns	Number of columns in reduced matrix.
pwheelSubmatrix	Pointer for storing the wheel submatrix (may be `NULL`).
pseparation	Pointer for storing a 2-separation (may be `NULL`).

◆ findCopy()

static size_t findCopy	(	ListMat8Element *	listData,
		ElementData *	data,
		CMR_LISTHASHTABLE *	hashtable,
		size_t	index,
		bool	isRow,
		bool	support
	)

static

Checks whether the row/column at index is a (negated) copy of a row/column stored in the hashtable.

Compares the actual vectors by traversing the linked-list representation.

Parameters

listData	Row/column list data.
data	Other row/column data.
hashtable	Row/column hashtable.
index	Index in `data`.
isRow	Whether we are dealing with rows.
support	Whether only the support of the vector matters.

◆ initializeQueueHashtableFromListMatrix()

static CMR_ERROR initializeQueueHashtableFromListMatrix	(	CMR *	cmr,
		CMR_LISTHASHTABLE *	hashtable,
		ListMat8 *	listmatrix,
		ElementData *	data,
		CMR_ELEMENT *	queue,
		size_t *	pqueueEnd,
		bool	isRow
	)

static

Adds all rows or columns of the list representation of the matrix either to the queue or to the hashtable.

Parameters

cmr	CMR environment.
hashtable	Row or column hashtable.
listmatrix	List matrix.
data	Other row/column data array.
queue	Queue.
pqueueEnd	Pointer to end of queue.
isRow	Whether we are deadling with rows.

◆ initializeQueueHashtableFromMatrix()

static CMR_ERROR initializeQueueHashtableFromMatrix	(	CMR *	cmr,
		CMR_LISTHASHTABLE *	hashtable,
		ListMat8Element *	listmatrixElements,
		ElementData *	data,
		size_t	sizeData,
		CMR_ELEMENT *	queue,
		size_t *	pqueueEnd,
		bool	isRow
	)

static

Scans the matrix initially in order to add all rows or columns either to the queue or to the hashtable.

Parameters

cmr	CMR environment.
hashtable	Row or column hashtable.
listmatrixElements	Row or column list matrix elements.
data	Other row/column data.
sizeData	Length of `ListMatrixElements` and `data`.
queue	Queue.
pqueueEnd	Pointer to end of queue.
isRow	Whether we are deadling with rows.

◆ processNonzero()

static CMR_ERROR processNonzero	(	CMR *	cmr,
		CMR_LISTHASHTABLE *	hashtable,
		long long	hashChange,
		size_t	index,
		ListMat8Element *	indexListData,
		ElementData *	indexData,
		CMR_ELEMENT *	queue,
		size_t *	pqueueEnd,
		size_t	queueMemory,
		bool	isRow
	)

static

Processes the deletion of a nonzero from the linked-list representation.

Parameters

cmr	CMR environment.
hashtable	Row/column hashtable.
hashChange	Modification of the hash value.
index	Index of row/column.
indexListData	Row/column list data.
indexData	Other row/column data.
queue	Queue.
pqueueEnd	Pointer to end of queue.
queueMemory	Memory allocated for queue.
isRow	Whether we are dealing with rows.

◆ reduceListMatrix()

static CMR_ERROR reduceListMatrix	(	CMR *	cmr,
		ListMat8 *	listmatrix,
		ElementData *	rowData,
		ElementData *	columnData,
		CMR_LISTHASHTABLE *	rowHashtable,
		CMR_LISTHASHTABLE *	columnHashtable,
		long long *	entryToHash,
		CMR_ELEMENT *	queue,
		size_t *	pqueueStart,
		size_t *	pqueueEnd,
		size_t	queueMemory,
		CMR_SP_REDUCTION *	reductions,
		size_t	maxNumReductions,
		size_t *	pnumReductions,
		size_t *	pnumRowReductions,
		size_t *	pnumColumnReductions
	)

static

Carry out the actual reduction algorithm after all data structures are initialized.

Parameters

cmr	CMR environment.
listmatrix	List matrix.
rowData	Row data.
columnData	Column data.
rowHashtable	Row hashtable.
columnHashtable	Column hashtable.
entryToHash	Pre-computed hash values of vector entries.
queue	Queue.
pqueueStart	Pointer to start of queue.
pqueueEnd	Pointer to end of queue.
queueMemory	Memory allocated for queue.
reductions	Array for storing the SP-reductions. Must be sufficiently large, e.g., number **< of rows + number of columns.
maxNumReductions	Maximum number of SP-reductions. Stops when this would be exceeded.
pnumReductions	Pointer for storing the number of SP-reductions; stores `SIZE_MAX` if **< `maxNumReductions` was exceeded.
pnumRowReductions	Pointer for storing the number of row reductions (may be `NULL`).
pnumColumnReductions	Pointer for storing the number of column reductions (may be `NULL`).

◆ unlinkNonzero()

static void unlinkNonzero ( ListMat8Nonzero * nonzero )

inlinestatic

Removes the given nonzero from the linked-list representation.

Parameters

nonzero Nonzero to be removed from the linked lists.

Variable Documentation

◆ seriesParallelStringBuffer

char seriesParallelStringBuffer[32]

static

Static buffer for CMRspReductionString.

Classes

Enumerations

Functions

Variables

Enumeration Type Documentation

◆ ElementType

Function Documentation

◆ breadthFirstSearch()

◆ calcBinaryHashFromListMatrix()

◆ calcNonzeroCountHashFromMatrix()

◆ CMRspDecomposeBinary()

◆ CMRspDecomposeTernary()

◆ CMRspReductionString()

◆ CMRspStatsInit()

◆ CMRspStatsPrint()

◆ CMRspTestBinary()

◆ CMRspTestTernary()

◆ createElementData()

◆ createFullRemainingMatrix()

◆ createHashVector()

◆ decomposeBinarySeriesParallel()

◆ decomposeTernarySeriesParallel()

◆ extractNonbinarySubmatrix()

◆ extractRemainingSubmatrix()

◆ extractWheelSubmatrix()

◆ findCopy()

◆ initializeQueueHashtableFromListMatrix()

◆ initializeQueueHashtableFromMatrix()

◆ processNonzero()

◆ reduceListMatrix()

◆ unlinkNonzero()

Variable Documentation

◆ seriesParallelStringBuffer