CMR  1.3.0
Classes | Functions
separation.c File Reference
#include <cmr/separation.h>
#include "env_internal.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 *cmr, 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 CMRoneSum (CMR *cmr, CMR_CHRMAT *first, CMR_CHRMAT *second, CMR_CHRMAT **presult)
 Constructs the 1-sum of the two matrices first and second. More...
 
CMR_ERROR CMRtwoSum (CMR *cmr, CMR_CHRMAT *first, CMR_CHRMAT *second, CMR_ELEMENT firstMarker, CMR_ELEMENT secondMarker, int8_t characteristic, CMR_CHRMAT **presult)
 Constructs the 2-sum of the two matrices first and second via firstMarker and secondMarker. More...
 
CMR_ERROR CMRthreeSum (CMR *cmr, CMR_CHRMAT *first, CMR_CHRMAT *second, CMR_ELEMENT firstMarker1, CMR_ELEMENT secondMarker1, CMR_ELEMENT firstMarker2, CMR_ELEMENT secondMarker2, int8_t characteristic, CMR_CHRMAT **presult)
 Constructs the 3-sum of the two matrices first and second via firstMarker1, firstMarker2, secondMarker1 and secondMarker2. 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
cmrCMR environment.
sepaSeparation.
matrixMatrix.
submatrixRowsArray mapping a submatrix row to a row of matrix.
columnsToSubmatrixColumnArray mapping a column of matrix to a column of the submatrix or NULL.
pisTernaryPointer for storing whether the check passed.
pviolatorPointer for storing a violator submatrix (may be NULL).

◆ CMRoneSum()

CMR_ERROR CMRoneSum ( CMR cmr,
CMR_CHRMAT first,
CMR_CHRMAT second,
CMR_CHRMAT **  presult 
)

Constructs the 1-sum of the two matrices first and second.

Let \( A \) and \( B \) denote the matrices given by first and second. Their 2-sum is the matrix

\[ C := \begin{pmatrix} A & \mathbb{O} \\ \mathbb{O} & B \end{pmatrix}. \]

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

Parameters
cmrCMR environment.
firstFirst matrix.
secondSecond matrix.
presultPointer 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
cmrCMR environment.
sepaSeparation.
matrixMatrix.
pisTernaryPointer for storing whether the check passed.
pviolatorPointer 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
cmrCMR environment.
sepaSeparation.
matrixMatrix.
submatrixSubmatrix to consider.
pisTernaryPointer for storing whether the check passed.
pviolatorPointer 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
sepaSeparation.
pnumRowsTopLeftPointer for storing the number of rows of the top-left part.
pnumColumnsTopLeftPointer for storing the number of columns of the top-left part.
pnumRowsBottomRightPointer for storing the number of rows of the bottom-right part.
pnumColumnsBottomRightPointer 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
cmrCMR environment.
numRowsNumber of rows.
numColumnsNumber of columns.
psepaPointer 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
cmrCMR environment.
sepaSeparation.
matrixMatrix.
transposeTranspose of matrix.
pswappedPointer for storing whether parts were swapped (may be NULL).
pviolatorPointer 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
cmrCMR environment.
sepaSeparation.
matrixMatrix.
transposeTranspose of matrix.
submatrixSubmatrix of matrix.
pswappedPointer for storing whether parts were swapped (may be NULL).
pviolatorPointer 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
cmrCMR environment.
psepaPointer 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
sepaSeparation.
partPart to project.
rowsToPartArray for storing the mapping from rows to those of part.
columnsToPartArray for storing the mapping from columns to those of part.
pnumPartRowsPointer for storing the number of rows of part (excluding representatives).
pnumPartColumnsPointer for storing the number of columns of part (excluding representatives).

◆ CMRsepaGetRepresentatives()

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

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

Parameters
cmrCMR environment.
sepaSeparation.
reprRowsArray mapping child to arrays of (at most 3) different representative rows.
reprColumnsArray mapping child to arrays of (at most 3) different representative columns.

◆ CMRthreeSum()

CMR_ERROR CMRthreeSum ( CMR cmr,
CMR_CHRMAT first,
CMR_CHRMAT second,
CMR_ELEMENT  firstMarker1,
CMR_ELEMENT  secondMarker1,
CMR_ELEMENT  firstMarker2,
CMR_ELEMENT  secondMarker2,
int8_t  characteristic,
CMR_CHRMAT **  presult 
)

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

