separation_internal.h File Reference

#include <cmr/matrix.h>

Go to the source code of this file.

Functions
CMR_EXPORT CMR_ERROR	CMRthreesumDecomposeSearch (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 3-sum.

Function Documentation

CMRthreesumDecomposeSearch()

CMR_EXPORT CMR_ERROR CMRthreesumDecomposeSearch	(	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 3-sum.

See CMRthreesumDecomposeConnecting 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.