compress_parms.h File Reference

#include "matrix_addon.h"
#include "matrix_permutations.h"
#include <assert.h>

Go to the source code of this file.

Defines
#define	Constraints_removeParmEqs(a, b, c, d)   Constraints_Remove_parm_eqs(a,b,c,d)
#define	Polyhedron_removeParmEqs(a, b, c, d, e)   Polyhedron_Remove_parm_eqs(a,b,c,d,e)
Functions
void	Equalities_integerSolution (Matrix *Eqs, Matrix **sol)
	Given a system of non-redundant equalities, looks if it has an integer solution in the combined space, and if yes, returns one solution.
void	Equalities_validityLattice (Matrix *Eqs, int a, Matrix **vl)
	Computes the validity lattice of a set of equalities.
void	Equalities_intModBasis (Matrix *B, Matrix *C, Matrix *d, Matrix **imb)
	Given an integer matrix B with m rows and integer m-vectors C and d, computes the basis of the integer solutions to (BN+C) mod d = 0 (1).
void	Constraints_fullDimensionize (Matrix **M, Matrix **C, Matrix **VL, Matrix **Eqs, Matrix **ParmEqs, unsigned int **elimVars, unsigned int **elimParms, int maxRays)
	Eliminates all the equalities in a set of constraints and returns the set of constraints defining a full-dimensional polyhedron, such that there is a bijection between integer points of the original polyhedron and these of the resulting (projected) polyhedron).
Matrix *	Constraints_Remove_parm_eqs (Matrix **M, Matrix **Ctxt, int renderSpace, unsigned int **elimParms)
	Removes the equalities that involve only parameters, by eliminating some parameters in the polyhedron's constraints and in the context.
void	Constraints_removeElimCols (Matrix *M, unsigned int nbVars, unsigned int *elimParms, Matrix **newM)
	Eliminates the columns corresponding to a list of eliminated parameters.
void	Lattice_extractSubLattice (Matrix *lat, unsigned int k, Matrix **subLat)
	Given a matrix that defines a full-dimensional affine lattice, returns the affine sub-lattice spanned in the k first dimensions.
Polyhedron *	Polyhedron_Remove_parm_eqs (Polyhedron **P, Polyhedron **C, int renderSpace, unsigned int **elimParms, int maxRays)
	Removes equalities involving only parameters, but starting from a Polyhedron and its context.
Matrix *	int_ker (Matrix *M)
	given a full-row-rank nxm matrix M(made of row-vectors), computes the basis K (made of n-m column-vectors) of the integer kernel of M so we have: M.K = 0
Matrix *	full_dimensionize (Matrix const *M, int nb_parms, Matrix **Validity_Lattice)
	Given a matrix with m parameterized equations, compress the nb_parms parameters and n-m variables so that m variables are integer, and transform the variable space into a n-m space by eliminating the m variables (using the equalities) the variables to be eliminated are chosen automatically by the function.
Matrix *	affine_periods (Matrix *M, Matrix *d)
	Computes the overall period of the variables I for (MI) mod |d|, where M is a matrix and |d| a vector.
Matrix *	int_mod_basis (Matrix *Bp, Matrix *Cp, Matrix *d)
	kept here for backwards compatiblity.
Matrix *	compress_parms (Matrix *E, int nb_parms)
	Given a parameterized constraints matrix with m equalities, computes the compression matrix G such that there is an integer solution in the variables space for each value of N', with N = G N' (N are the "nb_parms" parameters).

---

Define Documentation

#define Constraints_removeParmEqs	(	a,
		b,
		c,
		d		)	Constraints_Remove_parm_eqs(a,b,c,d)

Definition at line 72 of file compress_parms.h.

Referenced by Constraints_fullDimensionize().

#define Polyhedron_removeParmEqs	(	a,
		b,
		c,
		d,
		e		)	Polyhedron_Remove_parm_eqs(a,b,c,d,e)

Definition at line 101 of file compress_parms.h.

