#include <cmr/separation.h>
#include "separation_internal.h"
#include "env_internal.h"
#include "bipartite_graph.h"
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>

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

Functions
CMR_ERROR	CMRsepaCreate (CMR cmr, size_t numRows, size_t numColumns, CMR_SEPA *psepa)
	Creates a 2- or 3-separation. More...

CMR_ERROR	CMRsepaFree (CMR cmr, CMR_SEPA *psepa)
	Frees a separation. More...

CMR_ERROR	CMRsepaComputeSizes (CMR_SEPA sepa, size_t pnumRowsTopLeft, size_t pnumColumnsTopLeft, size_t pnumRowsBottomRight, size_t *pnumColumnsBottomRight)
	Computes the sizes of the top-left and bottom-right parts. More...

static CMR_ERROR	computeSubmatrixRank (CMR cmr, CMR_CHRMAT matrix, size_t numRows, size_t rows, bool columnsConsidered, CMR_SEPA_FLAGS rowsFlags, size_t prank, CMR_SUBMAT **pviolatorSubmatrix)
	Compute the binary and ternary of a submatrix of `matrix` (if at most 2). More...

static CMR_ERROR	findRepresentatives (CMR cmr, CMR_SEPA sepa, CMR_CHRMAT matrix, CMR_CHRMAT transpose, size_t submatrixRows, size_t submatrixColumns, bool pswapped, CMR_SUBMAT *pviolatorSubmatrix)
	Implementation of CMRsepaFindBinaryRepresentatives and CMRsepaFindBinaryRepresentativesSubmatrix. More...

CMR_ERROR	CMRsepaFindBinaryRepresentatives (CMR cmr, CMR_SEPA sepa, CMR_CHRMAT matrix, CMR_CHRMAT transpose, bool pswapped, CMR_SUBMAT *pviolator)
	Scans the support of `matrix` to compute all representative rows/columns for `sepa` and sets the type. More...

CMR_ERROR	CMRsepaFindBinaryRepresentativesSubmatrix (CMR cmr, CMR_SEPA sepa, CMR_CHRMAT matrix, CMR_CHRMAT transpose, CMR_SUBMAT submatrix, bool pswapped, CMR_SUBMAT **pviolator)
	Scans the support of `submatrix` of `matrix` to compute all representative rows/columns for `sepa` and sets the type. More...

CMR_ERROR	CMRsepaGetRepresentatives (CMR_SEPA *sepa, size_t reprRows[2][3], size_t reprColumns[2][3])
	Returns representative rows/columns of the low-rank submatrices. More...

CMR_ERROR	CMRsepaGetProjection (CMR_SEPA sepa, size_t part, size_t rowsToPart, size_t columnsToPart, size_t pnumPartRows, size_t *pnumPartColumns)
	Creates mappings from rows/columns to those of `part`; also maps up to 3 representative rows/columns. More...

static CMR_ERROR	checkTernary (CMR cmr, CMR_SEPA sepa, CMR_CHRMAT matrix, size_t submatrixRows, size_t columnsToSubmatrixColumn, bool pisTernary, CMR_SUBMAT **pviolator)
	Implementation of `CMRsepaCheckTernary` and `CMRsepaCheckTernarySubmatrix`. More...

CMR_ERROR	CMRsepaCheckTernary (CMR cmr, CMR_SEPA sepa, CMR_CHRMAT matrix, bool pisTernary, CMR_SUBMAT **pviolator)
	Checks for a given matrix whether the binary k-separation is also a ternary one. More...

CMR_ERROR	CMRsepaCheckTernarySubmatrix (CMR cmr, CMR_SEPA sepa, CMR_CHRMAT matrix, CMR_SUBMAT submatrix, bool pisTernary, CMR_SUBMAT *pviolator)
	Checks for a submatrix of a given matrix whether the binary k-separation is also a ternary one. More...

CMR_ERROR	CMRoneSumCompose (CMR cmr, size_t numMatrices, CMR_CHRMAT matrices, CMR_CHRMAT *presult)
	Composes the 1-sum of the several `matrices`. More...

CMR_ERROR	CMRtwoSumCompose (CMR cmr, CMR_CHRMAT first, CMR_CHRMAT second, size_t firstSpecialRows, size_t firstSpecialColumns, size_t secondSpecialRows, size_t secondSpecialColumns, int8_t characteristic, CMR_CHRMAT *presult)
	Composes the 2-sum of the two matrices `first` and `second` with connecting elements `firstMarker` and `secondMarker`. More...

CMR_ERROR	CMRtwoSumDecomposeFirst (CMR cmr, CMR_CHRMAT matrix, CMR_SEPA sepa, CMR_CHRMAT pfirst, size_t firstRowsOrigin, size_t firstColumnsOrigin, size_t rowsToFirst, size_t columnsToFirst, size_t firstSpecialRows, size_t *firstSpecialColumns)
	Decomposes `matrix` as a 2-sum according to the 2-separation `sepa`, computing the first component. More...

CMR_ERROR	CMRtwoSumDecomposeSecond (CMR cmr, CMR_CHRMAT matrix, CMR_SEPA sepa, CMR_CHRMAT psecond, size_t secondRowsOrigin, size_t secondColumnsOrigin, size_t rowsToSecond, size_t columnsToSecond, size_t secondSpecialRows, size_t *secondSpecialColumns)
	Decomposes `matrix` as a 2-sum according to the 2-separation `sepa`, computing the second component. More...

CMR_ERROR	CMRthreeSumSeymourCompose (CMR cmr, CMR_CHRMAT first, CMR_CHRMAT second, size_t firstSpecialRows, size_t firstSpecialColumns, size_t secondSpecialRows, size_t secondSpecialColumns, int8_t characteristic, CMR_CHRMAT *presult)
	Constructs the Seymour 3-sum of the two matrices `first` and `second` via `firstMarker1`, `firstMarker2`, `firstMarker3`, `secondMarker1`, `secondMarker2` and `secondMarker3`. More...

CMR_ERROR	CMRthreeSumSeymourDecomposeEpsilon (CMR cmr, CMR_CHRMAT matrix, CMR_CHRMAT transpose, CMR_SEPA sepa, char *pepsilon)
	Decomposes `matrix` as a Seymour 3-sum according to the 3-separation `sepa`, computing \( \varepsilon \). More...

CMR_ERROR	CMRthreeSumSeymourDecomposeFirst (CMR cmr, CMR_CHRMAT matrix, CMR_SEPA sepa, char epsilon, CMR_CHRMAT pfirst, size_t firstRowsOrigin, size_t firstColumnsOrigin, size_t rowsToFirst, size_t columnsToFirst, size_t firstSpecialRows, size_t *firstSpecialColumns)
	Decomposes `matrix` as a Seymour 3-sum according to the 3-separation `sepa`, computing the first component. More...

CMR_ERROR	CMRthreeSumSeymourDecomposeSecond (CMR cmr, CMR_CHRMAT matrix, CMR_SEPA sepa, char epsilon, CMR_CHRMAT psecond, size_t secondRowsOrigin, size_t secondColumnsOrigin, size_t rowsToSecond, size_t columnsToSecond, size_t secondSpecialRows, size_t *secondSpecialColumns)
	Decomposes `matrix` as a Seymour 3-sum according to the 3-separation `sepa`, computing the second component. More...

