CMR
1.3.0
|
#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... | |
|
static |
Implementation of CMRsepaCheckTernary
and CMRsepaCheckTernarySubmatrix
.
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 ). |
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
.
cmr | CMR environment. |
first | First matrix. |
second | Second matrix. |
presult | Pointer for storing the result. |
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.
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 ). |
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
.
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 ). |
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.
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. |
Creates a 2- or 3-separation.
Only the memory is allocated. The rowsFlags and columnsFlags arrays must be filled properly.
cmr | CMR environment. |
numRows | Number of rows. |
numColumns | Number of columns. |
psepa | Pointer for storing the created separation. |
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.
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 ). |
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.
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 ). |
Frees a separation.
cmr | CMR environment. |
psepa | Pointer to separation. |
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.
sepa | Separation. |
part | Part to project. |
rowsToPart | Array for storing the mapping from rows to those of part . |
columnsToPart | Array for storing the mapping from columns to those of part . |
pnumPartRows | Pointer for storing the number of rows of part (excluding representatives). |
pnumPartColumns | Pointer for storing the number of columns of part (excluding representatives). |
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.
cmr | CMR environment. |
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. |
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
.
cmr | CMR environment. |
first | First matrix. |
second | Second matrix. |
firstMarker1 | First marker element of first matrix. |
secondMarker1 | Second marker element of first matrix. |
firstMarker2 | First marker element of second matrix. |
secondMarker2 | Second marker element of second matrix. |
characteristic | Field characteristic. |
presult | Pointer for storing the result. |
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
.
cmr | CMR environment. |
first | First matrix. |
second | Second matrix. |
firstMarker | Marker element of first matrix. |
secondMarker | Marker element of second matrix. |
characteristic | Field characteristic. |
presult | Pointer for storing the result. |
|
static |
Compute the binary and ternary of a submatrix of matrix
(if at most 2).
Update indicator columns.
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 ). |
|
static |
Implementation of CMRsepaFindBinaryRepresentatives and CMRsepaFindBinaryRepresentativesSubmatrix.
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 ). |