---

Function Documentation

Matrix* affine_periods	(	Matrix *	M,
		Matrix *	d
	)

Computes the overall period of the variables I for (MI) mod |d|, where M is a matrix and |d| a vector.

Produce a diagonal matrix S = (s_k) where s_k is the overall period of i_k

Parameters:

	M	the set of affine functions of I (row-vectors)
	d	the column-vector representing the modulos

Definition at line 548 of file compress_parms.c.

References Matrix_Alloc(), matrix::NbColumns, matrix::NbRows, matrix::p, value_assign, value_clear, value_divexact, value_gcd, value_init, value_lcm, and value_set_si.

Matrix* compress_parms	(	Matrix *	E,
		int	nbParms
	)

Given a parameterized constraints matrix with m equalities, computes the compression matrix G such that there is an integer solution in the variables space for each value of N', with N = G N' (N are the "nb_parms" parameters).

Parameters:

	E	a matrix of parametric equalities
	nb_parms	the number of parameters Note: this function is mostly here for backwards compatibility. Prefer the use of Equalities_validityLattice.

Definition at line 630 of file compress_parms.c.

References Equalities_validityLattice(), and matrix::NbColumns.

Referenced by full_dimensionize().

void Constraints_fullDimensionize	(	Matrix **	M,
		Matrix **	C,
		Matrix **	VL,
		Matrix **	Eqs,
		Matrix **	ParmEqs,
		unsigned int **	elimVars,
		unsigned int **	elimParms,
		int	maxRays
	)

Eliminates all the equalities in a set of constraints and returns the set of constraints defining a full-dimensional polyhedron, such that there is a bijection between integer points of the original polyhedron and these of the resulting (projected) polyhedron).

If VL is set to NULL, this funciton allocates it. Else, it assumes that (*VL) points to a matrix of the right size.

The following things are done:

1. remove equalities involving only parameters, and remove as many parameters as there are such equalities. From that, the list of eliminated parameters elimParms is built.
2. remove equalities that involve variables. This requires a compression of the parameters and of the other variables that are not eliminated. The affine compresson is represented by matrix VL (for validity lattice) and is such that (N I 1)^T = VL.(N' I' 1), where N', I' are integer (they are the parameters and variables after compression).

Definition at line 386 of file compress_parms.c.

References assert, Constraints_compressLastVars, Constraints_eliminateFirstVars, Constraints_permute(), Constraints_removeElimCols(), Constraints_removeParmEqs, dbgCompParm, dbgCompParmMore, Equalities_validityLattice(), find_a_permutation(), Matrix_Alloc(), Matrix_Free(), Matrix_identity(), matrix::NbColumns, matrix::NbRows, matrix::p, show_matrix, split_constraints(), value_assign, and value_set_si.

Referenced by test_Constraints_fullDimensionize().

Matrix* Constraints_Remove_parm_eqs	(	Matrix **	M1,
		Matrix **	Ctxt1,
		int	renderSpace,
		unsigned int **	elimParms
	)

Removes the equalities that involve only parameters, by eliminating some parameters in the polyhedron's constraints and in the context.

Updates M and Ctxt.

Parameters:

	M1	the polyhedron's constraints
	Ctxt1	the constraints of the polyhedron's context
	renderSpace	tells if the returned equalities must be expressed in the parameters space (renderSpace=0) or in the combined var/parms space (renderSpace = 1)
	elimParms	the list of parameters that have been removed: an array whose 1st element is the number of elements in the list. (returned)

Returns:

the system of equalities that involve only parameters.

Definition at line 649 of file compress_parms.c.

References eliminate_var_with_constr(), First_Non_Zero(), Matrix_Alloc(), Matrix_Free(), matrix::NbColumns, matrix::NbRows, matrix::p, show_matrix, value_cmp_si, value_notzero_p, value_set_si, value_zero_p, and Vector_Copy().