CMR_ERROR	CMRthreeSumTruemperCompose (CMR cmr, CMR_CHRMAT first, CMR_CHRMAT second, size_t firstSpecialRows, size_t firstSpecialColumns, size_t secondSpecialRows, size_t secondSpecialColumns, int8_t characteristic, CMR_CHRMAT *presult)
	Constructs the Truemper 3-sum of the two matrices `first` and `second` at connecting rows `firstSpecialRows` and `secondSpecialRows` and columns `firstSpecialColumns` and `secondSpecialColumns`. More...

CMR_ERROR	CMRthreeSumTruemperDecomposeSearch (CMR cmr, CMR_CHRMAT matrix, CMR_CHRMAT transpose, CMR_SEPA sepa, bool topLeft, bool bottomRight, CMR_SUBMAT *pviolator, size_t specialRows, size_t specialColumns, char pgamma, char *pbeta)
	Carries out the search for the connecting submatrix for a Truemper 3-sum. More...

CMR_ERROR	CMRthreeSumTruemperDecomposeConnecting (CMR cmr, CMR_CHRMAT matrix, CMR_CHRMAT transpose, CMR_SEPA sepa, size_t specialRows, size_t specialColumns, char pgamma, char pbeta)
	Decomposes `matrix` as a Truemper 3-sum according to the 3-separation `sepa`, computing the connecing matrix. More...

CMR_ERROR	CMRthreeSumTruemperDecomposeFirst (CMR cmr, CMR_CHRMAT matrix, CMR_SEPA sepa, size_t specialRows, size_t specialColumns, char beta, CMR_CHRMAT pfirst, size_t firstRowsOrigin, size_t firstColumnsOrigin, size_t rowsToFirst, size_t columnsToFirst, size_t firstSpecialRows, size_t *firstSpecialColumns)
	Decomposes `matrix` as a Truemper 3-sum according to the 3-separation `sepa`, computing the first component. More...

CMR_ERROR	CMRthreeSumTruemperDecomposeSecond (CMR cmr, CMR_CHRMAT matrix, CMR_SEPA sepa, size_t specialRows, size_t specialColumns, char gamma, CMR_CHRMAT psecond, size_t secondRowsOrigin, size_t secondColumnsOrigin, size_t rowsToSecond, size_t columnsToSecond, size_t secondSpecialRows, size_t *secondSpecialColumns)
	Decomposes `matrix` as a Truemper 3-sum according to the 3-separation `sepa`, computing the second component. More...

Function Documentation

◆ checkTernary()

static CMR_ERROR checkTernary	(	CMR *	cmr,
		CMR_SEPA *	sepa,
		CMR_CHRMAT *	matrix,
		size_t *	submatrixRows,
		size_t *	columnsToSubmatrixColumn,
		bool *	pisTernary,
		CMR_SUBMAT **	pviolator
	)

static

Implementation of CMRsepaCheckTernary and CMRsepaCheckTernarySubmatrix.

Parameters

cmr	CMR environment.
sepa	Separation.
matrix	Matrix.
submatrixRows	Array mapping a submatrix row to a row of `matrix`.
columnsToSubmatrixColumn	Array mapping a column of `matrix` to a column of the submatrix or `NULL`.
pisTernary	Pointer for storing whether the check passed.
pviolator	Pointer for storing a violator submatrix (may be `NULL`).

◆ CMRoneSumCompose()

CMR_ERROR CMRoneSumCompose	(	CMR *	cmr,
		size_t	numMatrices,
		CMR_CHRMAT **	matrices,
		CMR_CHRMAT **	presult
	)

Composes the 1-sum of the several matrices.

Let \( A_1, A_2, \dotsc, A_k \) denote the matrices given by the array matrices. Their 1-sum is the matrix

\[ B := \begin{bmatrix} A_1 & \mathbb{O} & \dots & \mathbb{O} \\ \mathbb{O} & A_2 & & \vdots \\ \vdots & & \ddots & \mathbb{O} \\ \mathbb{O} & \dots & \mathbb{O} & A_k \end{bmatrix}. \]

The resulting matrix \( B \) is created and stored in *presult.

See also: CMRdecomposeBlocks for a decomposition of a given matrix \( B \) into \( A_i \).

Parameters

cmr	CMR environment.
numMatrices	Number \( k \) of matrices in the sum.
matrices	First matrix.
presult	Pointer for storing the result.

◆ CMRsepaCheckTernary()

CMR_ERROR CMRsepaCheckTernary	(	CMR *	cmr,
		CMR_SEPA *	sepa,
		CMR_CHRMAT *	matrix,
		bool *	pisTernary,
		CMR_SUBMAT **	pviolator
	)

Checks for a given matrix whether the binary k-separation is also a ternary one.

Checks, for a ternary input matrix \( M \) and a k-separation ( \( k \in \{2,3\} \)) of the (binary) support matrix of \( M \), whether it is also a k-separation of \( M \) itself. The result is stored in *pisTernary.

If the check fails, a violating 2-by-2 submatrix is returned.

Parameters

cmr	CMR environment.
sepa	Separation.
matrix	Matrix.
pisTernary	Pointer for storing whether the check passed.
pviolator	Pointer for storing a violator submatrix (may be `NULL`).

◆ CMRsepaCheckTernarySubmatrix()

CMR_ERROR CMRsepaCheckTernarySubmatrix	(	CMR *	cmr,
		CMR_SEPA *	sepa,
		CMR_CHRMAT *	matrix,
		CMR_SUBMAT *	submatrix,
		bool *	pisTernary,
		CMR_SUBMAT **	pviolator
	)

Checks for a submatrix of a given matrix whether the binary k-separation is also a ternary one.

Checks, for a ternary input matrix \( M \) and a k-separation ( \( k \in \{2,3\} \)) of the (binary) support matrix of \( M \), whether it is also a k-separation of \( M \) itself. The result is stored in *pisTernary.

If the check fails, a certifying submatrix is returned in *pviolator. Its row/column indices refer to submatrix.

Parameters

cmr	CMR environment.
sepa	Separation.
matrix	Matrix.
submatrix	Submatrix to consider.
pisTernary	Pointer for storing whether the check passed.
pviolator	Pointer for storing a violator submatrix (may be `NULL`).

◆ CMRsepaComputeSizes()

CMR_ERROR CMRsepaComputeSizes	(	CMR_SEPA *	sepa,
		size_t *	pnumRowsTopLeft,
		size_t *	pnumColumnsTopLeft,
		size_t *	pnumRowsBottomRight,
		size_t *	pnumColumnsBottomRight
	)

Computes the sizes of the top-left and bottom-right parts.

Parameters

sepa	Separation.
pnumRowsTopLeft	Pointer for storing the number of rows of the top-left part.
pnumColumnsTopLeft	Pointer for storing the number of columns of the top-left part.
pnumRowsBottomRight	Pointer for storing the number of rows of the bottom-right part.
pnumColumnsBottomRight	Pointer for storing the number of columns of the bottom-right part.

◆ CMRsepaCreate()

CMR_ERROR CMRsepaCreate	(	CMR *	cmr,
		size_t	numRows,
		size_t	numColumns,
		CMR_SEPA **	psepa
	)