Let \( A \) and \( B \) denote the matrices given by first and second, let \( A' \) be the matrix \( A \) without the rows or columns indexed by firstMarker1 and firstMarker2, and let \( B' \) be the matrix \( B \) without the rows or columns indexed by secondMarker1 and secondMarker2. If firstMarker1 and firstMarker2 both index row vectors \( a_1^{\textsf{T}}, a_2^{\textsf{T}} \) of \( A \) then secondMarker1 and secondMarker2 must index column vectors \( b_1, b_2 \) of \( B \). In this case the 3-sum is the matrix

\[ C := \begin{pmatrix} A' & \mathbb{O} \\ b_1 a_1^{\textsf{T}} + b_2 a_2^{\textsf{T}} & B' \end{pmatrix}. \]

Otherwise, if firstMarker1 and firstMarker2 both index column vectors \( a_1, a_2 \) of \( A \) then secondMarker1 and secondMarker2 must index row vectors \( b_1^{\textsf{T}}, b_2^{\textsf{T}} \) of \( B \). In this case the 3-sum is the matrix

\[ C := \begin{pmatrix} A' & a_1 b_1^{\textsf{T}} + a_2 b_2^{\textsf{T}} \\ \mathbb{O} & B' \end{pmatrix}. \]

Otherwise, if firstMarker1 indexes a row vector \( a_1^{\textsf{T}} \) and firstMarker2 indexes a column vector \( a_2 \) of \( A \) then secondMarker1 must index a column vector \( b_1 \) of \( B \) and secondMarker2 must index a row vector \( b_2^{\textsf{T}} \) of \( B \). In this case the 3-sum is the matrix

\[ C := \begin{pmatrix} A' & a_2 b_2^{\textsf{T}} \\ b_1 a_1^{\textsf{T}} & B' \end{pmatrix}. \]

The remaining case is identical to the previous one, except that firstMarker1 and firstMarker2 as well as secondMarker1 and secondMarker2 change roles. The calculations are done modulo characteristic, where the value \( 3 \) yields numbers from \( \{-1,0,+1\} \).

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

Parameters
cmrCMR environment.
firstFirst matrix.
secondSecond matrix.
firstMarker1First marker element of first matrix.
secondMarker1Second marker element of first matrix.
firstMarker2First marker element of second matrix.
secondMarker2Second marker element of second matrix.
characteristicField characteristic.
presultPointer for storing the result.

◆ CMRtwoSum()

CMR_ERROR CMRtwoSum ( CMR cmr,
CMR_CHRMAT first,
CMR_CHRMAT second,
CMR_ELEMENT  firstMarker,
CMR_ELEMENT  secondMarker,
int8_t  characteristic,
CMR_CHRMAT **  presult 
)

Constructs the 2-sum of the two matrices first and second via firstMarker and secondMarker.

Let \( A \) and \( B \) denote the matrices given by first and second and let \( A' \) and \( B' \) be these matrices without the row or column indexed by firstMarker and secondMarker, respectively. If firstMarker indexes a row vector \( a^{\textsf{T}} \) of \( A \) then secondMarker must index a column vector \( b \) of \( B \). In this case the 2-sum is the matrix

\[ C := \begin{pmatrix} A' & \mathbb{O} \\ b a^{\textsf{T}} & B' \end{pmatrix}. \]

Otherwise, firstMarker must index a column vector \( a \) of \( A \) and secondMarker must index a row vector \( b^{\textsf{T}} \) of \( B \), and the 2-sum is the matrix

\[ C := \begin{pmatrix} A' & a b^{\textsf{T}} \\ \mathbb{O} & B' \end{pmatrix}. \]

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

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

Parameters
cmrCMR environment.
firstFirst matrix.
secondSecond matrix.
firstMarkerMarker element of first matrix.
secondMarkerMarker element of second matrix.
characteristicField characteristic.
presultPointer for storing the result.

◆ 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
cmrCMR environment.
matrixMatrix.
numRowsNumber of rows.
rowsArray with row indices.
columnsConsideredArray indicating for each column of matrix whether it shall be considered.
rowsFlagsArray of length numRows for storing the flags for representatives.
prankPointer for storing the computed rank.
pviolatorSubmatrixPointer 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
cmrCMR environment.
sepaSeparation.
matrixMatrix.
transposeTranspose of matrix.
submatrixRowsArray mapping a submatrix row to a row of matrix.
submatrixColumnsArray mapping a submatrix column to a column of matrix.
pswappedPointer for storing whether parts were swapped (may be NULL).
pviolatorSubmatrixPointer for storing a violator submatrix if the ternary rank differs **< (may be NULL).