Referenced by Constraints_EhrhartQuickApx(), Polyhedron_Remove_parm_eqs(), and test_Constraints_Remove_parm_eqs().

void Constraints_removeElimCols	(	Matrix *	M,
		unsigned int	nbVars,
		unsigned int *	elimParms,
		Matrix **	newM
	)

Eliminates the columns corresponding to a list of eliminated parameters.

Eliminates the columns corresponding to a list of eliminated parameters.

Parameters:

	M	the constraints matrix whose columns are to be removed
	nbVars	an offset to be added to the ranks of the variables to be removed
	elimParms	the list of ranks of the variables to be removed
	newM	(output) the matrix without the removed columns

Definition at line 335 of file compress_parms.c.

References assert, Matrix_Alloc(), Matrix_clone(), matrix::NbColumns, matrix::NbRows, matrix::p, value_assign, and Vector_Copy().

Referenced by Constraints_fullDimensionize().

void Equalities_integerSolution	(	Matrix *	Eqs,
		Matrix **	I
	)

Given a system of non-redundant equalities, looks if it has an integer solution in the combined space, and if yes, returns one solution.

Author:

B. Meister 12/2003-2006 LSIIT -ICPS UMR 7005 CNRS Louis Pasteur University (ULP), Strasbourg, France

Given a system of non-redundant equalities, looks if it has an integer solution in the combined space, and if yes, returns one solution.

pre-condition: the equalities are full-row rank (without the constant part)

Parameters:

	Eqs	the system of equations (as constraints)
	I	a feasible integer solution if it exists, else NULL. Allocated if initially set to NULL, else reused.

Definition at line 181 of file compress_parms.c.

References dbgCompParm, dbgCompParmMore, ensureMatrix, left_hermite(), MatInverse(), Matrix_Alloc(), Matrix_Free(), Matrix_oppose(), Matrix_Product(), Matrix_subMatrix(), matrix::NbColumns, matrix::NbRows, matrix::p, show_matrix, value_clear, value_init, value_notzero_p, value_pdivision, value_pmodulus, and value_set_si.

Referenced by Equalities_validityLattice().

void Equalities_intModBasis	(	Matrix *	B,
		Matrix *	C,
		Matrix *	d,
		Matrix **	imb
	)

Given an integer matrix B with m rows and integer m-vectors C and d, computes the basis of the integer solutions to (BN+C) mod d = 0 (1).