Creates a 2- or 3-separation.

Only the memory is allocated. The rowsFlags and columnsFlags arrays must be filled properly.

Parameters

cmr	CMR environment.
numRows	Number of rows.
numColumns	Number of columns.
psepa	Pointer for storing the created separation.

◆ CMRsepaFindBinaryRepresentatives()

CMR_ERROR CMRsepaFindBinaryRepresentatives	(	CMR *	cmr,
		CMR_SEPA *	sepa,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		bool *	pswapped,
		CMR_SUBMAT **	pviolator
	)

Scans the support of matrix to compute all representative rows/columns for sepa and sets the type.

Assumes that the sum of the ranks of the off-diagonal blocks is at most 2. Potentially swaps parts to ensure that the rank of the bottom-left submatrix is at least that of the top-right submatrix. Sets the rowsFlags and columnsFlags attributes accordingly.

Parameters

cmr	CMR environment.
sepa	Separation.
matrix	Matrix.
transpose	Transpose of `matrix`.
pswapped	Pointer for storing whether parts were swapped (may be `NULL`).
pviolator	Pointer for storing a violator submatrix if the ternary rank differs (may be `NULL`).

◆ CMRsepaFindBinaryRepresentativesSubmatrix()

CMR_ERROR CMRsepaFindBinaryRepresentativesSubmatrix	(	CMR *	cmr,
		CMR_SEPA *	sepa,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		CMR_SUBMAT *	submatrix,
		bool *	pswapped,
		CMR_SUBMAT **	pviolator
	)

Scans the support of submatrix of matrix to compute all representative rows/columns for sepa and sets the type.

Assumes that the sum of the ranks of the off-diagonal blocks is at most 2. Potentially swaps parts to ensure that the rank of the bottom-left submatrix is at least that of the top-right submatrix. Sets the rowsFlags and columnsFlags attributes accordingly.

Parameters

cmr	CMR environment.
sepa	Separation.
matrix	Matrix.
transpose	Transpose of `matrix`.
submatrix	Submatrix of `matrix`.
pswapped	Pointer for storing whether parts were swapped (may be `NULL`).
pviolator	Pointer for storing a violator submatrix if the ternary rank differs (may be `NULL`).

◆ CMRsepaFree()

CMR_ERROR CMRsepaFree	(	CMR *	cmr,
		CMR_SEPA **	psepa
	)

Frees a separation.

Parameters

cmr	CMR environment.
psepa	Pointer to separation.

◆ CMRsepaGetProjection()

CMR_ERROR CMRsepaGetProjection	(	CMR_SEPA *	sepa,
		size_t	part,
		size_t *	rowsToPart,
		size_t *	columnsToPart,
		size_t *	pnumPartRows,
		size_t *	pnumPartColumns
	)

Creates mappings from rows/columns to those of part; also maps up to 3 representative rows/columns.

Parameters

sepa	Separation.
part	Part to project.
rowsToPart	Array for storing the mapping from rows to those of `part`. Must be large enough.
columnsToPart	Array for storing the mapping from columns to those of `part`. Must be large enough.
pnumPartRows	Pointer for storing the number of rows of `part` (excluding representatives).
pnumPartColumns	Pointer for storing the number of columns of `part` (excluding representatives).

◆ CMRsepaGetRepresentatives()

CMR_ERROR CMRsepaGetRepresentatives	(	CMR_SEPA *	sepa,
		size_t	reprRows[2][3],
		size_t	reprColumns[2][3]
	)

Returns representative rows/columns of the low-rank submatrices.

Parameters

sepa	Separation.
reprRows	Array mapping child to arrays of (at most 3) different representative rows.
reprColumns	Array mapping child to arrays of (at most 3) different representative columns.

◆ CMRthreeSumSeymourCompose()

CMR_ERROR CMRthreeSumSeymourCompose	(	CMR *	cmr,
		CMR_CHRMAT *	first,
		CMR_CHRMAT *	second,
		size_t *	firstSpecialRows,
		size_t *	firstSpecialColumns,
		size_t *	secondSpecialRows,
		size_t *	secondSpecialColumns,
		int8_t	characteristic,
		CMR_CHRMAT **	presult
	)

Constructs the Seymour 3-sum of the two matrices first and second via firstMarker1, firstMarker2, firstMarker3, secondMarker1, secondMarker2 and secondMarker3.

Let \( M_1 \) and \( M_2 \) denote the matrices given by first and second, let \( A \) be the matrix \( M_1 \) without the row indexed by firstSpecialRows[0] and the columns indexed by firstSpecialColumns[0] and firstSpecialColumns[1]. After reordering these to be last, \( M_1 \) must be of the form \( M_1 = \begin{bmatrix} A & a & a \\ c^{\textsf{T}} & 0 & \varepsilon \end{bmatrix}, \) where \( \varepsilon \in \{-1,+1 \} \) (otherwise, CMR_ERROR_STRUCTURE is returned). Similarly, let \( D \) be the matrix \( M_2 \) without the row indexed by secondSpecialRows[0] and the columns indexed by secondSpecialColumns[0] and secondSpecialColumns[1]. After reordering these to be first, \( M_2 \) must be of the form \( M_2 = \begin{bmatrix} \varepsilon & 0 & b^{\textsf{T}} \\ d & d & D \end{bmatrix} \) with the same \( \varepsilon \) (otherwise, CMR_ERROR_STRUCTURE is returned). The 3-sum of \( M_1 \) and \( M_2 \) (at these special rows/columns) is the matrix

\[ M = \begin{bmatrix} A & a b^{\textsf{T}} \\ d c^{\textsf{T}} & D \end{bmatrix}. \]

The calculations are done modulo characteristic, where the value \( 3 \) yields numbers from \( \{-1,0,+1\} \).

The resulting matrix \( M \) is created and stored in *presult.

Parameters

cmr	CMR environment.
first	First matrix.
second	Second matrix.
firstSpecialRows	Array of length 1 with row index of \( \begin{bmatrix} c^{\textsf{T}} & 0 & \varepsilon \end{bmatrix} \) in \( M_1 \).
firstSpecialColumns	Array of length 2 with column indices of \( \begin{bmatrix} a \\ 0 \end{bmatrix} \) and \( \begin{bmatrix} a \\ \varepsilon \end{bmatrix} \) in \( M_1 \).
secondSpecialRows	Array of length 1 with row index of \( b^{\textsf{T}} \) \( \begin{bmatrix} \varepsilon & 0 & b^{\textsf{T}} \end{bmatrix} \) in \( M_2 \).
secondSpecialColumns	Array of length 2 with column indices \( \begin{bmatrix} \varepsilon \\ d \end{bmatrix} \) and \( \begin{bmatrix} 0 \\ d \end{bmatrix} \) in \( M_2 \).
characteristic	Field characteristic.
presult	Pointer for storing the result.

◆ CMRthreeSumSeymourDecomposeEpsilon()

CMR_ERROR CMRthreeSumSeymourDecomposeEpsilon	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		CMR_SEPA *	sepa,
		char *	pepsilon
	)

Decomposes matrix as a Seymour 3-sum according to the 3-separation sepa, computing \( \varepsilon \).

