compress_parms.c File Reference

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

Defines
#define	dbgCompParm 0
	Id compress_parms.c,v 1.32 2006/11/03 17:34:26 skimo Exp
#define	dbgCompParmMore 0
#define	dbgStart(a)
#define	dbgEnd(a)
Functions
Matrix *	int_ker (Matrix *M)
	Given a full-row-rank nxm matrix M made of m row-vectors), computes the basis K (made of n-m column-vectors) of the integer kernel of the rows of M so we have: M.K = 0.
static void	linearInter (Matrix A, Matrix B, Matrix I, Matrix Lb)
	Computes the intersection of two linear lattices, whose base vectors are respectively represented in A and B.
void	Equalities_integerSolution (Matrix Eqs, Matrix *I)
	Given a system of 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	Constraints_removeElimCols (Matrix M, unsigned int nbVars, unsigned int elimParms, Matrix **newM)
	Eliminate the columns corresponding to a list of eliminated parameters.
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).
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.
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.
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).
Matrix *	int_mod_basis (Matrix B, Matrix C, Matrix *d)
	kept here for backwards compatiblity.
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).
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.
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 *	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.

Define Documentation

#define dbgCompParm 0

Id: compress_parms.c,v 1.32 2006/11/03 17:34:26 skimo Exp

The integer points in a parametric linear subspace of Q^n are generally lying on a sub-lattice of Z^n. Functions here use and compute validity lattices, i.e. lattices induced on a set of variables by such equalities involving another set of integer variables.

Author:: B. Meister 12/2003-2006 meister@icps.u-strasbg.fr LSIIT -ICPS UMR 7005 CNRS Louis Pasteur University (ULP), Strasbourg, France debug flags (2 levels)

Definition at line 38 of file compress_parms.c.

Referenced by Constraints_fullDimensionize(), Equalities_integerSolution(), Equalities_validityLattice(), full_dimensionize(), int_ker(), and linearInter().

#define dbgCompParmMore 0

Definition at line 39 of file compress_parms.c.

Referenced by Constraints_fullDimensionize(), Equalities_integerSolution(), int_ker(), and Lattice_extractSubLattice().

#define dbgEnd ( a )

Value:

if (dbgCompParmMore) { printf(" -- end "); \
                                         printf(#a);      \
                                         printf(" --\n"); } \
                                         while(0)

Definition at line 45 of file compress_parms.c.

Referenced by Lattice_extractSubLattice().

#define dbgStart ( a )

Value:

if (dbgCompParmMore) { printf(" -- begin "); \
                                           printf(#a);        \
                                           printf(" --\n"); }   \
                                           while(0)

Definition at line 41 of file compress_parms.c.

Referenced by Lattice_extractSubLattice().

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:

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.
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
	)

Eliminate 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 equalities, looks if it has an integer solution in the combined space, and if yes, returns one solution.

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.

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. 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 m row-vectors), computes the basis K (made of n-m column-vectors) of the integer kernel of the rows of M so we have: M.K = 0.

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.

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().

static void linearInter	(	Matrix *	A,
		Matrix *	B,
		Matrix **	I,
		Matrix **	Lb
	)			`[static]`

Computes the intersection of two linear lattices, whose base vectors are respectively represented in A and B.

If I and/or Lb is set to NULL, then the matrix is allocated. Else, the matrix is assumed to be allocated already. I and Lb are rk x rk, where rk is the rank of A (or B).

Parameters:

	A	the full-row rank matrix whose column-vectors are the basis for the first linear lattice.
	B	the matrix whose column-vectors are the basis for the second linear lattice.
	Lb	the matrix such that B.Lb = I, where I is the intersection.

Returns:: their intersection.

Definition at line 119 of file compress_parms.c.

References assert, dbgCompParm, left_hermite(), Matrix_Alloc(), Matrix_copySubMatrix(), Matrix_Free(), Matrix_subMatrix(), matrix::NbColumns, matrix::NbRows, matrix::p, show_matrix, value_set_si, and value_zero_p.

Referenced by Equalities_validityLattice().

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().

compress_parms.c File Reference

Defines

Functions

Define Documentation

Function Documentation