separation.h File Reference

Data structures for k-separations and k-sums. More...

#include <cmr/env.h>
#include <cmr/matrix.h>
#include <cmr/element.h>
#include <assert.h>
#include <stdint.h>

Go to the source code of this file.

Classes
struct	CMR_SEPA

Enumerations
enum	CMR_SEPA_FLAGS {   CMR_SEPA_FIRST = 0 , CMR_SEPA_SECOND = 1 , CMR_SEPA_FLAG_RANK1 = 2 , CMR_SEPA_FLAG_RANK2 = 4 ,   CMR_SEPA_MASK_CHILD = 1 , CMR_SEPA_MASK_EXTRA = CMR_SEPA_FLAG_RANK1 | CMR_SEPA_FLAG_RANK2 }
enum	CMR_SEPA_TYPE { CMR_SEPA_TYPE_TWO = 2 , CMR_SEPA_TYPE_THREE_DISTRIBUTED_RANKS = 3 , CMR_SEPA_TYPE_THREE_CONCENTRATED_RANK = 4 }

Functions
CMR_EXPORT CMR_ERROR	CMRsepaCreate (CMR *cmr, size_t numRows, size_t numColumns, CMR_SEPA **psepa)
	Creates a 2- or 3-separation.
CMR_EXPORT CMR_ERROR	CMRsepaFree (CMR *cmr, CMR_SEPA **psepa)
	Frees a separation.
CMR_EXPORT CMR_ERROR	CMRsepaTranspose (CMR *cmr, CMR_SEPA *sepa, CMR_SEPA **ptransposed)
	Transposes a given separation.
CMR_EXPORT 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.
CMR_EXPORT 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.
CMR_EXPORT 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.
CMR_EXPORT 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.
CMR_EXPORT 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.
CMR_EXPORT 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.
CMR_EXPORT 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.
CMR_EXPORT CMR_ERROR	CMRonesumCompose (CMR *cmr, size_t numMatrices, CMR_CHRMAT **matrices, CMR_CHRMAT **presult)
	Composes the 1-sum of the several matrices.