The input matrix \( M \) must have a 3-separation that is given by sepa, i.e., it can be reordered to look like \( M = \begin{bmatrix} A & B \\ C & D \end{bmatrix} \), where \( \text{rank}(B) = \text{rank}(C) = 1 \). The two components of the 3-sum are matrices \( M_1 = \begin{bmatrix} A & a & a \\ c^{\textsf{T}} & 0 & \varepsilon \end{bmatrix} \) and \( M_2 = \begin{bmatrix} \varepsilon & 0 & b^{\textsf{T}} \\ d & d & D \end{bmatrix} \) such that \( B = a b^{\textsf{T}} \) and \( C = d c^{\textsf{T}} \) hold and such that \( a \) and \( c^{\textsf{T}} \) are an actual column and row of \( M \). Consequently, \( b^{\textsf{T}} \) and \( d \) are (possibly negated) rows and columns of \( M \).

The value of \( \varepsilon \in \{-1,+1\} \) must be so that there exists a singular submatrix of \( M_1 \) with exactly two nonzeros per row and per column that covers the top-left \( \varepsilon \)-entry.

This function only computes \( \varepsilon \); the matrices \( M_1 \) and \( M_2 \) can be computed by CMRthreeSumSeymourDecomposeFirst and CMRthreeSumSeymourDecomposeSecond, respectively.

Parameters

cmr	CMR environment.
matrix	Input matrix \( M \).
transpose	Transpose matrix \( M^{\textsf{T}} \).
sepa	3-separation to decompose at.
pepsilon	Pointer for storing a correct value of \( \varepsilon \).

◆ CMRthreeSumSeymourDecomposeFirst()

CMR_ERROR CMRthreeSumSeymourDecomposeFirst	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_SEPA *	sepa,
		char	epsilon,
		CMR_CHRMAT **	pfirst,
		size_t *	firstRowsOrigin,
		size_t *	firstColumnsOrigin,
		size_t *	rowsToFirst,
		size_t *	columnsToFirst,
		size_t *	firstSpecialRows,
		size_t *	firstSpecialColumns
	)

Decomposes matrix as a Seymour 3-sum according to the 3-separation sepa, computing the first component.

The input matrix \( M \) must have a 3-separation that is given by sepa, i.e., it can be reordered to look like \( M = \begin{bmatrix} A & B \\ C & D \end{bmatrix} \), where \( \text{rank}(B) = \text{rank}(C) = 1 \). The two components of the 3-sum are matrices \( M_1 = \begin{bmatrix} A & a & a \\ c^{\textsf{T}} & 0 & \varepsilon \end{bmatrix} \) and \( M_2 = \begin{bmatrix} \varepsilon & 0 & b^{\textsf{T}} \\ d & d & D \end{bmatrix} \) such that \( B = a b^{\textsf{T}} \) and \( C = d c^{\textsf{T}} \) hold and such that \( a \) and \( c^{\textsf{T}} \) are an actual column and row of \( M \). Consequently, \( b^{\textsf{T}} \) and \( d \) are (possibly negated) rows and columns of \( M \).

The value of \( \varepsilon \in \{-1,+1\} \) must be given by epsilon and should be computed by CMRthreeSumSeymourDecomposeEpsilon.

This function computes \( M_1 \), while \( M_2 \) can be computed by CMRthreeSumSeymourDecomposeSecond.

If firstSpecialRows is not NULL, then firstSpecialRows[0] will refer to the last row of \( M_1 \). If firstSpecialColumns is not NULL, then firstSpecialColumns[0] will refer to the second-to last column and firstSpecialColumns[1] will refer to the last column of \( M_2 \).

Parameters

cmr	CMR environment.
matrix	Input matrix \( M \).
sepa	3-separation to decompose at.
epsilon	Value of \( \varepsilon \).
pfirst	Pointer for storing the first matrix \( M_1 \).
firstRowsOrigin	Array for storing the mapping from rows of \( M_1 \) to rows of \( M \); also set for the extra row if applicable, even if negated; may be `NULL`.
firstColumnsOrigin	Array for storing the mapping from columns of \( M_1 \) to columns of \( M \); also set for the extra column if applicable, even if negated; may be `NULL`.
rowsToFirst	Array for storing the mapping from rows of \( M \) to rows of \( M_1 \) or to `SIZE_MAX`; may be `NULL`.
columnsToFirst	Array for storing the mapping from columns of \( M \) to columns of \( M_1 \) or to `SIZE_MAX`; may be `NULL`.
firstSpecialRows	Array of length 1 for storing the row index of \( \begin{bmatrix} c^{\textsf{T}} & 0 & \varepsilon \end{bmatrix} \) in \( M_1 \); may be `NULL`.
firstSpecialColumns	Array of length 2 for storing the column indices of \( \begin{bmatrix} a \\ 0 \end{bmatrix} \) and \( \begin{bmatrix} a \\ \varepsilon \end{bmatrix} \) in \( M_1 \); may be `NULL`.

◆ CMRthreeSumSeymourDecomposeSecond()

CMR_ERROR CMRthreeSumSeymourDecomposeSecond	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_SEPA *	sepa,
		char	epsilon,
		CMR_CHRMAT **	psecond,
		size_t *	secondRowsOrigin,
		size_t *	secondColumnsOrigin,
		size_t *	rowsToSecond,
		size_t *	columnsToSecond,
		size_t *	secondSpecialRows,
		size_t *	secondSpecialColumns
	)

Decomposes matrix as a Seymour 3-sum according to the 3-separation sepa, computing the second component.

The input matrix \( M \) must have a 3-separation that is given by sepa, i.e., it can be reordered to look like \( M = \begin{bmatrix} A & B \\ C & D \end{bmatrix} \), where \( \text{rank}(B) = \text{rank}(C) = 1 \). The two components of the 3-sum are matrices \( M_1 = \begin{bmatrix} A & a & a \\ c^{\textsf{T}} & 0 & \varepsilon \end{bmatrix} \) and \( M_2 = \begin{bmatrix} \varepsilon & 0 & b^{\textsf{T}} \\ d & d & D \end{bmatrix} \) such that \( B = a b^{\textsf{T}} \) and \( C = d c^{\textsf{T}} \) hold and such that \( a \) and \( c^{\textsf{T}} \) are an actual column and row of \( M \). Consequently, \( b^{\textsf{T}} \) and \( d \) are (possibly negated) rows and columns of \( M \).

The value of \( \varepsilon \in \{-1,+1\} \) must be given by epsilon and should be computed by CMRthreeSumSeymourDecomposeEpsilon.

This function computes \( M_2 \), while \( M_1 \) can be computed by CMRthreeSumSeymourDecomposeFirst.

Note: If secondSpecialRows is not NULL, then secondSpecialRows[0] will refer to the first row of \( M_2 \).; If secondSpecialColumns is not NULL, then secondSpecialColumns[0] will refer to the first column and secondSpecialColumns[1] will refer to the second column of \( M_2 \).

Parameters

