matrix_addon.h File Reference

#include <polylib/polylib.h>
#include <assert.h>

Defines
#define	show_matrix(M)
	Polylib matrix addons Mainly, deals with polyhedra represented in implicit form (set of constraints).
#define	ensureMatrix(M, r, c)
	Allocates a matrix if it is null, or else asserts that it has at least a certain size.
#define	Constraints_compressLastVars(a, b) mpolyhedron_compress_last_vars(a, b)
#define	Constraints_eliminateFirstVars(a, b) mpolyhedron_eliminate_first_variables(a,b)
Functions
Matrix *	constraintsView (Polyhedron *P)
	Id matrix_addon.c,v 1.17 2007/03/18 18:49:08 skimo Exp
void	constraintsView_Free (Matrix *M)
	"Frees" a view of the constraints of a polyhedron
void	split_constraints (Matrix const M, Matrix Eqs, Matrix *Ineqs)
	splits a matrix of constraints M into a matrix of equalities Eqs and a matrix of inequalities Ineqs allocs the new matrices.
Matrix *	Identity_Matrix (unsigned int dim)
void	Matrix_identity (unsigned int dim, Matrix **I)
	returns the dim-dimensional identity matrix.
void	mtransformation_inverse (Matrix transf, Matrix inv, Value g)
	given a n x n integer transformation matrix transf, compute its inverse M/g, where M is a nxn integer matrix.
void	mpolyhedron_simplify (Matrix *polyh)
	simplify a matrix seen as a polyhedron, by dividing its rows by the gcd of their elements.
void	mpolyhedron_inflate (Matrix *polyh, unsigned int nb_parms)
	inflates a polyhedron (represented as a matrix) P, so that the apx of its Ehrhart Polynomial is an upper bound of the Ehrhart polynomial of P WARNING: this inflation is supposed to be applied on full-dimensional polyhedra.
void	mpolyhedron_deflate (Matrix *polyh, unsigned int nb_parms)
	deflates a polyhedron (represented as a matrix) P, so that the apx of its Ehrhart Polynomial is a lower bound of the Ehrhart polynomial of P WARNING: this deflation is supposed to be applied on full-dimensional polyhedra.
void	eliminate_var_with_constr (Matrix Eliminator, unsigned int eliminator_row, Matrix Victim, unsigned int victim_row, unsigned int var_to_elim)
	use an eliminator row to eliminate a variable in a victim row (without changing the sign of the victim row -> important if it is an inequality).
void	mpolyhedron_compress_last_vars (Matrix M, Matrix compression)
	compress the last vars/pars of the polyhedron M expressed as a polylib matrix adresses the full-rank compressions only modfies M
unsigned int	mpolyhedron_eliminate_first_variables (Matrix Eqs, Matrix Ineqs)
	use a set of m equalities Eqs to eliminate m variables in the polyhedron Ineqs represented as a matrix eliminates the m first variables assumes that Eqs allow to eliminate the m equalities modifies Eqs and Ineqs
void	Matrix_subMatrix (Matrix M, unsigned int sr, unsigned int sc, unsigned int nbR, unsigned int nbC, Matrix *sub)
	returns a contiguous submatrix of a matrix.
void	Matrix_clone (Matrix M, Matrix *Cl)
	Cloning function.
void	Matrix_copySubMatrix (Matrix M1, unsigned int sr1, unsigned int sc1, unsigned int nbR, unsigned int nbC, Matrix M2, unsigned int sr2, unsigned int sc2)
	Copies a contiguous submatrix of M1 into M2, at the indicated position.
void	Matrix_oppose (Matrix *M)
	given a matrix M into -M

Define Documentation

#define Constraints_compressLastVars	(	a,
		b		)	mpolyhedron_compress_last_vars(a, b)

Definition at line 94 of file matrix_addon.h.

Referenced by Constraints_fullDimensionize().

#define Constraints_eliminateFirstVars	(	a,
		b		)	mpolyhedron_eliminate_first_variables(a,b)

Definition at line 102 of file matrix_addon.h.

Referenced by Constraints_fullDimensionize().

#define ensureMatrix	(	M,
		r,
		c	)

Value:

{ if (M==NULL) M = Matrix_Alloc(r,c); \
                                else assert (M->NbRows>=r && M->NbColumns>=c); \
                              }

Allocates a matrix if it is null, or else asserts that it has at least a certain size.

Definition at line 41 of file matrix_addon.h.

Referenced by Equalities_integerSolution(), and Equalities_validityLattice().

#define show_matrix ( M )

Value:

{ printf(#M"= \n"); \
                         if (M!=NULL) { \
                         Matrix_Print(stderr,P_VALUE_FMT,(M));} \
                         else {printf("<NULL>\n");} \
                       }

Polylib matrix addons Mainly, deals with polyhedra represented in implicit form (set of constraints).

Author:: Benoit Meister Shortcut for Matrix_Print

Definition at line 32 of file matrix_addon.h.

Referenced by Constraints_fullDimensionize(), Constraints_Remove_parm_eqs(), Ehrhart_Quick_Apx(), Equalities_integerSolution(), Equalities_validityLattice(), full_dimensionize(), int_ker(), Lattice_extractSubLattice(), LexSmaller(), linearInter(), main(), test_Constraints_fullDimensionize(), and test_Constraints_Remove_parm_eqs().

Function Documentation

Matrix* constraintsView ( Polyhedron * P )

Id: matrix_addon.c,v 1.17 2007/03/18 18:49:08 skimo Exp

Polylib matrix addons Mainly, deals with polyhedra represented as a matrix (implicit form)

Author:: Benoit Meister <meister@icps.u-strasbg.fr> Creates a view of the constraints of a polyhedron as a Matrix *

Definition at line 32 of file matrix_addon.c.

References polyhedron::Constraint, polyhedron::Dimension, matrix::NbColumns, polyhedron::NbConstraints, matrix::NbRows, and matrix::p.

void constraintsView_Free ( Matrix * M )

"Frees" a view of the constraints of a polyhedron

Definition at line 41 of file matrix_addon.c.

void eliminate_var_with_constr	(	Matrix *	Eliminator,
		unsigned int	eliminator_row,
		Matrix *	Victim,
		unsigned int	victim_row,
		unsigned int	var_to_elim
	)

use an eliminator row to eliminate a variable in a victim row (without changing the sign of the victim row -> important if it is an inequality).

Parameters:

	Eliminator	the matrix containing the eliminator row
	eliminator_row	the index of the eliminator row in `Eliminator`
	Victim	the matrix containing the row to be eliminated
	victim_row	the row to be eliminated in `Victim`
	var_to_elim	the variable to be eliminated.

Definition at line 241 of file matrix_addon.c.

References matrix::NbColumns, matrix::p, value_addto, value_clear, value_division, value_init, value_lcm, value_multiply, value_notzero_p, value_oppose, and value_pos_p.

Referenced by Constraints_Remove_parm_eqs(), and mpolyhedron_eliminate_first_variables().

Matrix* Identity_Matrix ( unsigned int dim )

Definition at line 80 of file matrix_addon.c.

References Matrix_Alloc(), matrix::p, and value_set_si.

Referenced by full_dimensionize(), Matrix_identity(), and mtransformation_expand_left_to_dim().

void Matrix_clone	(	Matrix *	M,
		Matrix **	Cl
	)

Cloning function.

Similar to Matrix_Copy() but allocates the target matrix if it is set to NULL.

Definition at line 377 of file matrix_addon.c.

References Matrix_subMatrix(), matrix::NbColumns, and matrix::NbRows.

Referenced by Constraints_removeElimCols().

void Matrix_copySubMatrix	(	Matrix *	M1,
		unsigned int	sr1,
		unsigned int	sc1,
		unsigned int	nbR,
		unsigned int	nbC,
		Matrix *	M2,
		unsigned int	sr2,
		unsigned int	sc2
	)

Copies a contiguous submatrix of M1 into M2, at the indicated position.

M1 and M2 are assumed t be allocated already.

Parameters:

	M1	the source matrix
	sr1	the starting source row
	sc1	the starting source column
	nbR	the number of rows
	nbC	the number of columns
	M2	the target matrix
	sr2	the starting target row
	sc2	the starting target column

Definition at line 394 of file matrix_addon.c.

References matrix::p, and Vector_Copy().

Referenced by Equalities_intModBasis(), Equalities_validityLattice(), Lattice_extractSubLattice(), and linearInter().

void Matrix_identity	(	unsigned int	dim,
		Matrix **	I
	)

returns the dim-dimensional identity matrix.

If I is set to NULL, allocates it first. Else, assumes an existing, allocated Matrix.

Definition at line 99 of file matrix_addon.c.

References assert, Identity_Matrix(), and value_set_si.

Referenced by Constraints_fullDimensionize().

void Matrix_oppose ( Matrix * M )

given a matrix M into -M

Definition at line 409 of file matrix_addon.c.

References matrix::NbColumns, matrix::NbRows, matrix::p, and value_oppose.

Referenced by Equalities_integerSolution().

void Matrix_subMatrix	(	Matrix *	M,
		unsigned int	sr,
		unsigned int	sc,
		unsigned int	er,
		unsigned int	ec,
		Matrix **	sub
	)

returns a contiguous submatrix of a matrix.

Parameters:

	M	the input matrix
	sr	the index of the starting row
	sc	the index of the starting column
	er	the index ofthe ending row (excluded)
	ec	the ined of the ending colummn (excluded)
	sub	(returned), the submatrix. Allocated if set to NULL, assumed to be already allocated else.

Definition at line 357 of file matrix_addon.c.

References assert, Matrix_Alloc(), matrix::p, and Vector_Copy().

Referenced by Equalities_integerSolution(), Equalities_validityLattice(), int_ker(), Lattice_extractSubLattice(), linearInter(), and Matrix_clone().

void mpolyhedron_compress_last_vars	(	Matrix *	M,
		Matrix *	compression
	)

compress the last vars/pars of the polyhedron M expressed as a polylib matrix

adresses the full-rank compressions only
modfies M

Definition at line 293 of file matrix_addon.c.

References assert, Matrix_Alloc(), Matrix_Free(), matrix::NbColumns, matrix::NbRows, matrix::p, value_addmul, value_assign, and value_set_si.

Referenced by Ehrhart_Quick_Apx(), and full_dimensionize().

void mpolyhedron_deflate	(	Matrix *	polyh,
		unsigned int	nb_parms
	)

deflates a polyhedron (represented as a matrix) P, so that the apx of its Ehrhart Polynomial is a lower bound of the Ehrhart polynomial of P WARNING: this deflation is supposed to be applied on full-dimensional polyhedra.

Definition at line 213 of file matrix_addon.c.

References matrix::NbColumns, matrix::NbRows, matrix::p, value_addto, value_clear, value_init, value_pos_p, value_set_si, and value_subtract.

Referenced by main().

unsigned int mpolyhedron_eliminate_first_variables	(	Matrix *	Eqs,
		Matrix *	Ineqs
	)

use a set of m equalities Eqs to eliminate m variables in the polyhedron Ineqs represented as a matrix eliminates the m first variables

assumes that Eqs allow to eliminate the m equalities
modifies Eqs and Ineqs

Definition at line 321 of file matrix_addon.c.

References eliminate_var_with_constr(), matrix::NbRows, matrix::p, value_cmp_si, and value_set_si.

Referenced by full_dimensionize().

void mpolyhedron_inflate	(	Matrix *	polyh,
		unsigned int	nb_parms
	)

inflates a polyhedron (represented as a matrix) P, so that the apx of its Ehrhart Polynomial is an upper bound of the Ehrhart polynomial of P WARNING: this inflation is supposed to be applied on full-dimensional polyhedra.

Definition at line 190 of file matrix_addon.c.

References matrix::NbColumns, matrix::NbRows, matrix::p, value_addto, value_clear, value_init, value_neg_p, value_set_si, and value_subtract.

Referenced by main().

void mpolyhedron_simplify ( Matrix * polyh )

simplify a matrix seen as a polyhedron, by dividing its rows by the gcd of their elements.

Definition at line 172 of file matrix_addon.c.

References matrix::NbColumns, matrix::NbRows, matrix::p, value_clear, value_init, value_print, Vector_AntiScale(), and Vector_Gcd().

void mtransformation_inverse	(	Matrix *	transf,
		Matrix **	inverse,
		Value *	g
	)

given a n x n integer transformation matrix transf, compute its inverse M/g, where M is a nxn integer matrix.

g is a common denominator for elements of (transf^{-1})

Definition at line 123 of file matrix_addon.c.

References MatInverse(), Matrix_Alloc(), Matrix_Copy(), Matrix_Free(), matrix::NbColumns, matrix::NbRows, matrix::p, value_clear, value_division, value_init, value_lcm, value_multiply, and value_set_si.

void split_constraints	(	Matrix const *	M,
		Matrix **	Eqs,
		Matrix **	Ineqs
	)

splits a matrix of constraints M into a matrix of equalities Eqs and a matrix of inequalities Ineqs allocs the new matrices.

Allocates Eqs and Ineqs.

Definition at line 50 of file matrix_addon.c.

References Matrix_Alloc(), matrix::NbColumns, matrix::NbRows, matrix::p, value_assign, and value_zero_p.

Referenced by Constraints_fullDimensionize(), and full_dimensionize().

matrix_addon.h File Reference

Defines

Functions

Define Documentation

Function Documentation