CMR_EXPORT 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.
CMR_EXPORT 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.
CMR_EXPORT 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.
CMR_EXPORT CMR_ERROR	CMRdeltasumCompose (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 \( \Delta \)-sum of the two matrices first and second.
CMR_EXPORT CMR_ERROR	CMRdeltasumDecomposeEpsilon (CMR *cmr, CMR_CHRMAT *matrix, CMR_CHRMAT *transpose, CMR_SEPA *sepa, char *pepsilon)
	Decomposes matrix as a \( \Delta \)-sum according to the 3-separation sepa, computing \( \varepsilon \).
CMR_EXPORT CMR_ERROR	CMRdeltasumDecomposeFirst (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 \( \Delta \)-sum according to the 3-separation sepa, computing the first component.
CMR_EXPORT CMR_ERROR	CMRdeltasumDecomposeSecond (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 \( \Delta \)-sum according to the 3-separation sepa, computing the second component.
CMR_EXPORT CMR_ERROR	CMRysumCompose (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 Y-sum of the two matrices first and second.
CMR_EXPORT CMR_ERROR	CMRysumDecomposeEpsilon (CMR *cmr, CMR_CHRMAT *matrix, CMR_CHRMAT *transpose, CMR_SEPA *sepa, char *pepsilon)
	Decomposes matrix as a Y-sum according to the 3-separation sepa, computing \( \varepsilon \).
CMR_EXPORT CMR_ERROR	CMRysumDecomposeFirst (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 Y-sum according to the 3-separation sepa, computing the first component.
CMR_EXPORT CMR_ERROR	CMRysumDecomposeSecond (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 Y-sum according to the 3-separation sepa, computing the second component.
CMR_EXPORT CMR_ERROR	CMRthreesumCompose (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 3-sum of the two matrices first and second at connecting rows firstSpecialRows and secondSpecialRows and columns firstSpecialColumns and secondSpecialColumns.
CMR_EXPORT CMR_ERROR	CMRthreesumDecomposeSearchConnecting (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 3-sum according to the 3-separation sepa, searching a suitable connecing matrix.
CMR_EXPORT CMR_ERROR	CMRthreesumDecomposeSignConnecting (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 3-sum according to the 3-separation sepa, searching a suitable connecing matrix.
CMR_EXPORT CMR_ERROR	CMRthreesumDecomposeFirst (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 3-sum according to the 3-separation sepa, computing the first component.
CMR_EXPORT CMR_ERROR	CMRthreesumDecomposeSecond (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 3-sum according to the 3-separation sepa, computing the second component.

Detailed Description

Data structures for k-separations and k-sums.

Author

Matthias Walter

Enumeration Type Documentation

CMR_SEPA_FLAGS

enum CMR_SEPA_FLAGS

Enumerator
CMR_SEPA_FIRST	This row/column belongs to the first child.
CMR_SEPA_SECOND	This row/column belongs to the second child.
CMR_SEPA_FLAG_RANK1	This bit flag indicates that the row/column also belongs to the other child.
CMR_SEPA_FLAG_RANK2	This bit flag indicates that the row/column also belongs to the other child and is independent of the one from CMR_SEPA_FLAG_RANK1.
CMR_SEPA_MASK_CHILD	Bit mask for the ownership.
CMR_SEPA_MASK_EXTRA	Bit mask extra belongings.

CMR_SEPA_TYPE

enum CMR_SEPA_TYPE

Enumerator
CMR_SEPA_TYPE_TWO	2-separation whose bottom-left part has rank 1.
CMR_SEPA_TYPE_THREE_DISTRIBUTED_RANKS	3-separation with distributed ranks.
CMR_SEPA_TYPE_THREE_CONCENTRATED_RANK	3-separation whose botom-left part has rank 2.

Function Documentation

CMRdeltasumCompose()

CMR_EXPORT CMR_ERROR CMRdeltasumCompose	(	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 \( \Delta \)-sum of the two matrices first and second.

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 \( \Delta \)-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.

CMRdeltasumDecomposeEpsilon()

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

Decomposes matrix as a \( \Delta \)-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 \( \Delta \)-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 CMRdeltasumDecomposeFirst and CMRdeltasumDecomposeSecond, 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 \).

CMRdeltasumDecomposeFirst()

CMR_EXPORT CMR_ERROR CMRdeltasumDecomposeFirst	(	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 \( \Delta \)-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 \( \Delta \)-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 CMRdeltasumDecomposeEpsilon.

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

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.

CMRdeltasumDecomposeSecond()

CMR_EXPORT CMR_ERROR CMRdeltasumDecomposeSecond	(	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 \( \Delta \)-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 \( \Delta \)-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 CMRdeltasumDecomposeEpsilon.

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

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.

CMRonesumCompose()

CMR_EXPORT 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_EXPORT 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_EXPORT 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_EXPORT 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_EXPORT 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_EXPORT 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_EXPORT 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_EXPORT CMR_ERROR CMRsepaFree	(	CMR *	cmr,
		CMR_SEPA **	psepa
	)

Frees a separation.

Parameters

cmr	CMR environment.
psepa	Pointer to separation.

CMRsepaGetProjection()

CMR_EXPORT 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_EXPORT 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.

CMRsepaTranspose()

CMR_EXPORT CMR_ERROR CMRsepaTranspose	(	CMR *	cmr,
		CMR_SEPA *	sepa,
		CMR_SEPA **	ptransposed
	)

Transposes a given separation.

Parameters

cmr	CMR environment.
sepa	Given separation.
ptransposed	Pointer for storing the transpose of sepa.

CMRthreesumCompose()

CMR_EXPORT CMR_ERROR CMRthreesumCompose	(	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 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 (otherwise, CMR_ERROR_STRUCTURE is returned). 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.

CMRthreesumDecomposeFirst()

CMR_EXPORT CMR_ERROR CMRthreesumDecomposeFirst	(	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 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 can be computed by CMRthreesumDecomposeSearchConnecting.

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

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.

CMRthreesumDecomposeSearchConnecting()

CMR_EXPORT CMR_ERROR CMRthreesumDecomposeSearchConnecting	(	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 3-sum according to the 3-separation sepa, searching a suitable 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 CMRthreesumDecomposeFirst and CMRthreesumDecomposeSecond, respectively. If only \( \beta \) and \( \gamma \) shall be computed for given \( i,j,k,\ell \) then CMRthreesumDecomposeSignConnecting can be used.

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.

CMRthreesumDecomposeSecond()

CMR_EXPORT CMR_ERROR CMRthreesumDecomposeSecond	(	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 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 can be computed by CMRthreesumDecomposeSearchConnecting.

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

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.

CMRthreesumDecomposeSignConnecting()

CMR_EXPORT CMR_ERROR CMRthreesumDecomposeSignConnecting	(	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 3-sum according to the 3-separation sepa, searching a suitable 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 tries to compute values for \( \beta \) and \( \gamma \) for given indices \( i,j,k,\ell \) if this is possible. If the latter are not known, CMRthreesumDecomposeSearchConnecting can be used. In either case, the matrices \( M_1 \) and \( M_2 \) can be computed by CMRthreesumDecomposeFirst and CMRthreesumDecomposeSecond, 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 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 \).
pgamma	Pointer for storing a correct value of \( \gamma \); may be NULL.
pbeta	Pointer for storing a correct value of \( \beta \); may be NULL.

CMRtwosumCompose()

CMR_EXPORT 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_EXPORT 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_EXPORT 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 \).

CMRysumCompose()

CMR_EXPORT CMR_ERROR CMRysumCompose	(	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 Y-sum of the two matrices first and second.

Let \( M_1 \) and \( M_2 \) denote the matrices given by first and second, let \( A \) be the matrix \( M_1 \) without the rows indexed by firstSpecialRows[0] and firstSpecialRows[1] and the column indexed by firstSpecialColumns[0]. After reordering these to be last, \( M_1 \) must be of the form \( M_1 = \begin{bmatrix} A & a \\ c^{\textsf{T}} & 0 \\ c^{\textsf{T}} & \varepsilon \end{bmatrix}, \) where \( \varepsilon \in \{-1,+1 \} \) (otherwise, CMR_ERROR_STRUCTURE is returned). Similarly, let \( D \) be the matrix \( M_2 \) without the rows indexed by secondSpecialRows[0] and secondSpecialRows[1] the column secondSpecialColumns[0]. After reordering these to be first, \( M_2 \) must be of the form \( M_2 = \begin{bmatrix} \varepsilon & b^{\textsf{T}} \\ 0 & b^{\textsf{T}} \\ d & D \end{bmatrix} \) with the same \( \varepsilon \) (otherwise, CMR_ERROR_STRUCTURE is returned). The Y-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 2 with row indices of \( \begin{bmatrix} c^{\textsf{T}} & 0 \end{bmatrix} \) and \( \begin{bmatrix} c^{\textsf{T}} & \varepsilon \end{bmatrix} \) in \( M_1 \).
firstSpecialColumns	Array of length 1 with row index of \( \begin{bmatrix} a \\ 0 \\ \varepsilon \end{bmatrix} \) in \( M_1 \).
secondSpecialRows	Array of length 2 with row indices of \( b^{\textsf{T}} \) \( \begin{bmatrix} \varepsilon & b^{\textsf{T}} \end{bmatrix} \) and \( \begin{bmatrix} 0 & b^{\textsf{T}} \end{bmatrix} \) in \( M_2 \).
secondSpecialColumns	Array of length 1 with column index \( \begin{bmatrix} \varepsilon \\ 0 \\ d \end{bmatrix} \) in \( M_2 \).
characteristic	Field characteristic.
presult	Pointer for storing the result.

CMRysumDecomposeEpsilon()

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

Decomposes matrix as a Y-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 Y-sum are matrices \( M_1 = \begin{bmatrix} A & a \\ c^{\textsf{T}} & 0 \\ c^{\textsf{T}} & \varepsilon \end{bmatrix} \) and \( M_2 = \begin{bmatrix} \varepsilon & b^{\textsf{T}} \\ 0 & b^{\textsf{T}} \\ 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 CMRysumDecomposeFirst and CMRysumDecomposeSecond, 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 \).

CMRysumDecomposeFirst()

CMR_EXPORT CMR_ERROR CMRysumDecomposeFirst	(	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 Y-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 Y-sum are matrices \( M_1 = \begin{bmatrix} A & a \\ c^{\textsf{T}} & 0 \\ c^{\textsf{T}} & \varepsilon \end{bmatrix} \) and \( M_2 = \begin{bmatrix} \varepsilon & b^{\textsf{T}} \\ 0 & b^{\textsf{T}} \\ 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 CMRysumDecomposeEpsilon.

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

If firstSpecialRows is not NULL, then firstSpecialRows[0] will refer to the second-to-last row and firstSpecialRows[1] will refer to the last row of \( M_1 \). If firstSpecialColumns is not NULL, then firstSpecialColumns[0] 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 2 for storing the row indices of \( \begin{bmatrix} c^{\textsf{T}} & 0 \end{bmatrix} \) and \( \begin{bmatrix} c^{\textsf{T}} & \varepsilon \end{bmatrix} \) in \( M_1 \); may be NULL.
firstSpecialColumns	Array of length 1 for storing the column index of \( \begin{bmatrix} a \\ 0 \\ \varepsilon \end{bmatrix} \) in \( M_1 \); may be NULL.

CMRysumDecomposeSecond()

CMR_EXPORT CMR_ERROR CMRysumDecomposeSecond	(	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 Y-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 Y-sum are matrices \( M_1 = \begin{bmatrix} A & a \\ c^{\textsf{T}} & 0 \\ c^{\textsf{T}} & \varepsilon \end{bmatrix} \) and \( M_2 = \begin{bmatrix} \varepsilon & b^{\textsf{T}} \\ 0 & b^{\textsf{T}} \\ 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 CMRysumDecomposeEpsilon.

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

If secondSpecialRows is not NULL, then secondSpecialRows[0] will refer to the first row and secondSpecialRows[1] will refer to the second column of \( M_2 \). If secondSpecialColumns is not NULL, then secondSpecialColumns[0] will refer to the first 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 2 for storing the row indices of \( \begin{bmatrix} \varepsilon & b^{\textsf{T}} \end{bmatrix} \) and \( \begin{bmatrix} 0 & b^{\textsf{T}} \end{bmatrix} \) in \( M_2 \); may be NULL.
secondSpecialColumns	Array of length 1 for storing the column index of \( \begin{bmatrix} \varepsilon \\ 0 \\ d \end{bmatrix} \) in \( M_2 \); may be NULL.