cmr	CMR environment.
matrix	Input matrix \( M \).
sepa	3-separation to decompose at.
epsilon	Value of \( \varepsilon \).
psecond	Pointer for storing the second matrix \( M_2 \).
secondRowsOrigin	Array for storing the mapping from rows of \( M_2 \) to rows of \( M \); also set for the extra row if applicable, even if negated; may be `NULL`.
secondColumnsOrigin	Array for storing the mapping from columns of \( M_2 \) to columns of \( M \); also set for the extra column if applicable, even if negated; may be `NULL`.
rowsToSecond	Array for storing the mapping from rows of \( M \) to rows of \( M_2 \) or to `SIZE_MAX`; may be `NULL`.
columnsToSecond	Array for storing the mapping from columns of \( M \) to columns of \( M_2 \) or to `SIZE_MAX`; may be `NULL`.
secondSpecialRows	Array of length 1 for storing the row index of \( \begin{bmatrix} \varepsilon & 0 & b^{\textsf{T}} \end{bmatrix} \) in \( M_2 \); may be `NULL`.
secondSpecialColumns	Array of length 2 for storing the column indices of \( \begin{bmatrix} \varepsilon & d \end{bmatrix} \) and \( \begin{bmatrix} 0 & d \end{bmatrix} \) in \( M_2 \); may be `NULL`.

◆ CMRthreeSumTruemperCompose()

CMR_ERROR CMRthreeSumTruemperCompose	(	CMR *	cmr,
		CMR_CHRMAT *	first,
		CMR_CHRMAT *	second,
		size_t *	firstSpecialRows,
		size_t *	firstSpecialColumns,
		size_t *	secondSpecialRows,
		size_t *	secondSpecialColumns,
		int8_t	characteristic,
		CMR_CHRMAT **	presult
	)

Constructs the Truemper 3-sum of the two matrices first and second at connecting rows firstSpecialRows and secondSpecialRows and columns firstSpecialColumns and secondSpecialColumns.

Let \( M_1 \) and \( M_2 \) denote the matrices given by first and second, let \( A \) be the matrix \( M_1 \) without the rows firstSpecialRows[0] and firstSpecialRows[1] and column firstSpecialColumns[2]. After permuting these to be last, \( M_1 \) must be of the form

\[ M_1 = \begin{bmatrix} A & \mathbb{O} \\ C_{i,\star} & \alpha \\ C_{j,\star} & \beta \end{bmatrix}, \]

where \( \alpha,\beta \in \{-1,+1 \} \) (otherwise, CMR_ERROR_STRUCTURE is returned). Let \( D \) be the matrix \( M_2 \) without the row secondSpecialRows[0] and columns secondSpecialColumns[0] and secondSpecialColumns[1]. After reordering these to be first, \( M_2 \) must be of the form

\[ M_2 = \begin{bmatrix} \gamma & \delta & \mathbb{O}^{\textsf{T}} \\ C_{\star,k} & C_{\star,\ell} & D \end{bmatrix}, \]

where \( \gamma,\delta \in \{ -1,+1 \} \) (otherwise, CMR_ERROR_STRUCTURE is returned) and such that the matrix

\[ N = \begin{bmatrix} \gamma & \delta & 0 \\ C_{i,k} & C_{i,\ell} & \alpha \\ C_{j,k} & C_{j,\ell} & \beta \end{bmatrix} \]

is totally unimodular. The columns firstSpecialColumns[0] and firstSpecialColumns[1] indicate the columns of \( M_1 \) that shall correspond to \( C_{\star,k}\) and \( C_{\star,\ell} \), respectively. Similarly, the rows secondSpecialRows[1] and secondSpecialRows[2] indicate the rows of \( M_2 \) that shall correspond to \( C_{i,\star}\) and \( C_{j,\star} \), respectively.

Note: The 2-by-2 submatrix of \( M_1 \) indexed by rows firstSpecialRows[0] and firstSpecialRows[1] and columns firstSpecialColumns[0] and firstSpecialColumns[1] must be identical to the submatrix of \( M_2 \) indexed by rows secondSpecialRows[1] and secondSpecialRows[2] and columns secondSpecialColumns[0] and secondSpecialColumns[1], which is the matrix \( C_{\{i,j\},\{k,\ell\}} \).

The 3-sum of \( M_1 \) and \( M_2 \) (at these rows/columns) is the matrix

\[ M = \begin{bmatrix} A & \mathbb{O} \\ C & D \end{bmatrix}, \]

where \( C \) is the unique rank-2 matrix having linearly independent rows \( C_{i,\star} \) and \( C_{j,\star} \) and linearly independent columns \( C_{\star,k} \) and \( C_{\star,\ell} \). The calculations are done modulo characteristic, where the value \( 3 \) yields numbers from \( \{-1,0,+1\} \).

The resulting matrix \( M \) is created and stored in *presult.

Parameters

cmr	CMR environment.
first	First matrix.
second	Second matrix.
firstSpecialRows	Array of length 2 with the last two rows of the connecting submatrix in `first`.
firstSpecialColumns	Array of length 3 with all columns of the connecting submatrix in `first`.
secondSpecialRows	Array of length 3 with the all rows of the connecting submatrix in `second`.
secondSpecialColumns	Array of length 2 with the first two columns of connecting submatrix in `second`.
characteristic	Field characteristic.
presult	Pointer for storing the result.

◆ CMRthreeSumTruemperDecomposeConnecting()

CMR_ERROR CMRthreeSumTruemperDecomposeConnecting	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		CMR_SEPA *	sepa,
		size_t *	specialRows,
		size_t *	specialColumns,
		char *	pgamma,
		char *	pbeta
	)

Decomposes matrix as a Truemper 3-sum according to the 3-separation sepa, computing the connecing matrix.

The input matrix \( M \) must have a 3-separation that is given by sepa, i.e., it can be reordered to look like \( M = \begin{bmatrix} A & \mathbb{O} \\ C & D \end{bmatrix} \), where \( \text{rank}(C) = 2 \). The two components of the 3-sum are matrices

\[ M_1 = \begin{bmatrix} A & \mathbb{O} \\ C_{i,\star} & 1 \\ C_{j,\star} & \beta \end{bmatrix} \]

and

\[ M_2 = \begin{bmatrix} \gamma & 1 & \mathbb{O}^{\textsf{T}} \\ C_{\star,k} & C_{\star,\ell} & D \end{bmatrix}, \]

where \( \beta,\gamma \in \{-1,+1 \} \), \(\text{rank}(C_{\{i,j\},\{k,\ell\}}) = 2\) and such that

\[ N := \begin{bmatrix} \gamma & 1 & 0 \\ C_{i,k} & C_{i,\ell} & 1 \\ C_{j,k} & C_{j,\ell} & \beta \end{bmatrix} \]

is totally unimodular.

The value of \( \beta \in \{-1,+1\} \) must be so that there exists a singular submatrix of \( M_1 \) with exactly two nonzeros per row and per column that covers the bottom-right \( \beta \)-entry.

This function only computes the indices \( i,j,k,\ell \) as well as values for \( \beta \) and \( \gamma \); the matrices \( M_1 \) and \( M_2 \) can be computed by CMRthreeSumTruemperDecomposeFirst and CMRthreeSumTruemperDecomposeSecond, respectively.

Parameters

cmr	CMR environment.
matrix	Input matrix \( M \).
transpose	Transpose matrix \( M^{\textsf{T}} \).
sepa	3-separation to decompose at.
specialRows	Array of length 2 for storing the rows \( i \) and \( j \) as rows of \( M \).
specialColumns	Array of length 2 for storing the columns \( k \) and \( \ell \) as rows of \( M \).
pgamma	Pointer for storing a correct value of \( \gamma \); may be `NULL`.
pbeta	Pointer for storing a correct value of \( \beta \); may be `NULL`.

