balanced.h File Reference

Recognition of balanced matrices. More...

#include <cmr/env.h>
#include <cmr/matrix.h>
#include <cmr/series_parallel.h>
#include <inttypes.h>

Go to the source code of this file.

Classes
struct	CMR_BALANCED_PARAMS
struct	CMR_BALANCED_STATS
	Statistics for recognition algorithm for balanced matrices. More...

Enumerations
enum	CMR_BALANCED_ALGORITHM { CMR_BALANCED_ALGORITHM_AUTO = 0 , CMR_BALANCED_ALGORITHM_SUBMATRIX = 1 , CMR_BALANCED_ALGORITHM_GRAPH = 2 }

Functions
CMR_EXPORT CMR_ERROR	CMRbalancedParamsInit (CMR_BALANCED_PARAMS *params)
	Initializes the default parameters for recognition of balanced matrices. More...
CMR_EXPORT CMR_ERROR	CMRbalancedStatsInit (CMR_BALANCED_STATS *stats)
	Initializes all statistics for recognition algorithm for balanced matrices. More...
CMR_EXPORT CMR_ERROR	CMRbalancedStatsPrint (FILE *stream, CMR_BALANCED_STATS *stats, const char *prefix)
	Prints statistics for recognition algorithm for balanced matrices. More...
CMR_EXPORT CMR_ERROR	CMRbalancedTest (CMR *cmr, CMR_CHRMAT *matrix, bool *pisBalanced, CMR_SUBMAT **psubmatrix, CMR_BALANCED_PARAMS *params, CMR_BALANCED_STATS *stats, double timeLimit)

Variables
CMR_SP_STATISTICS	seriesParallel
	Tests a matrix \( M \) for being balanced. More...

Detailed Description

Recognition of balanced matrices.

Author

Henk Kraaij and Matthias Walter

Enumeration Type Documentation

CMR_BALANCED_ALGORITHM

enum CMR_BALANCED_ALGORITHM

Enumerator
CMR_BALANCED_ALGORITHM_AUTO	Automatically select a fast algorithm.
CMR_BALANCED_ALGORITHM_SUBMATRIX	Exponential-time enumeration algorithm based on submatrices.
CMR_BALANCED_ALGORITHM_GRAPH	Polynomial-time algorithm based on graphs.

Function Documentation

CMRbalancedParamsInit()

CMR_EXPORT CMR_ERROR CMRbalancedParamsInit

(

CMR_BALANCED_PARAMS *

params

)

Initializes the default parameters for recognition of balanced matrices.

Parameters

params

Pointer to parameters.

CMRbalancedStatsInit()

CMR_EXPORT CMR_ERROR CMRbalancedStatsInit

(

CMR_BALANCED_STATS *

stats

)

Initializes all statistics for recognition algorithm for balanced matrices.

Parameters

stats

Pointer to statistics.

CMRbalancedStatsPrint()

CMR_EXPORT CMR_ERROR CMRbalancedStatsPrint	(	FILE *	stream,
		CMR_BALANCED_STATS *	stats,
		const char *	prefix
	)

Prints statistics for recognition algorithm for balanced matrices.

Parameters

stream	File stream to print to.
stats	Pointer to statistics.
prefix	Prefix string to prepend to each printed line (may be NULL).

CMRbalancedTest()

CMR_EXPORT CMR_ERROR CMRbalancedTest	(	CMR *	cmr,
		CMR_CHRMAT *	matrix,
		bool *	pisBalanced,
		CMR_SUBMAT **	psubmatrix,
		CMR_BALANCED_PARAMS *	params,
		CMR_BALANCED_STATS *	stats,
		double	timeLimit
	)

Parameters

cmr	CMR environment
matrix	Matrix \( M \).
pisBalanced	Pointer for storing whether \( M \) is balanced.
psubmatrix	Pointer for storing a minimal nonbalanced submatrix (may be NULL).
params	Parameters for the computation (may be NULL for defaults).
stats	Statistics for the computation (may be NULL).
timeLimit	Time limit to impose.

Variable Documentation

seriesParallel

CMR_SP_STATISTICS seriesParallel

Tests a matrix \( M \) for being balanced.

Tests if matrix \( M \) is balanced and sets *pisBalanced accordingly. Automatically decides which algorithm to use.

If \( M \) is not balanced and psubmatrix != NULL, then *psubmatrix will indicate a submatrix of \( M \) with exactly two nonzeros in each row and in each column and with determinant \( -2 \) or \( 2 \). Statistics for series-parallel algorithm.