This is an affine lattice (G): (N 1)^T= G(N' 1)^T, forall N' in Z^b. If there is no solution, returns NULL.

This is an affine lattice (G): (N 1)^T= G(N' 1)^T, forall N' in Z^b. If there is no solution, returns NULL.

Parameters:

	B	B, a (m x b) matrix
	C	C, a (m x 1) integer matrix
	d	d, a (1 x m) integer matrix
	imb	the affine (b+1)x(b+1) basis of solutions, in the homogeneous form. Allocated if initially set to NULL, reused if not.

Definition at line 592 of file compress_parms.c.

References Equalities_validityLattice(), Matrix_Alloc(), Matrix_copySubMatrix(), Matrix_Free(), matrix::NbColumns, matrix::NbRows, matrix::p, and value_assign.

Referenced by int_mod_basis().

void Equalities_validityLattice	(	Matrix *	Eqs,
		int	a,
		Matrix **	vl
	)

Computes the validity lattice of a set of equalities.

I.e., the lattice induced on the last b variables by the equalities involving the first a integer existential variables.

I.e., the lattice induced on the last b variables by the equalities involving the first a integer existential variables. The submatrix of Eqs that concerns only the existential variables (so the first a columns) is assumed to be full-row rank.

Parameters:

	Eqs	the equalities
	a	the number of existential integer variables, placed as first variables
	vl	the (returned) validity lattice, in homogeneous form. It is allocated if initially set to null, or reused if already allocated.

Definition at line 271 of file compress_parms.c.

References dbgCompParm, ensureMatrix, Equalities_integerSolution(), left_hermite(), linearInter(), Matrix_copySubMatrix(), Matrix_Free(), Matrix_subMatrix(), matrix::NbColumns, matrix::NbRows, show_matrix, value_assign, value_set_si, and Vector_Set().

Referenced by compress_parms(), Constraints_fullDimensionize(), and Equalities_intModBasis().

Matrix* full_dimensionize	(	Matrix const *	M,
		int	nbParms,
		Matrix **	validityLattice
	)

Given a matrix with m parameterized equations, compress the nb_parms parameters and n-m variables so that m variables are integer, and transform the variable space into a n-m space by eliminating the m variables (using the equalities) the variables to be eliminated are chosen automatically by the function.

Deprecated. Try to use Constraints_fullDimensionize instead.

Parameters:

	M	the constraints
	the	number of parameters
	validityLattice	the the integer lattice underlying the integer solutions.

Definition at line 904 of file compress_parms.c.

References compress_parms(), dbgCompParm, find_a_permutation(), Identity_Matrix(), Matrix_Alloc(), Matrix_Free(), mpolyhedron_compress_last_vars(), mpolyhedron_eliminate_first_variables(), mpolyhedron_permute(), matrix::NbColumns, matrix::NbRows, matrix::p, show_matrix, split_constraints(), value_assign, and value_set_si.

Referenced by Ehrhart_Quick_Apx().

Matrix* int_ker

(

Matrix *

M

)

given a full-row-rank nxm matrix M(made of row-vectors), computes the basis K (made of n-m column-vectors) of the integer kernel of M so we have: M.K = 0

Definition at line 56 of file compress_parms.c.

References dbgCompParm, dbgCompParmMore, left_hermite(), Matrix_Alloc(), Matrix_Free(), Matrix_subMatrix(), matrix::NbColumns, matrix::NbRows, matrix::p, right_hermite(), show_matrix, and Vector_IsZero().

Matrix* int_mod_basis	(	Matrix *	B,
		Matrix *	C,
		Matrix *	d
	)

kept here for backwards compatiblity.

Wrapper to Equalities_intModBasis()

Definition at line 614 of file compress_parms.c.

References Equalities_intModBasis().

void Lattice_extractSubLattice	(	Matrix *	lat,
		unsigned int	k,
		Matrix **	subLat
	)

Given a matrix that defines a full-dimensional affine lattice, returns the affine sub-lattice spanned in the k first dimensions.

Useful for instance when you only look for the parameters' validity lattice.

Useful for instance when you only look for the parameters' validity lattice.

Parameters:

	lat	the original full-dimensional lattice
	subLat	the sublattice

Definition at line 499 of file compress_parms.c.

References assert, dbgCompParmMore, dbgEnd, dbgStart, Lattice_extractSubLattice(), left_hermite(), Matrix_Alloc(), Matrix_Copy(), Matrix_copySubMatrix(), Matrix_Free(), Matrix_subMatrix(), matrix::NbColumns, matrix::NbRows, show_matrix, and value_set_si.

Referenced by Lattice_extractSubLattice(), and test_Constraints_fullDimensionize().

Polyhedron* Polyhedron_Remove_parm_eqs	(	Polyhedron **	P,
		Polyhedron **	C,
		int	renderSpace,
		unsigned int **	elimParms,
		int	maxRays
	)

Removes equalities involving only parameters, but starting from a Polyhedron and its context.

Parameters:

	P	the polyhedron
	C	P's context
	renderSpace,:	0 for the parameter space, =1 for the combined space. Polylib's usual workspace.

Definition at line 856 of file compress_parms.c.

References Constraints2Polyhedron(), Constraints_Remove_parm_eqs(), F_ISSET, FL_INIT, Matrix_Free(), matrix::NbRows, POL_INEQUALITIES, POL_NO_DUAL, POL_VALID, Polyhedron2Constraints(), and Polyhedron_Free().

Referenced by test_Polyhedron_Remove_parm_eqs().