◆ CMRthreeSumTruemperDecomposeFirst()

CMR_ERROR CMRthreeSumTruemperDecomposeFirst	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_SEPA *	sepa,
		size_t *	specialRows,
		size_t *	specialColumns,
		char	beta,
		CMR_CHRMAT **	pfirst,
		size_t *	firstRowsOrigin,
		size_t *	firstColumnsOrigin,
		size_t *	rowsToFirst,
		size_t *	columnsToFirst,
		size_t *	firstSpecialRows,
		size_t *	firstSpecialColumns
	)

Decomposes matrix as a Truemper 3-sum according to the 3-separation sepa, computing the first component.

The input matrix \( M \) must have a 3-separation that is given by sepa, i.e., it can be reordered to look like \( M = \begin{bmatrix} A & \mathbb{O} \\ C & D \end{bmatrix} \), where \( \text{rank}(C) = 2 \). The two components of the 3-sum are matrices

\[ M_1 = \begin{bmatrix} A & \mathbb{O} \\ C_{i,\star} & 1 \\ C_{j,\star} & \beta \end{bmatrix} \]

and

\[ M_2 = \begin{bmatrix} \gamma & 1 & \mathbb{O}^{\textsf{T}} \\ C_{\star,k} & C_{\star,\ell} & D \end{bmatrix}, \]

where \( \beta,\gamma \in \{-1,+1 \} \), \(\text{rank}(C_{\{i,j\},\{k,\ell\}}) = 2\) and such that

\[ N := \begin{bmatrix} \gamma & 1 & 0 \\ C_{i,k} & C_{i,\ell} & 1 \\ C_{j,k} & C_{j,\ell} & \beta \end{bmatrix} \]

is totally unimodular.

The value of \( \beta \in \{-1,+1\} \), given via beta. The row indices \( i,j \), given via specialRows, and column indices \( k,\ell \), given via specialColumns, must index a rank-2 submatrix of \( C \). They should be computed by CMRthreeSumTruemperDecomposeConnecting.

This function computes \( M_1 \), while \( M_2 \) can be computed by CMRthreeSumTruemperDecomposeSecond.

If firstSpecialRows is not NULL, then firstSpecialRows[0] and firstSpecialRows[1] will refer to the last two rows of \( M_1 \). If firstSpecialColumns is not NULL, then firstSpecialColumns[0] and firstSpecialColumns[1] will refer to the two columns containing \( C_{\star,k}\) and \( C_{\star,\ell} \) as columns of \( M_1 \), and firstSpecialColumns[2] will refer to the last (artificial) column.

Parameters

cmr	CMR environment.
matrix	Input matrix \( M \).
sepa	3-separation to decompose at.
specialRows	Array of length 2 with the rows \( i \) and \( j \) as rows of \( M \).
specialColumns	Array of length 2 with the columns \( k \) and \( \ell \) as rows of \( M \).
beta	Value of \( \beta \).
pfirst	Pointer for storing the first matrix \( M_1 \).
firstRowsOrigin	Array for storing the mapping from rows of \( M_1 \) to rows of \( M \); may be `NULL`.
firstColumnsOrigin	Array for storing the mapping from columns of \( M_1 \) to columns of \( M \); set to `SIZE_MAX` for the last column; may be `NULL`.
rowsToFirst	Array for storing the mapping from rows of \( M \) to rows of \( M_1 \) or to `SIZE_MAX`; may be `NULL`.
columnsToFirst	Array for storing the mapping from columns of \( M \) to columns of \( M_1 \) or to `SIZE_MAX`; may be `NULL`.
firstSpecialRows	Array of length 2 for storing the row indices of \( C_{i,\star} \) and of \( C_{j,\star} \) in \( M_1 \); may be `NULL`.
firstSpecialColumns	Array of length 3 for storing the column indices of \( C_{\star,k} \), of \( C_{\star,\ell} \) and of the artificial column in \( M_1 \); may be `NULL`.

◆ CMRthreeSumTruemperDecomposeSearch()

CMR_ERROR CMRthreeSumTruemperDecomposeSearch	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		CMR_SEPA *	sepa,
		bool	topLeft,
		bool	bottomRight,
		CMR_SUBMAT **	pviolator,
		size_t *	specialRows,
		size_t *	specialColumns,
		char *	pgamma,
		char *	pbeta
	)

Carries out the search for the connecting submatrix for a Truemper 3-sum.

See CMRthreeSumTruemperDecomposeConnecting for the specification. This function carries out a breadth-first search in the graphs of the top-left and/or bottom-right submatrices.

At least one of topLeft and bottomRight must be true. If both are true then the implementation may detect a submatrix with absolute determinant 2, which is also stored in *pviolator if pviolator is not NULL. Even if this is the case, specialRows, specialColumns, *pgamma and *pbeta are set according to the top-left matrix.

Connecting matrix is:

gamma 1 0 s00 s01 1 s10 s11 beta

gamma + 1 should be equal to the top-left sum (mod 4).

The 3x3 matrix should be singular: gamma*s01*beta + s10 - s11*gamma - beta*s00 = 0. <=> beta * (gamma*s01 - s00) = s11*gamma - s10. <=> beta = (s10 - s11*gamma) / (s00 - gamma*s01) <=> gamma * (s01*beta - s11) = beta * s00 - s10 <=> gamma = (s10 - beta * s00) / (s11 - s01*beta)

Parameters

cmr	CMR environment.
matrix	Input matrix \( M \).
transpose	Transpose matrix \( M^{\textsf{T}} \).
sepa	3-separation to decompose at.
topLeft	Whether to search in the top-left submatrix.
bottomRight	Whether to search in the bottom-right submatrix.
pviolator	Pointer for storing a submatrix with absolute determinant 2, if found.
specialRows	Array of length 2 for storing the rows \( i \) and \( j \) as rows of \( M \).
specialColumns	Array of length 2 for storing the columns \( k \) and \( \ell \) as rows of \( M \).
pgamma	Pointer for storing a correct value of \( \gamma \); may be `NULL`.
pbeta	Pointer for storing a correct value of \( \beta \); may be `NULL`.

◆ CMRthreeSumTruemperDecomposeSecond()

CMR_ERROR CMRthreeSumTruemperDecomposeSecond	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_SEPA *	sepa,
		size_t *	specialRows,
		size_t *	specialColumns,
		char	gamma,
		CMR_CHRMAT **	psecond,
		size_t *	secondRowsOrigin,
		size_t *	secondColumnsOrigin,
		size_t *	rowsToSecond,
		size_t *	columnsToSecond,
		size_t *	secondSpecialRows,
		size_t *	secondSpecialColumns
	)

Decomposes matrix as a Truemper 3-sum according to the 3-separation sepa, computing the second component.

The input matrix \( M \) must have a 3-separation that is given by sepa, i.e., it can be reordered to look like \( M = \begin{bmatrix} A & \mathbb{O} \\ C & D \end{bmatrix} \), where \( \text{rank}(C) = 2 \). The two components of the 3-sum are matrices

\[ M_1 = \begin{bmatrix} A & \mathbb{O} \\ C_{i,\star} & 1 \\ C_{j,\star} & \beta \end{bmatrix} \]

and

\[ M_2 = \begin{bmatrix} \gamma & 1 & \mathbb{O}^{\textsf{T}} \\ C_{\star,k} & C_{\star,\ell} & D \end{bmatrix}, \]

where \( \beta,\gamma \in \{-1,+1 \} \), \(\text{rank}(C_{\{i,j\},\{k,\ell\}}) = 2\) and such that

\[ N := \begin{bmatrix} \gamma & 1 & 0 \\ C_{i,k} & C_{i,\ell} & 1 \\ C_{j,k} & C_{j,\ell} & \beta \end{bmatrix} \]

is totally unimodular.

The value of \( \gamma \in \{-1,+1\} \), given via gamma. The row indices \( i,j \), given via specialRows, and column indices \( k,\ell \), given via specialColumns, must index a rank-2 submatrix of \( C \). They should be computed by CMRthreeSumTruemperDecomposeConnecting.

This function computes \( M_2 \), while \( M_1 \) can be computed by CMRthreeSumTruemperDecomposeFirst.

If secondSpecialRows is not NULL, then secondSpecialRows[0] will refer to the first (artificial) row and secondSpecialRows[1] and secondSpecialRows[2] will refer to the two rows containing \( C_{i,\star} \) and \( C_{j,\star} \) as rows of \( M_2 \). If secondSpecialColumns is not NULL, then secondSpecialColumns[0] and secondSpecialColumns[1] will refer to the first two columns of \( M_2 \).

Parameters

cmr	CMR environment.
matrix	Input matrix \( M \).
sepa	3-separation to decompose at.
specialRows	Array of length 2 with the rows \( i \) and \( j \) as rows of \( M \).
specialColumns	Array of length 2 with the columns \( k \) and \( \ell \) as rows of \( M \).
gamma	Value of \( \gamma \).
psecond	Pointer for storing the second matrix \( M_2 \).
secondRowsOrigin	Array for storing the mapping from rows of \( M_2 \) to rows of \( M \); set to `SIZE_MAX` for the first row; may be `NULL`.
secondColumnsOrigin	Array for storing the mapping from columns of \( M_2 \) to columns of \( M \); may be `NULL`.
rowsToSecond	Array for storing the mapping from rows of \( M \) to rows of \( M_2 \) or to `SIZE_MAX`; may be `NULL`.
columnsToSecond	Array for storing the mapping from columns of \( M \) to columns of \( M_2 \) or to `SIZE_MAX`; may be `NULL`.
secondSpecialRows	Array of length 3 for storing the row indices of the artificial row, of \( C_{i,\star} \) and of \( C_{j,\star} \) in \( M_2 \); may be `NULL`.
secondSpecialColumns	Array of length 2 for storing the column indices of \( C_{\star,k} \) and of \( C_{\star,\ell} \) in \( M_2 \); may be `NULL`.

◆ CMRtwoSumCompose()

CMR_ERROR CMRtwoSumCompose	(	CMR *	cmr,
		CMR_CHRMAT *	first,
		CMR_CHRMAT *	second,
		size_t *	firstSpecialRows,
		size_t *	firstSpecialColumns,
		size_t *	secondSpecialRows,
		size_t *	secondSpecialColumns,
		int8_t	characteristic,
		CMR_CHRMAT **	presult
	)

Composes the 2-sum of the two matrices first and second with connecting elements firstMarker and secondMarker.

Depending on the input, one of two variants of the 2-sum of two matrices \( M_1 \), given by first and \( M_2 \), given by second are computed. For the first variant, consider the matrices \( M_1 = \begin{bmatrix} A \\ c^{\textsf{T}} \end{bmatrix} \) and \( M_2 = \begin{bmatrix} d & D \end{bmatrix} \). Then the 2-sum is the matrix

\[ M := \begin{bmatrix} A & \mathbb{O} \\ d c^{\textsf{T}} & D \end{bmatrix}. \]

To obtain this 2-sum, the arrays firstSpecialRows and secondSpecialColumns must be arrays of length 1, consisting of the row index of \( c^{\textsf{T}} \) of \( M_1 \) and of the column index of \( d \) of \( M_2 \). For the other variant, consider the matrices \( M_1 = \begin{bmatrix} A & a \end{bmatrix} \) and \( M_2 = \begin{bmatrix} b^{\textsf{T}} \\ D \end{bmatrix} \). Then the 2-sum is the matrix

\[ M := \begin{bmatrix} A & a b^{\textsf{T}} \\ \mathbb{O} & D \end{bmatrix}. \]

To obtain this 2-sum, the arrays firstSpecialColumns and secondSpecialRows must be arrays of length 1, consisting of the column index of \( a \) of \( M_1 \) and of the row index of \( b^{\textsf{T}} \) of \( M_2 \).

The calculations are done modulo characteristic, where the value \( 3 \) yields numbers from \( \{-1,0,+1\} \).

The resulting matrix \( M \) is created and stored in *presult.

Parameters

cmr	CMR environment.
first	First matrix \( M_1 \).
second	Second matrix \( M_2 \).
firstSpecialRows	Array of length 1 with row index of \( c^{\textsf{T}} \) or `NULL`.
firstSpecialColumns	Array of length 1 with column index of \( a \) or `NULL`.
secondSpecialRows	Array of length 1 with row index of \( b^{\textsf{T}} \) or `NULL`.
secondSpecialColumns	Array of length 1 with column index of \( d \) or `NULL`.
characteristic	Field characteristic.
presult	Pointer for storing the result.

◆ CMRtwoSumDecomposeFirst()

CMR_ERROR CMRtwoSumDecomposeFirst	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_SEPA *	sepa,
		CMR_CHRMAT **	pfirst,
		size_t *	firstRowsOrigin,
		size_t *	firstColumnsOrigin,
		size_t *	rowsToFirst,
		size_t *	columnsToFirst,
		size_t *	firstSpecialRows,
		size_t *	firstSpecialColumns
	)

Decomposes matrix as a 2-sum according to the 2-separation sepa, computing the first component.

The input matrix \( M \) must have a 2-separation that is given by sepa, i.e., it can be reordered to look like \( M = \begin{bmatrix} A & B \\ C & D \end{bmatrix} \), where \( \text{rank}(B) + \text{rank}(C) = 1 \). If \( \text{rank}(B) = \mathbb{O} \) then the two components of the 2-sum are matrices \( M_1 = \begin{bmatrix} A \\ c^{\textsf{T}} \end{bmatrix} \) and \( M_2 = \begin{bmatrix} d & D \end{bmatrix} \) such that \( C = d c^{\textsf{T}} \) holds and such that \( c^{\textsf{T}} \) is an actual row of \( M \). Otherwise, the two components of the 2-sum are matrices \( M_1 = \begin{bmatrix} A & a \end{bmatrix} \) and \( M_2 = \begin{bmatrix} b^{\textsf{T}} \\ D \end{bmatrix} \) such that \( B = a b^{\textsf{T}} \) holds and such that \( a \) is an actual column of \( M \).

This function computes \( M_1 \), while \( M_2 \) can be computed by CMRtwoSumDecomposeSecond.

Note: For the first variant, if firstSpecialRows is not NULL then *firstSpecialRows[0] will be the last row.; For the second variant, if firstSpecialColumns is not NULL then *firstSpecialColumns[0] will be the last column.

Parameters

cmr	CMR environment.
matrix	Input matrix \( M \).
sepa	2-separation to decompose at.
pfirst	Pointer for storing the first matrix \( M_1 \).
firstRowsOrigin	Array for storing the mapping from rows of \( M_1 \) to rows of \( M \); also set for the extra row if applicable; may be `NULL`.
firstColumnsOrigin	Array for storing the mapping from columns of \( M_1 \) to columns of \( M \); also set for the extra column if applicable; may be `NULL`.
rowsToFirst	Array for storing the mapping from rows of \( M \) to rows of \( M_1 \) or to `SIZE_MAX`; may be `NULL`.
columnsToFirst	Array for storing the mapping from columns of \( M \) to columns of \( M_1 \) or to `SIZE_MAX`; may be `NULL`.
firstSpecialRows	Either `NULL` or an array for storing the row index of \( c^{\textsf{T}} \) in \( M_1 \).
firstSpecialColumns	Either `NULL` or an array for storing the column index of \( a \) in \( M_1 \).

◆ CMRtwoSumDecomposeSecond()

CMR_ERROR CMRtwoSumDecomposeSecond	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		CMR_SEPA *	sepa,
		CMR_CHRMAT **	psecond,
		size_t *	secondRowsOrigin,
		size_t *	secondColumnsOrigin,
		size_t *	rowsToSecond,
		size_t *	columnsToSecond,
		size_t *	secondSpecialRows,
		size_t *	secondSpecialColumns
	)

Decomposes matrix as a 2-sum according to the 2-separation sepa, computing the second component.

The input matrix \( M \) must have a 2-separation that is given by sepa, i.e., it can be reordered to look like \( M = \begin{bmatrix} A & B \\ C & D \end{bmatrix} \), where \( \text{rank}(B) + \text{rank}(C) = 1 \). If \( \text{rank}(B) = \mathbb{O} \) then the two components of the 2-sum are matrices \( M_1 = \begin{bmatrix} A \\ c^{\textsf{T}} \end{bmatrix} \) and \( M_2 = \begin{bmatrix} d & D \end{bmatrix} \) such that \( C = d c^{\textsf{T}} \) holds and such that \( c^{\textsf{T}} \) is an actual row of \( M \). Otherwise, the two components of the 2-sum are matrices \( M_1 = \begin{bmatrix} A & a \end{bmatrix} \) and \( M_2 = \begin{bmatrix} b^{\textsf{T}} \\ D \end{bmatrix} \) such that \( B = a b^{\textsf{T}} \) holds and such that \( a \) is an actual column of \( M \).

This function computes \( M_2 \), while \( M_1 \) can be computed by CMRtwoSumDecomposeFirst.

Note: For the first variant, if secondSpecialColumns is not NULL then *secondSpecialColumns[0] will be the first column.; For the second variant, if secondSpecialRows is not NULL then *secondSpecialRows[0] will be the first row.

Parameters

cmr	CMR environment.
matrix	Input matrix \( M \).
sepa	2-separation to decompose at.
psecond	Pointer for storing the second matrix \( M_2 \).
secondRowsOrigin	Array for storing the mapping from rows of \( M_2 \) to rows of \( M \); also set for the extra row if applicable; may be `NULL`.
secondColumnsOrigin	Array for storing the mapping from columns of \( M_2 \) to columns of \( M \); also set for the extra column if applicable; may be `NULL`.
rowsToSecond	Array for storing the mapping from rows of \( M \) to rows of \( M_2 \) or to `SIZE_MAX`; may be `NULL`.
columnsToSecond	Array for storing the mapping from columns of \( M \) to columns of \( M_2 \) or to `SIZE_MAX`; may be `NULL`.
secondSpecialRows	Either `NULL` or an array for storing the row index of \( b^{\textsf{T}} \) in \( M_2 \).
secondSpecialColumns	Either `NULL` or an array for storing the column index of \( d \) in \( M_2 \).

◆ computeSubmatrixRank()

static CMR_ERROR computeSubmatrixRank	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		size_t	numRows,
		size_t *	rows,
		bool *	columnsConsidered,
		CMR_SEPA_FLAGS *	rowsFlags,
		size_t *	prank,
		CMR_SUBMAT **	pviolatorSubmatrix
	)

static

Compute the binary and ternary of a submatrix of matrix (if at most 2).

Update indicator columns.

Parameters

cmr	CMR environment.
matrix	Matrix.
numRows	Number of rows.
rows	Array with row indices.
columnsConsidered	Array indicating for each column of `matrix` whether it shall be considered.
rowsFlags	Array of length `numRows` for storing the flags for representatives.
prank	Pointer for storing the computed rank.
pviolatorSubmatrix	Pointer for storing a submatrix of absolute determinant 2 (or `NULL`).

◆ findRepresentatives()

static CMR_ERROR findRepresentatives	(	CMR *	cmr,
		CMR_SEPA *	sepa,
		CMR_CHRMAT *	matrix,
		CMR_CHRMAT *	transpose,
		size_t *	submatrixRows,
		size_t *	submatrixColumns,
		bool *	pswapped,
		CMR_SUBMAT **	pviolatorSubmatrix
	)

static

Implementation of CMRsepaFindBinaryRepresentatives and CMRsepaFindBinaryRepresentativesSubmatrix.

Parameters

cmr	CMR environment.
sepa	Separation.
matrix	Matrix.
transpose	Transpose of `matrix`.
submatrixRows	Array mapping a submatrix row to a row of `matrix`.
submatrixColumns	Array mapping a submatrix column to a column of `matrix`.
pswapped	Pointer for storing whether parts were swapped (may be `NULL`).
pviolatorSubmatrix	Pointer for storing a violator submatrix if the ternary rank differs **< (may be `NULL`).

Classes

Functions

Function Documentation

◆ checkTernary()

◆ CMRoneSumCompose()

◆ CMRsepaCheckTernary()

◆ CMRsepaCheckTernarySubmatrix()

◆ CMRsepaComputeSizes()

◆ CMRsepaCreate()

◆ CMRsepaFindBinaryRepresentatives()

◆ CMRsepaFindBinaryRepresentativesSubmatrix()

◆ CMRsepaFree()

◆ CMRsepaGetProjection()

◆ CMRsepaGetRepresentatives()

◆ CMRthreeSumSeymourCompose()

◆ CMRthreeSumSeymourDecomposeEpsilon()

◆ CMRthreeSumSeymourDecomposeFirst()

◆ CMRthreeSumSeymourDecomposeSecond()

◆ CMRthreeSumTruemperCompose()

◆ CMRthreeSumTruemperDecomposeConnecting()

◆ CMRthreeSumTruemperDecomposeFirst()

◆ CMRthreeSumTruemperDecomposeSearch()

◆ CMRthreeSumTruemperDecomposeSecond()

◆ CMRtwoSumCompose()

◆ CMRtwoSumDecomposeFirst()

◆ CMRtwoSumDecomposeSecond()

◆ computeSubmatrixRank()

◆ findRepresentatives()