Data Structures
struct	Pmatrix
	package matrice More...

Macros
#define	MATRIX_UNDEFINED ((Pmatrix) NULL)

#define	matrix_free(m) (free(m), (m)=(Pmatrix) NULL)
	Allocation et desallocation d'une matrice. More...

#define	MATRIX_ELEM(matrix, i, j) ((matrix)->coefficients[(((j)-1)*((matrix)->number_of_lines))+((i)-1)])
	Macros d'acces aux elements d'une matrice. More...

#define	MATRIX_DENOMINATOR(matrix) ((matrix)->denominator)
	int MATRIX_DENONIMATOR(matrix): acces au denominateur global d'une matrice matrix More...

#define	MATRIX_NB_LINES(matrix) ((matrix)->number_of_lines)

#define	MATRIX_NB_COLUMNS(matrix) ((matrix)->number_of_columns)

#define	matrix_triangular_inferieure_p(a) matrix_triangular_p(a, true)
	bool matrix_triangular_inferieure_p(matrice a): test de triangularite de la matrice a More...

#define	matrix_triangular_superieure_p(a) matrix_triangular_p(a, false)
	bool matrix_triangular_superieure_p(matrice a, int n, int m): test de triangularite de la matrice a More...

#define	SUB_MATRIX_ELEM(matrix, i, j, level)
	MATRIX_RIGHT_INF_ELEM Permet d'acceder des sous-matrices dont le coin infe'rieur droit (i.e. More...

Typedefs
typedef struct Pmatrix	Smatrix

Functions
Pmatrix	matrix_new (int, int)
	cproto-generated files More...

void	matrix_rm (Pmatrix)

void	matrix_determinant (Pmatrix, Value[])
	determinant.c More...

void	matrix_sub_determinant (Pmatrix, int, int, Value[])

void	matrix_hermite (Pmatrix, Pmatrix, Pmatrix, Pmatrix, Value , Value )
	hermite.c More...

int	matrix_hermite_rank (Pmatrix)
	int matrix_hermite_rank(Pmatrix a): rang d'une matrice en forme de hermite More...

int	matrix_dim_hermite (Pmatrix)
	Calcul de la dimension de la matrice de Hermite H. More...

void	matrix_unimodular_triangular_inversion (Pmatrix, Pmatrix, bool)
	inversion.c More...

void	matrix_diagonal_inversion (Pmatrix, Pmatrix)
	void matrix_diagonal_inversion(Pmatrix s,Pmatrix inv_s) calcul de l'inversion du matrice en forme reduite smith. More...

void	matrix_triangular_inversion (Pmatrix, Pmatrix, bool)
	void matrix_triangular_inversion(Pmatrix h, Pmatrix inv_h,bool infer) calcul de l'inversion du matrice en forme triangulaire. More...

void	matrix_general_inversion (Pmatrix, Pmatrix)
	void matrix_general_inversion(Pmatrix a; Pmatrix inv_a) calcul de l'inversion du matrice general. More...

void	matrix_unimodular_inversion (Pmatrix, Pmatrix)
	void matrix_unimodular_inversion(Pmatrix u, Pmatrix inv_u) calcul de l'inversion de la matrice unimodulaire. More...

Value *	matrix_elem_ref (Pmatrix, int, int)
	matrix.c More...

Value	matrix_elem (Pmatrix, int, int)

void	matrix_transpose (const Pmatrix, Pmatrix)
	void matrix_transpose(Pmatrix a, Pmatrix a_t): transpose an (nxm) rational matrix a into a (mxn) rational matrix a_t More...

void	matrix_multiply (const Pmatrix, const Pmatrix, Pmatrix)
	void matrix_multiply(Pmatrix a, Pmatrix b, Pmatrix c): multiply rational matrix a by rational matrix b and store result in matrix c More...

void	matrix_normalize (Pmatrix)
	void matrix_normalize(Pmatrix a) More...

void	matrix_normalizec (Pmatrix)
	void matrix_normalizec(Pmatrix MAT): Normalisation des coefficients de la matrice MAT, i.e. More...

void	matrix_swap_columns (Pmatrix, int, int)
	void matrix_swap_columns(Pmatrix a, int c1, int c2): exchange columns c1,c2 of an (nxm) rational matrix More...

void	matrix_swap_rows (Pmatrix, int, int)
	void matrix_swap_rows(Pmatrix a, int r1, int r2): exchange rows r1 and r2 of an (nxm) rational matrix a More...

void	matrix_assign (Pmatrix, Pmatrix)
	void matrix_assign(Pmatrix A, Pmatrix B) Copie de la matrice A dans la matrice B More...

bool	matrix_equality (Pmatrix, Pmatrix)
	bool matrix_equality(Pmatrix A, Pmatrix B) test de l'egalite de deux matrices A et B; elles doivent avoir ete normalisees au prealable pour que le test soit mathematiquement exact More...

void	matrix_nulle (Pmatrix)
	void matrix_nulle(Pmatrix Z): Initialisation de la matrice Z a la valeur matrice nulle More...

bool	matrix_nulle_p (Pmatrix)
	bool matrix_nulle_p(Pmatrix Z): test de nullite de la matrice Z More...

bool	matrix_diagonal_p (Pmatrix)
	bool matrix_diagonal_p(Pmatrix Z): test de nullite de la matrice Z More...

bool	matrix_triangular_p (Pmatrix, bool)
	bool matrix_triangular_p(Pmatrix Z, bool inferieure): test de triangularite de la matrice Z More...

bool	matrix_triangular_unimodular_p (Pmatrix, bool)
	bool matrix_triangular_unimodular_p(Pmatrix Z, bool inferieure) test de la triangulaire et unimodulaire de la matrice Z. More...

void	matrix_substract (Pmatrix, Pmatrix, Pmatrix)
	void matrix_substract(Pmatrix a, Pmatrix b, Pmatrix c): substract rational matrix c from rational matrix b and store result in matrix a More...

void	matrix_add (Pmatrix, Pmatrix, Pmatrix)
	a = b + c More...

void	matrix_subtraction_column (Pmatrix, int, int, Value)
	void matrix_subtraction_column(Pmatrix MAT,int c1,int c2,int x): Soustrait x fois la colonne c2 de la colonne c1 Precondition: n > 0; m > 0; 0 < c1, c2 < m; Effet: c1[0..n-1] = c1[0..n-1] - x*c2[0..n-1]. More...

void	matrix_subtraction_line (Pmatrix, int, int, Value)
	void matrix_subtraction_line(Pmatrix MAT,int r1,int r2,int x): Soustrait x fois la ligne r2 de la ligne r1 Precondition: n > 0; m > 0; 0 < r1, r2 < n; Effet: r1[0..m-1] = r1[0..m-1] - x*r2[0..m-1] More...

void	matrix_uminus (Pmatrix, Pmatrix)
	void matrix_uminus(A, mA) More...

void	matrix_fprint (FILE *, Pmatrix)
	matrix_io.c More...

void	matrix_print (Pmatrix)
	void matrix_print(matrice a): print an (nxm) rational matrix More...

void	matrix_fscan (FILE , Pmatrix , int , int )
	void matrix_fscan(FILE * f, matrice * a, int * n, int * m): read an (nxm) rational matrix in an ASCII file accessible via file descriptor f; a is allocated as a function of its number of columns and rows, n and m. More...

void	matrix_pr_quot (FILE *, Value, Value)

void	matrix_smith (Pmatrix, Pmatrix, Pmatrix, Pmatrix)
	smith.c More...

int	matrices_to_1D_lattice (Pmatrix, Pmatrix, int, int, int, Value , Value )
	Under the assumption A x = B, A[n,m] and B[n], compute the 1-D lattice for x_i of x[m] as. More...

int	matrix_line_nnul (Pmatrix, int)
	sub-matrix.c More...

void	matrix_perm_col (Pmatrix, int, int)
	void matrix_perm_col(Pmatrix MAT, int k, int level): Calcul de la matrice de permutation permettant d'amener la k-ieme ligne de la matrice MAT(1..n,1..m) a la ligne (level + 1). More...

void	matrix_perm_line (Pmatrix, int, int)
	void matrix_perm_line(Pmatrix MAT, int k, int level): Calcul de la matrice de permutation permettant d'amener la k-ieme colonne de la sous-matrice MAT(1..n,1..m) a la colonne 'level + 1' (premiere colonne de la sous matrice MAT(level+1 ..n,level+1 ..m)). More...

void	matrix_min (Pmatrix, int , int , int)
	void matrix_min(Pmatrix MAT, int * i_min, int * j_min, int level): Recherche des coordonnees (i_min, j_min) de l'element de la sous-matrice MAT(level+1 ..n, level+1 ..m) dont la valeur absolue est la plus petite et non nulle. More...

void	matrix_maj_col (Pmatrix, Pmatrix, int)
	void matrix_maj_col(Pmatrix A, matrice P, int level): Calcul de la matrice permettant de remplacer chaque terme de la premiere ligne de la sous-matrice A(level+1 ..n, level+1 ..m) autre que le premier terme A11=A(level+1,level+1) par le reste de sa division entiere par A11 More...

void	matrix_maj_line (Pmatrix, Pmatrix, int)
	void matrix_maj_line(Pmatrix A, matrice Q, int level): Calcul de la matrice permettant de remplacer chaque terme de la premiere ligne autre que le premier terme A11=A(level+1,level+1) par le reste de sa division entiere par A11 More...

void	matrix_identity (Pmatrix, int)
	void matrix_identity(Pmatrix ID, int level) Construction d'une sous-matrice identity dans ID(level+1..n, level+1..n) More...

bool	matrix_identity_p (Pmatrix, int)
	bool matrix_identity_p(Pmatrix ID, int level) test d'une sous-matrice dans ID(level+1..n, level+1..n) pour savoir si c'est une matrice identity. More...

int	matrix_line_el (Pmatrix, int)
	int matrix_line_el(Pmatrix MAT, int level) renvoie le numero de colonne absolu du premier element non nul de la sous-ligne MAT(level+1,level+2..m); renvoie 0 si la sous-ligne est vide. More...

int	matrix_col_el (Pmatrix, int)
	int matrix_col_el(Pmatrix MAT, int level) renvoie le numero de ligne absolu du premier element non nul de la sous-colonne MAT(level+2..n,level+1); renvoie 0 si la sous-colonne est vide. More...

void	matrix_coeff_nnul (Pmatrix, int , int , int)
	void matrix_coeff_nnul(Pmatrix MAT, int * lg_nnul, int * cl_nnul, int level) renvoie les coordonnees du plus petit element non-nul de la premiere sous-ligne non nulle 'lg_nnul' de la sous-matrice MAT(level+1..n, level+1..m) More...

void	ordinary_sub_matrix (Pmatrix, Pmatrix, int, int, int, int)
	void ordinary_sub_matrix(Pmatrix A, A_sub, int i1, i2, j1, j2) input : a initialized matrix A, an uninitialized matrix A_sub, which dimensions are i2-i1+1 and j2-j1+1. More...

void	insert_sub_matrix (Pmatrix, Pmatrix, int, int, int, int)
	void insert_sub_matrix(A, A_sub, i1, i2, j1, j2) input: matrix A and smaller A_sub output: nothing modifies: A_sub is inserted in A at the specified position comment: A must be pre-allocated More...

Macro Definition Documentation

◆ MATRIX_DENOMINATOR

#define MATRIX_DENOMINATOR ( matrix ) ((matrix)->denominator)

int MATRIX_DENONIMATOR(matrix): acces au denominateur global d'une matrice matrix

Definition at line 94 of file matrix.h.

◆ MATRIX_ELEM

#define MATRIX_ELEM	(	matrix,
		i,
		j
	)	((matrix)->coefficients[(((j)-1)*((matrix)->number_of_lines))+((i)-1)])

Macros d'acces aux elements d'une matrice.

int MATRIX_ELEM(int * matrix, int i, int j): acces a l'element (i,j) de la matrice matrix.

Definition at line 88 of file matrix.h.

◆ matrix_free

#define matrix_free ( m ) (free(m), (m)=(Pmatrix) NULL)

Allocation et desallocation d'une matrice.

Definition at line 81 of file matrix.h.

◆ MATRIX_NB_COLUMNS

#define MATRIX_NB_COLUMNS ( matrix ) ((matrix)->number_of_columns)

Definition at line 96 of file matrix.h.

◆ MATRIX_NB_LINES

#define MATRIX_NB_LINES ( matrix ) ((matrix)->number_of_lines)

Definition at line 95 of file matrix.h.

◆ matrix_triangular_inferieure_p

#define matrix_triangular_inferieure_p ( a ) matrix_triangular_p(a, true)

bool matrix_triangular_inferieure_p(matrice a): test de triangularite de la matrice a

Definition at line 101 of file matrix.h.

◆ matrix_triangular_superieure_p

#define matrix_triangular_superieure_p ( a ) matrix_triangular_p(a, false)

bool matrix_triangular_superieure_p(matrice a, int n, int m): test de triangularite de la matrice a

Definition at line 107 of file matrix.h.

◆ MATRIX_UNDEFINED

#define MATRIX_UNDEFINED ((Pmatrix) NULL)

Definition at line 78 of file matrix.h.

◆ SUB_MATRIX_ELEM

#define SUB_MATRIX_ELEM	(	matrix,
		i,
		j,
		level
	)

Value:

(matrix->coefficients[((j)-1+(level))* \

((matrix)->number_of_lines) + (i) - 1 + (level)])

level

#define level

matrix

Definition: test_chernikova.c:52

MATRIX_RIGHT_INF_ELEM Permet d'acceder des sous-matrices dont le coin infe'rieur droit (i.e.

le premier element) se trouve sur la diagonal

Definition at line 114 of file matrix.h.

Typedef Documentation

◆ Smatrix

typedef struct Pmatrix Smatrix

Function Documentation

◆ insert_sub_matrix()

void insert_sub_matrix	(	Pmatrix	A,
		Pmatrix	A_sub,
		int	i1,
		int	i2,
		int	j1,
		int	j2
	)

void insert_sub_matrix(A, A_sub, i1, i2, j1, j2) input: matrix A and smaller A_sub output: nothing modifies: A_sub is inserted in A at the specified position comment: A must be pre-allocated

Parameters

A_sub	_sub
i1	1
i2	2
j1	1
j2	2

Definition at line 487 of file sub-matrix.c.

 {
     int i,j,i_sub,j_sub;
  
     assert(i1>=1 && j1>=1 && 
            i2<=MATRIX_NB_LINES(A) && j2<=MATRIX_NB_COLUMNS(A) &&
            i2-i1<MATRIX_NB_LINES(A_sub) && j2-j1<MATRIX_NB_COLUMNS(A_sub));
  
     for (i = i1, i_sub = 1; i <= i2; i++, i_sub ++)
         for(j = j1, j_sub = 1; j <= j2; j++, j_sub ++)
             MATRIX_ELEM(A,i,j) = MATRIX_ELEM(A_sub,i_sub,j_sub) ;
 }

References assert, MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.

Referenced by extract_lattice().

Here is the caller graph for this function:

◆ matrices_to_1D_lattice()

int matrices_to_1D_lattice	(	Pmatrix	A,
		Pmatrix	B,
		int	n,
		int	m,
		int	i,
		Value *	gcd_p,
		Value *	c_p
	)

Under the assumption A x = B, A[n,m] and B[n], compute the 1-D lattice for x_i of x[m] as.

x_i = gcd_i lambda + c_i

derived from the parametric solution of the system :

x_i = sum_{k<j<=m} q_{i,j} lambda_j + sum_{1<=j,=k} q_{i,j} y_c_{j}

where k is the rank of matrix A (0<=k<=n, k<=m), lambda_j are the free variables and y_c is the solution of the equations. This leads to:

gcd_i = sum_{k<j<=m} q_{i,j} and c_i = sum_{1<=j,=k} q_{i,j} y_c_{j}

when the system has a least one solution.

To compute Q and y_c, We use D[n,m], the Smith form of A, with D = P A Q and P[n,n] and Q[m,m] unimodular

inv(P) D inv(Q) x = b

inv(P) D y = b => D y = P b => some components of y[m] are constants, y_c[m]

y_c = D'{-1} P b, where D'[min(n,m),min(n,m)] is the top left submatrix of D[n,m]

y = inv(Q) x => x = Q (y_c[1..k],y[k+1..m])

where (a,b) represents s the concatenation of vectors a and b, and k<=min(n,m) the .

c_i = sum_j Q_{i,j} y_c_{j}

gcd = gcd_{j s.t. yc_j = 0} Q_{i,j}

Return false if the system Ax=b has no solution

This implements a partial parametric resolution of A x = B. It might be better from an engineering viewpoint to solve the system fully and then to exploit the equation for x_i.

Parameters

gcd_p	cd_p
c_p	_p

Definition at line 195 of file smith.c.

 {
   // The number of equations is smaller than the number of variables
   // Not necessarily because you may have redundant equations
   // assert(n<=m);
   int success = 1;
   Pmatrix P, D, Q;
   P = matrix_new(n,n);
   D = matrix_new(n,m);
   Q = matrix_new(m,m);
   matrix_smith(A,P,D,Q);
  
   // Compute P b
  
   Pmatrix Pb = matrix_new(n, 1);
   matrix_multiply(P, B, Pb);
  
   // Compute yc by solving D yc = P b
  
   Pmatrix yc = matrix_new(m, 1);
   int j;
   for(j=1; j <= m; j++)
     MATRIX_ELEM(yc, j, 1) = VALUE_ZERO;
   // FI: it might be sufficient to check the pseudo-diagonal element Dii
   int k = 0;
   for(j=1; j <= n && j <= m; j++) {
     Value Pbj = MATRIX_ELEM(Pb, j, 1);
     if(!value_zero_p(Pbj)) {
       Value Djj = MATRIX_ELEM(D, j, j);
       if(!value_zero_p(Djj)) {
         Value r = modulo(Pbj, Djj);
         if(value_zero_p(r))
           MATRIX_ELEM(yc, j, 1) = DIVIDE(Pbj, Djj), k=j;
         else
           success = false;
       }
     }
   }
   for(j=k+1; j <= n; j++) {
     Value Pbj = MATRIX_ELEM(Pb, j, 1);
     if(!value_zero_p(Pbj)) {
         success = false;
     }
    }
  
   // If the system has parametric solutions
  
   if(success) {
     //  k = MIN(n,m);
     // Compute the constant term "c_i"
     *c_p = VALUE_ZERO;
     for(j=1; j <= k; j++) {
       *c_p += value_mult(MATRIX_ELEM(Q, i, j), MATRIX_ELEM(yc, j, 1));
     }
  
     // and the gcd "gcd_i" with x = Q yc
     *gcd_p = VALUE_ZERO;
     for(j=k+1; j <= m; j++) {
       if(value_zero_p(*gcd_p))
         *gcd_p = MATRIX_ELEM(Q, i, j);
       else if(!value_zero_p(MATRIX_ELEM(Q, i, j)))
         *gcd_p = pgcd(*gcd_p, MATRIX_ELEM(Q, i, j));
     }
  
     // With no information at all, the gcd default value is one
     if(value_zero_p(*gcd_p))
       *gcd_p = VALUE_ONE;
     *c_p = modulo(*c_p, *gcd_p);
   }
   free(P);
   free(Pb);
   free(D);
   free(Q);
   free(yc);
   return success;
 }

References B, D, DIVIDE, free(), MATRIX_ELEM, matrix_multiply(), matrix_new(), matrix_smith(), modulo, pgcd, Q, value_mult, VALUE_ONE, VALUE_ZERO, and value_zero_p.

Referenced by transformer_to_1D_lattice().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_add()

void matrix_add	(	Pmatrix	a,
		Pmatrix	b,
		Pmatrix	c
	)

a = b + c

precondition

Definition at line 471 of file matrix.c.

 {
   /* precondition */
   int m = MATRIX_NB_LINES(a);
   int n = MATRIX_NB_COLUMNS(a);
   assert(n>0 && m>0);
   assert(value_pos_p(MATRIX_DENOMINATOR(b)));
   assert(value_pos_p(MATRIX_DENOMINATOR(c)));
  
   Value d1 = MATRIX_DENOMINATOR(b);
   Value d2 = MATRIX_DENOMINATOR(c);
   if (value_eq(d1,d2)){
     int i, j;
     for (i=1; i<=m; i++)
             for (j=1; j<=n; j++)
         MATRIX_ELEM(a,i,j) =
           value_plus(MATRIX_ELEM(b,i,j),MATRIX_ELEM(c,i,j));
     MATRIX_DENOMINATOR(a) = d1;
   }
   else{
     Value lcm = ppcm(d1, d2);
     d1 = value_div(lcm,d1);
     d2 = value_div(lcm,d2);
     int i, j;
     for (i=1; i<=m; i++) {
             for (j=1; j<=n; j++) {
         Value t1 = value_mult(MATRIX_ELEM(b,i,j),d1);
         Value t2 = value_mult(MATRIX_ELEM(c,i,j),d2);
         MATRIX_ELEM(a,i,j) = value_plus(t1,t2);
       }
     }
     MATRIX_DENOMINATOR(a) = lcm;
   }
 }

References assert, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, ppcm(), value_div, value_eq, value_mult, value_plus, and value_pos_p.

Referenced by make_reindex(), and prepare_reindexing().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_assign()

void matrix_assign	(	Pmatrix	A,
		Pmatrix	B
	)

void matrix_assign(Pmatrix A, Pmatrix B) Copie de la matrice A dans la matrice B

Les parametres de la fonction :

int A[] : matrice !int B[] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice

Ancien nom: matrix_dup

Definition at line 259 of file matrix.c.

 {
   int m = MATRIX_NB_LINES(A);
   int n = MATRIX_NB_COLUMNS(A);
   int i;
   for (i=0 ; i<m*n; i++)
     B->coefficients[i] = A->coefficients[i];
 }

References B, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.

Referenced by matrix_hermite(), matrix_smith(), sc_resol_smith(), and smith_int().

Here is the caller graph for this function:

◆ matrix_coeff_nnul()

void matrix_coeff_nnul	(	Pmatrix	MAT,
		int *	lg_nnul,
		int *	cl_nnul,
		int	level
	)

void matrix_coeff_nnul(Pmatrix MAT, int * lg_nnul, int * cl_nnul, int level) renvoie les coordonnees du plus petit element non-nul de la premiere sous-ligne non nulle 'lg_nnul' de la sous-matrice MAT(level+1..n, level+1..m)

recherche de la premiere ligne non nulle de la sous-matrice MAT(level+1 .. n,level+1 .. m)

recherche du plus petit (en valeur absolue) element non nul de cette ligne

Parameters

MAT	AT
lg_nnul	g_nnul
cl_nnul	l_nnul
level	evel

Definition at line 421 of file sub-matrix.c.

 {
     bool trouve = false;
     int j;
     Value min = VALUE_ZERO,val=VALUE_ZERO;
     int m = MATRIX_NB_COLUMNS(MAT);
     *lg_nnul = 0;
     *cl_nnul = 0;
  
     /* recherche de la premiere ligne non nulle de la 
        sous-matrice MAT(level+1 .. n,level+1 .. m)      */
  
     *lg_nnul= matrix_line_nnul(MAT,level);
  
     /* recherche du plus petit (en valeur absolue) element non nul de cette ligne */
     if (*lg_nnul) {
         for (j=1+level;j<=m && !trouve; j++) {
             min = MATRIX_ELEM(MAT,*lg_nnul,j);
             min = value_abs(min);
             if (value_notzero_p(min)) {
                 trouve = true;
                 *cl_nnul=j;
             }
         }
         for (j=1+level;j<=m && value_gt(min,VALUE_ONE); j++) {
             val = MATRIX_ELEM(MAT,*lg_nnul,j);
             val = value_abs(val);
             if (value_notzero_p(val) && value_lt(val,min)) {
                 min = val;
                 *cl_nnul =j;
             }
         }
     }
 }

References level, MATRIX_ELEM, matrix_line_nnul(), MATRIX_NB_COLUMNS, min, value_abs, value_gt, value_lt, value_notzero_p, VALUE_ONE, and VALUE_ZERO.

Referenced by matrix_hermite().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_col_el()

int matrix_col_el	(	Pmatrix	MAT,
		int	level
	)

int matrix_col_el(Pmatrix MAT, int level) renvoie le numero de ligne absolu du premier element non nul de la sous-colonne MAT(level+2..n,level+1); renvoie 0 si la sous-colonne est vide.

RGSUSED

Parameters

MAT	AT
level	evel

Definition at line 401 of file sub-matrix.c.

 {
     int i;
     int i_min=0;
     int n = MATRIX_NB_LINES(MAT); 
     for(i = level+2; i <= n && (MATRIX_ELEM(MAT,i,level+1)==0); i++);
     if (i<n+1)
         i_min = i-1;
     return (i_min);
 }

References level, MATRIX_ELEM, and MATRIX_NB_LINES.

Referenced by matrix_smith(), and smith_int().

Here is the caller graph for this function:

◆ matrix_determinant()

void matrix_determinant	(	Pmatrix	,
		Value	[]
	)

determinant.c

◆ matrix_diagonal_inversion()

void matrix_diagonal_inversion	(	Pmatrix	s,
		Pmatrix	inv_s
	)

void matrix_diagonal_inversion(Pmatrix s,Pmatrix inv_s) calcul de l'inversion du matrice en forme reduite smith.

s est un matrice de la forme reduite smith, inv_s est l'inversion de s ; telles que s * inv_s = I.

les parametres de la fonction : matrice s : matrice en forme reduite smith – input int n : dimension de la matrice caree – input matrice inv_s : l'inversion de s – output

tests des preconditions

calcul de la ppcm(s[1,1],s[2,2],...s[n,n])

Parameters

inv_s nv_s

Definition at line 93 of file inversion.c.

 {
     Value d, d1; 
     Value gcd, lcm;
     int i;
     int n = MATRIX_NB_LINES(s);
     /* tests des preconditions */
     assert(matrix_diagonal_p(s));
     assert(matrix_hermite_rank(s)==n);
     assert(value_pos_p(MATRIX_DENOMINATOR(s)));
  
     matrix_nulle(inv_s);
     /* calcul de la ppcm(s[1,1],s[2,2],...s[n,n]) */
     lcm = MATRIX_ELEM(s,1,1);
     for (i=2; i<=n; i++)
         lcm = ppcm(lcm,MATRIX_ELEM(s,i,i));
     
     d = MATRIX_DENOMINATOR(s);
     gcd = pgcd(lcm,d);
     d1 = value_div(d,gcd);
     for (i=1; i<=n; i++) {
         Value tmp = value_div(lcm,MATRIX_ELEM(s,i,i));
         MATRIX_ELEM(inv_s,i,i) = value_mult(d1,tmp);
     }
     MATRIX_DENOMINATOR(inv_s) = value_div(lcm,gcd);
 }

References assert, MATRIX_DENOMINATOR, matrix_diagonal_p(), MATRIX_ELEM, matrix_hermite_rank(), MATRIX_NB_LINES, matrix_nulle(), pgcd, ppcm(), value_div, value_mult, and value_pos_p.

Here is the call graph for this function:

◆ matrix_diagonal_p()

bool matrix_diagonal_p ( Pmatrix Z )

bool matrix_diagonal_p(Pmatrix Z): test de nullite de la matrice Z

QQ i dans [1..n] QQ j dans [1..n] Z(i,j) == 0 && i != j || i == j

Les parametres de la fonction :

int Z[] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice

Definition at line 336 of file matrix.c.

 {
   int i,j;
   int m = MATRIX_NB_LINES(Z);
   int n = MATRIX_NB_COLUMNS(Z);
   for (i=1;i<=m;i++)
     for (j=1;j<=n;j++)
             if(i!=j && MATRIX_ELEM(Z,i,j)!=0)
         return false;
   return true;
 }

References MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.

Referenced by extract_lattice(), and matrix_diagonal_inversion().

Here is the caller graph for this function:

◆ matrix_dim_hermite()

int matrix_dim_hermite ( Pmatrix H )

Calcul de la dimension de la matrice de Hermite H.

La matrice de Hermite est une matrice tres particuliere, pour laquelle il est tres facile de calculer sa dimension. Elle est egale au nombre de colonnes non nulles de la matrice.

Definition at line 194 of file hermite.c.

 {
     int i,j;
     bool trouve_j = false;
     int res=0;
     int n = MATRIX_NB_LINES(H);
     int m = MATRIX_NB_COLUMNS(H);
     for (j = 1; j<=m && !trouve_j;j++) {
         for (i=1; i<= n && MATRIX_ELEM(H,i,j) == 0; i++);
         if (i>n) {
             trouve_j = true;
             res= j-1;
         }
     }
  
  
     if (!trouve_j && m>=1) res = m;
     return (res);
  
 }

References MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.

◆ matrix_elem()

Value matrix_elem	(	Pmatrix	M,
		int	r,
		int	c
	)

Definition at line 49 of file matrix.c.

 {
   assert(M != NULL && M->coefficients != NULL);
   assert(1 <= r && r <= M->number_of_lines);
   assert(1 <= c && c <= M->number_of_columns);
   // return M->coefficients[(c-1) * M->number_of_lines + r - 1];
   return MATRIX_ELEM(M, r, c);
 }

References assert, Pmatrix::coefficients, and MATRIX_ELEM.

◆ matrix_elem_ref()

Value* matrix_elem_ref	(	Pmatrix	M,
		int	r,
		int	c
	)

matrix.c

Definition at line 41 of file matrix.c.

 {
   assert(M != NULL && M->coefficients != NULL);
   assert(1 <= r && r <= M->number_of_lines);
   assert(1 <= c && c <= M->number_of_columns);
   return &(MATRIX_ELEM(M, r, c));
 }

References assert, Pmatrix::coefficients, and MATRIX_ELEM.

◆ matrix_equality()

bool matrix_equality	(	Pmatrix	A,
		Pmatrix	B
	)

bool matrix_equality(Pmatrix A, Pmatrix B) test de l'egalite de deux matrices A et B; elles doivent avoir ete normalisees au prealable pour que le test soit mathematiquement exact

Definition at line 273 of file matrix.c.

 {
   int m = MATRIX_NB_LINES(A);
   int n = MATRIX_NB_COLUMNS(A);
   int i;
   for (i = 0 ; i < m*n; i++)
     if (B->coefficients[i] != A->coefficients[i])
             return false;
   return true;
 }

References B, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.

◆ matrix_fprint()

void matrix_fprint	(	FILE *	f,
		Pmatrix	a
	)

matrix_io.c

void matrix_fprint(File * f, matrix a): print a rational matrix

Note: the output format is compatible with matrix_fscan()

Definition at line 44 of file matrix_io.c.

 {
   int   i, j;
   int m = MATRIX_NB_LINES(a);
   int n = MATRIX_NB_COLUMNS(a);
   assert(MATRIX_DENOMINATOR(a) != VALUE_ZERO);
  
   (void) fprintf(f, "%d %d\n", m, n);
   (void) fprint_Value(f, MATRIX_DENOMINATOR(a));
   (void) fprintf(f, "\n");
   for(i=1; i<=m; i++) {
     for(j=1; j<=n; j++) {
       // matrix_pr_quot(f, MATRIX_ELEM(a,i,j), MATRIX_DENOMINATOR(a));
       fprint_Value(f, MATRIX_ELEM(a,i,j));
       fprintf(f, " ");
     }
     (void) fprintf(f, "\n");
   }
 }

References assert, f(), fprint_Value(), fprintf(), MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, and VALUE_ZERO.

Referenced by main(), make_reindex(), matrix_print(), and prepare_reindexing().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_fscan()

void matrix_fscan	(	FILE *	f,
		Pmatrix *	a,
		int *	n,
		int *	m
	)

void matrix_fscan(FILE * f, matrice * a, int * n, int * m): read an (nxm) rational matrix in an ASCII file accessible via file descriptor f; a is allocated as a function of its number of columns and rows, n and m.

Format:

n m denominator a[1,1] a[1,2] ... a[1,m] a[2,1] ... a[2,m] ... a[n,m]

After the two dimensions and the global denominator, the matrix as usually displayed, line by line. Line feed can be used anywhere. Example for a (2x3) integer matrix: 2 3 1 1 2 3 4 5 6 row size

number of read elements

read dimensions

allocate a

read denominator

necessaires pour eviter les divisions par zero

pour "normaliser" un peu les representations

Parameters

m Format:

n m denominator a[1,1] a[1,2] ... a[1,m] a[2,1] ... a[2,m] ... a[n,m]

After the two dimensions and the global denominator, the matrix as usually displayed, line by line. Line feed can be used anywhere. Example for a (2x3) integer matrix: 2 3 1 1 2 3 4 5 6 column size

Definition at line 93 of file matrix_io.c.

 {
     int r;
     int c;
  
     /* number of read elements */
     int n_read;
  
     /* read dimensions */
     n_read = fscanf(f,"%d%d", n, m);
     assert(n_read==2);
     assert(1 <= *n && 1 <= *m);
  
     /* allocate a */
     *a = matrix_new(*n,*m); 
  
     /* read denominator */
     n_read = fscan_Value(f,&(MATRIX_DENOMINATOR(*a)));
     assert(n_read == 1);
     /* necessaires pour eviter les divisions par zero */
     assert(value_notzero_p(MATRIX_DENOMINATOR(*a)));
     /* pour "normaliser" un peu les representations */
     assert(value_pos_p(MATRIX_DENOMINATOR(*a)));
  
     for(r = 1; r <= *n; r++) 
         for(c = 1; c <= *m; c++) {
             n_read = fscan_Value(f, &MATRIX_ELEM(*a,r,c));
             assert(n_read == 1);
         }
 }

References assert, f(), fscan_Value(), MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_new(), value_notzero_p, and value_pos_p.

Referenced by Hierarchical_tiling(), main(), Tiling2_buffer(), and Tiling_buffer_allocation().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_general_inversion()

void matrix_general_inversion	(	Pmatrix	a,
		Pmatrix	inv_a
	)

void matrix_general_inversion(Pmatrix a; Pmatrix inv_a) calcul de l'inversion du matrice general.

Algorithme : calcul P, Q, H telque : PAQ = H ; -1 -1 si rank(H) = n ; A = Q H P .

les parametres de la fonction : matrice a : matrice general -— input matrice inv_a : l'inversion de a -— output int n : dimensions de la matrice caree -— input

ne utilise pas

test

Parameters

inv_a nv_a

Definition at line 216 of file inversion.c.

 {
     int n = MATRIX_NB_LINES(a);
     Pmatrix p = matrix_new(n,n);
     Pmatrix q = matrix_new(n,n);
     Pmatrix h = matrix_new(n,n);
     Pmatrix inv_h = matrix_new(n,n);
     Pmatrix temp = matrix_new(n,n);
     Value deno;
     Value det_p, det_q;                 /* ne utilise pas */
  
     /* test */
     assert(value_pos_p(MATRIX_DENOMINATOR(a)));
  
     deno = MATRIX_DENOMINATOR(a);
     MATRIX_DENOMINATOR(a) = VALUE_ONE;
     matrix_hermite(a,p,h,q,&det_p,&det_q);
     MATRIX_DENOMINATOR(a) = deno;
     if ( matrix_hermite_rank(h) == n){
         MATRIX_DENOMINATOR(h) = deno;
         matrix_triangular_inversion(h,inv_h,true);
         matrix_multiply(q,inv_h,temp);
         matrix_multiply(temp,p,inv_a);
     }
     else{
         fprintf(stderr," L'inverse de la matrice a n'existe pas!\n");
         exit(1);
     }
 }

References assert, exit, fprintf(), MATRIX_DENOMINATOR, matrix_hermite(), matrix_hermite_rank(), matrix_multiply(), MATRIX_NB_LINES, matrix_new(), matrix_triangular_inversion(), VALUE_ONE, and value_pos_p.

Referenced by build_contraction_matrices(), and prepare_reindexing().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_hermite()

void matrix_hermite	(	Pmatrix	MAT,
		Pmatrix	P,
		Pmatrix	H,
		Pmatrix	Q,
		Value *	det_p,
		Value *	det_q
	)

hermite.c

void matrix_hermite(matrix MAT, matrix P, matrix H, matrix Q, int *det_p, int *det_q): calcul de la forme reduite de Hermite H de la matrice MAT avec les deux matrices de changement de base unimodulaire P et Q, telles que H = P x MAT x Q et en le meme temp, produit les determinants des P et Q. det_p = |P|, det_q = |Q|.

(c.f. Programmation Lineaire. Theorie et algorithmes. tome 2. M.MINOUX. Dunod (1983)) FI: Quels est l'invariant de l'algorithme? MAT = P x H x Q? FI: Quelle est la norme decroissante? La condition d'arret?

Les parametres de la fonction :

int MAT[n,m]: matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice int P[n,n] : matrice int H[n,m] : matrice reduite de Hermite int Q[m,m] : matrice int *det_p : determinant de P (nombre de permutation de ligne) int *det_q : determinant de Q (nombre de permutation de colonne)

Les 3 matrices P(nxn), Q(mxm) et H(nxm) doivent etre allouees avant le calcul.

Note: les denominateurs de MAT, P, A et H ne sont pas utilises.

Auteurs: Corinne Ancourt, Yi-qing Yang

Modifications:

modification du profil de la fonction pour permettre le calcul du determinant de MAT
permutation de colonnes directe, remplacant une permutation par produit de matrices
suppression des copies entre H, P, Q et NH, PN, QN

indice de la ligne et indice de la colonne correspondant au plus petit element de la sous-matrice traitee

niveau de la sous-matrice traitee

le plus petit element sur la diagonale

la quotient de la division par ALL

if ((n>0) && (m>0) && MAT)

Initialisation des matrices

tant qu'il reste des termes non nuls dans la partie triangulaire superieure de la matrice H,
on cherche le plus petit element de la sous-matrice

la sous-matrice restante est nulle, on a terminee

s'il existe un plus petit element non nul dans la partie triangulaire superieure de la sous-matrice, on amene cet element en haut sur la diagonale. si cet element est deja sur la diagonale, et que tous les termes de la ligne correspondante sont nuls, on effectue les calculs sur la sous-matrice de rang superieur

Parameters

MAT	AT
det_p	et_p
det_q	et_q

Definition at line 78 of file hermite.c.

 {
     Pmatrix PN=NULL;
     Pmatrix QN=NULL;
     Pmatrix HN = NULL;
     int n,m;
     /* indice de la ligne et indice de la colonne correspondant
        au plus petit element de la sous-matrice traitee */
     int ind_n,ind_m;   
  
     /* niveau de la sous-matrice traitee */
     int level = 0;    
     
     Value ALL;/* le plus petit element sur la diagonale */
     Value x=VALUE_ZERO;  /* la quotient de la division par ALL */
     bool stop = false;
     int i;
     
     *det_p = *det_q = VALUE_ONE;
     /* if ((n>0) && (m>0) && MAT) */
     n = MATRIX_NB_LINES(MAT);
     m=MATRIX_NB_COLUMNS(MAT);
     assert(n >0 && m > 0);
     assert(value_one_p(MATRIX_DENOMINATOR(MAT)));
  
     HN = matrix_new(n, m);
     PN = matrix_new(n, n);
     QN = matrix_new(m, m);
    
     /* Initialisation des matrices */
  
     matrix_assign(MAT,H);
     matrix_identity(PN,0);
     matrix_identity(QN,0);
     matrix_identity(P,0);
     matrix_identity(Q,0);
     matrix_nulle(HN);
  
     while (!stop) {  
         /* tant qu'il reste des termes non nuls dans la partie 
            triangulaire superieure  de la matrice H,        
            on cherche le plus petit element de la sous-matrice     */
         matrix_coeff_nnul(H,&ind_n,&ind_m,level);
  
         if (ind_n == 0 && ind_m == 0)
             /* la sous-matrice restante est nulle, on a terminee */
             stop = true; 
         else { 
             /* s'il existe un plus petit element non nul dans la partie
                triangulaire superieure de la sous-matrice,
                on amene cet element en haut sur la diagonale.
                si cet element est deja sur la diagonale, et que  tous les 
                termes de la ligne correspondante sont nuls,
                on effectue les calculs sur la sous-matrice de rang superieur*/
                
             if (ind_n > level + 1) {
                 matrix_swap_rows(H,level+1,ind_n);
                 matrix_swap_rows(PN,level+1,ind_n);
                 *det_p = value_uminus(*det_p);
             }
  
             if (ind_m > level+1) {
                 matrix_swap_columns(H,level+1,ind_m);
                 matrix_swap_columns(QN,level+1,ind_m);  
                 *det_q = value_uminus(*det_q);
             }
  
             if(matrix_line_el(H,level) != 0) {
                 ALL = SUB_MATRIX_ELEM(H,1,1,level);
                 for (i=level+2; i<=m; i++) {
                     x = value_div(MATRIX_ELEM(H,level+1,i),ALL);
                     matrix_subtraction_column(H,i,level+1,x);
                     matrix_subtraction_column(QN,i,level+1,x);
                 }
  
             }
             else level++;
         }
     }
  
     matrix_assign(PN,P);
     matrix_assign(QN,Q);
     matrix_free(HN);
     matrix_free(PN);
     matrix_free(QN);
 }

References ALL, assert, level, matrix_assign(), matrix_coeff_nnul(), MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_free, matrix_identity(), matrix_line_el(), MATRIX_NB_COLUMNS, MATRIX_NB_LINES, matrix_new(), matrix_nulle(), matrix_subtraction_column(), matrix_swap_columns(), matrix_swap_rows(), Q, SUB_MATRIX_ELEM, value_div, VALUE_ONE, value_one_p, value_uminus, VALUE_ZERO, and x.

Referenced by extract_lattice(), matrix_determinant(), matrix_general_inversion(), matrix_unimodular_inversion(), prepare_reindexing(), and region_sc_minimal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_hermite_rank()

int matrix_hermite_rank ( Pmatrix a )

int matrix_hermite_rank(Pmatrix a): rang d'une matrice en forme de hermite

Definition at line 174 of file hermite.c.

 {
     int i;
     int r = 0;
     int n = MATRIX_NB_LINES(a);
     for(i=1; i<=n; i++, r++)
         if(MATRIX_ELEM(a, i, i) == 0) break;
  
     return r;
 }

References MATRIX_ELEM, and MATRIX_NB_LINES.

Referenced by matrix_diagonal_inversion(), matrix_general_inversion(), and matrix_triangular_inversion().

Here is the caller graph for this function:

◆ matrix_identity()

void matrix_identity	(	Pmatrix	ID,
		int	level
	)

void matrix_identity(Pmatrix ID, int level) Construction d'une sous-matrice identity dans ID(level+1..n, level+1..n)

Les parametres de la fonction :

!int ID[] : matrice int n : nombre de lignes de la matrice int level : niveau de la matrice i.e. numero de la premiere ligne et de la premiere colonne a partir duquel on commence a prendre en compte les elements de la matrice

Parameters

ID	D
level	evel

Definition at line 322 of file sub-matrix.c.

 {
     int i,j;
     int n = MATRIX_NB_LINES(ID);
     for(i = level+1; i <= n; i++) {
         for(j = level+1; j <= n; j++)
             MATRIX_ELEM(ID,i,j) = VALUE_ZERO;
         MATRIX_ELEM(ID,i,i) = VALUE_ONE;
     }
  
     MATRIX_DENOMINATOR(ID) = VALUE_ONE;
 }

References level, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_LINES, VALUE_ONE, and VALUE_ZERO.

Referenced by build_contraction_matrices(), extract_lattice(), matrix_hermite(), matrix_maj_col(), matrix_maj_line(), matrix_smith(), matrix_unimodular_triangular_inversion(), and smith_int().

Here is the caller graph for this function:

◆ matrix_identity_p()

bool matrix_identity_p	(	Pmatrix	ID,
		int	level
	)

bool matrix_identity_p(Pmatrix ID, int level) test d'une sous-matrice dans ID(level+1..n, level+1..n) pour savoir si c'est une matrice identity.

Le test n'est correct que si la matrice ID passee en argument est normalisee (cf. matrix_normalize())

Pour tester toute la matrice ID, appeler avec level==0

Les parametres de la fonction :

int ID[] : matrice int n : nombre de lignes (et de colonnes) de la matrice ID int level : niveau de la matrice i.e. numero de la premiere ligne et de la premiere colonne a partir duquel on commence a prendre en compte les elements de la matrice

i!=j

Parameters

ID	D
level	evel

Definition at line 352 of file sub-matrix.c.

 {
     int i,j;
     int n = MATRIX_NB_LINES(ID);
     for(i = level+1; i <= n; i++) {
         for(j = level+1; j <= n; j++) {
             if(i==j) {
                 if(value_notone_p(MATRIX_ELEM(ID,i,i)))
                     return(false);
             }
             else                        /* i!=j */
                 if(value_notzero_p(MATRIX_ELEM(ID,i,j)))
                     return(false);
         }
     }
     return(true);
 }

References level, MATRIX_ELEM, MATRIX_NB_LINES, value_notone_p, and value_notzero_p.

◆ matrix_line_el()

int matrix_line_el	(	Pmatrix	MAT,
		int	level
	)

int matrix_line_el(Pmatrix MAT, int level) renvoie le numero de colonne absolu du premier element non nul de la sous-ligne MAT(level+1,level+2..m); renvoie 0 si la sous-ligne est vide.

RGUSED

recherche du premier element non nul de la sous-ligne MAT(level+1,level+2..m)

Parameters

MAT	AT
level	evel

Definition at line 379 of file sub-matrix.c.

 {
     int j;
     int j_min = 0;
     int m = MATRIX_NB_COLUMNS(MAT);
     /* recherche du premier element non nul de la sous-ligne 
        MAT(level+1,level+2..m) */
     for(j = level+2; j<=m && (MATRIX_ELEM(MAT,1+level,j)==0) ; j++);
     if(j < m+1)
         j_min = j-1;
     return (j_min);
 }

References level, MATRIX_ELEM, and MATRIX_NB_COLUMNS.

Referenced by matrix_hermite(), matrix_smith(), and smith_int().

Here is the caller graph for this function:

◆ matrix_line_nnul()

int matrix_line_nnul	(	Pmatrix	MAT,
		int	level
	)

sub-matrix.c

resultat retourne par la fonction :

int : numero de la premiere ligne non nulle de la matrice MAT; ou 0 si la sous-matrice MAT(level+1 ..n,level+1 ..m) est identiquement nulle;

parametres de la fonction :

int MAT[] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice int level : niveau de la matrice i.e. numero de la premiere ligne et de la premiere colonne a partir duquel on commence a prendre en compte les elements de la matrice

recherche du premier element non nul de la sous-matrice

on dumpe la colonne J...

Parameters

MAT	AT
level	evel

Definition at line 72 of file sub-matrix.c.

 {
     int i,j;
     int I = 0;
     bool trouve = false;
     int n = MATRIX_NB_LINES(MAT);
     int m= MATRIX_NB_COLUMNS(MAT);
     /* recherche du premier element non nul de la sous-matrice */
     for (i = level+1; i<=n && !trouve ; i++) {
         for (j = level+1; j<= m && (MATRIX_ELEM(MAT,i,j) == 0); j++);
         if(j <= m) {
             /* on dumpe la colonne J... */
             trouve = true;
             I = i;
         }
     }
     return (I);
 }

References level, MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.

Referenced by matrix_coeff_nnul().

Here is the caller graph for this function:

◆ matrix_maj_col()

void matrix_maj_col	(	Pmatrix	A,
		Pmatrix	P,
		int	level
	)

void matrix_maj_col(Pmatrix A, matrice P, int level): Calcul de la matrice permettant de remplacer chaque terme de la premiere ligne de la sous-matrice A(level+1 ..n, level+1 ..m) autre que le premier terme A11=A(level+1,level+1) par le reste de sa division entiere par A11

La matrice P est modifiee.

Les parametres de la fonction :

int A[1..n,1..m] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice (unused) !int P[] : matrice de dimension au moins P[1..n, 1..n] int level : niveau de la matrice i.e. numero de la premiere ligne et de la premiere colonne a partir duquel on commence a prendre en compte les elements de la matrice RGSUSED

Parameters

level evel

Definition at line 256 of file sub-matrix.c.

 {
     Value A11;
     int i;
     Value x;
     int n = MATRIX_NB_LINES(A);
     matrix_identity(P,0);
  
     A11 =SUB_MATRIX_ELEM(A,1,1,level);
     for (i=2+level; i<=n; i++) {
         x = MATRIX_ELEM(A,i,1+level);
         value_division(x,A11);
         MATRIX_ELEM(P,i,1+level) = value_uminus(x);
     }
 }

References level, MATRIX_ELEM, matrix_identity(), MATRIX_NB_LINES, SUB_MATRIX_ELEM, value_division, value_uminus, and x.

Referenced by smith_int().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_maj_line()

void matrix_maj_line	(	Pmatrix	A,
		Pmatrix	Q,
		int	level
	)

void matrix_maj_line(Pmatrix A, matrice Q, int level): Calcul de la matrice permettant de remplacer chaque terme de la premiere ligne autre que le premier terme A11=A(level+1,level+1) par le reste de sa division entiere par A11

La matrice Q est modifiee.

Les parametres de la fonction :

int A[] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice !int Q[] : matrice int level : niveau de la matrice i.e. numero de la premiere ligne et de la premiere colonne a partir duquel on commence a prendre en compte les elements de la matrice

Parameters

level evel

Definition at line 294 of file sub-matrix.c.

 {
     Value A11;
     int j;
     Value x;
     int m= MATRIX_NB_COLUMNS(A);
     matrix_identity(Q,0);
     A11 =SUB_MATRIX_ELEM(A,1,1,level);
     for (j=2+level; j<=m; j++) {
         x = value_div(MATRIX_ELEM(A,1+level,j),A11);
         MATRIX_ELEM(Q,1+level,j) = value_uminus(x);
     }
 }

References level, MATRIX_ELEM, matrix_identity(), MATRIX_NB_COLUMNS, Q, SUB_MATRIX_ELEM, value_div, value_uminus, and x.

Referenced by smith_int().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_min()

void matrix_min	(	Pmatrix	MAT,
		int *	i_min,
		int *	j_min,
		int	level
	)

void matrix_min(Pmatrix MAT, int * i_min, int * j_min, int level): Recherche des coordonnees (*i_min, *j_min) de l'element de la sous-matrice MAT(level+1 ..n, level+1 ..m) dont la valeur absolue est la plus petite et non nulle.

QQ i dans [level+1 ..n] QQ j dans [level+1 ..m] | MAT[*i_min, *j_min] | <= | MAT[i, j]

resultat retourne par la fonction :

les parametres i_min et j_min sont modifies.

parametres de la fonction :

int MAT[] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice !int i_min : numero de la ligne a laquelle se trouve le plus petit element !int j_min : numero de la colonne a laquelle se trouve le plus petit int level : niveau de la matrice i.e. numero de la premiere ligne et de la premiere colonne a partir duquel on commence a prendre en compte les elements de la matrice element

initialisation du minimum car recherche d'un minimum non nul

Parameters

MAT	AT
i_min	_min
j_min	_min
level	evel

Definition at line 196 of file sub-matrix.c.

 {
     int i,j;
     int vali= 0;
     int valj=0;
     Value min=VALUE_ZERO;
     Value val=VALUE_ZERO;
     bool trouve = false;
  
     int n = MATRIX_NB_LINES(MAT);
     int m= MATRIX_NB_COLUMNS(MAT);
     /*  initialisation du minimum  car recherche d'un minimum non nul*/
     for (i=1+level;i<=n && !trouve;i++)
         for(j = level+1; j <= m && !trouve; j++) {
             min = MATRIX_ELEM(MAT,i,j);
             min = value_abs(min);
             if(value_notzero_p(min)) {
                 trouve = true;
                 vali = i;
                 valj = j;
             }
         }
  
     for (i=1+level;i<=n;i++)
         for (j=1+level;j<=m && value_gt(min,VALUE_ONE); j++) {
             val = MATRIX_ELEM(MAT,i,j);
             val = value_abs(val);
             if (value_notzero_p(val) && value_lt(val,min)) {
                 min = val;
                 vali= i;
                 valj =j;
             }
         }
     *i_min = vali;
     *j_min = valj;
 }

References level, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, min, value_abs, value_gt, value_lt, value_notzero_p, VALUE_ONE, and VALUE_ZERO.

Referenced by matrix_smith(), and smith_int().

Here is the caller graph for this function:

◆ matrix_multiply()

void matrix_multiply	(	const Pmatrix	a,
		const Pmatrix	b,
		Pmatrix	c
	)

void matrix_multiply(Pmatrix a, Pmatrix b, Pmatrix c): multiply rational matrix a by rational matrix b and store result in matrix c

 a is a (pxq) matrix, b a (qxr) and c a (pxr)

 c := a x b ;

Algorithm used is directly from definition, and space has to be provided for output matrix c by caller. Matrix c is not necessarily normalized: its denominator may divide all its elements (see matrix_normalize()).

Precondition: p > 0; q > 0; r > 0; c != a; c != b; – aliasing between c and a or b – is not supported

validate dimensions

simplified aliasing test

set denominator

use ordinary school book algorithm

Definition at line 95 of file matrix.c.

 {
   /* validate dimensions */
   int   p = MATRIX_NB_LINES(a);
   int   q = MATRIX_NB_COLUMNS(a);
   int   r = MATRIX_NB_COLUMNS(b);
   // should check that all dimensions are compatible & well allocated?!
  
   assert(p > 0 && q > 0 && r > 0);
   /* simplified aliasing test */
   assert(c != a && c != b);
  
   /* set denominator */
   MATRIX_DENOMINATOR(c) =
     value_mult(MATRIX_DENOMINATOR(a), MATRIX_DENOMINATOR(b));
  
   /* use ordinary school book algorithm */
   int i, j, k;
   for(i=1; i<=p; i++) {
     for(j=1; j<=r; j++) {
             Value v = VALUE_ZERO;
             for(k=1; k<=q; k++) {
         Value va = MATRIX_ELEM(a, i, k);
         Value vb = MATRIX_ELEM(b, k, j);
         value_addto(v, value_mult(va, vb));
             }
             MATRIX_ELEM(c, i, j) = v;
     }
   }
 }

References assert, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, value_addto, value_mult, and VALUE_ZERO.

Referenced by extract_lattice(), fusion_buffer(), make_reindex(), matrices_to_1D_lattice(), matrix_general_inversion(), matrix_unimodular_inversion(), prepare_reindexing(), region_sc_minimal(), sc_resol_smith(), smith_int(), and Tiling_buffer_allocation().

Here is the caller graph for this function:

◆ matrix_new()

Pmatrix matrix_new	(	int	m,
		int	n
	)

cproto-generated files

alloc.c

cproto-generated files

Definition at line 41 of file alloc.c.

 {
   Pmatrix a = (Pmatrix) malloc(sizeof(Smatrix));
   a->denominator = VALUE_ONE;
   a->number_of_lines = m;
   a->number_of_columns = n;
   a->coefficients = (Value *) malloc(sizeof(Value)*((n*m)));
   return a;
 }

References Pmatrix::coefficients, Pmatrix::denominator, malloc(), Pmatrix::number_of_columns, Pmatrix::number_of_lines, and VALUE_ONE.

Referenced by call_rwt(), compute_delay_merged_nest(), compute_delay_tiled_nest(), extract_lattice(), fusion_buffer(), main(), make_reindex(), matrices_to_1D_lattice(), matrix_determinant(), matrix_fscan(), matrix_general_inversion(), matrix_hermite(), matrix_sub_determinant(), matrix_unimodular_inversion(), prepare_reindexing(), region_sc_minimal(), sc_resol_smith(), smith_int(), Tiling2_buffer(), Tiling_buffer_allocation(), transformer_to_1D_lattice(), xml_Connection(), xml_ConstOffset(), xml_LoopOffset(), and xml_Transposition().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_normalize()

void matrix_normalize ( Pmatrix a )

void matrix_normalize(Pmatrix a)

 A rational matrix is stored as an integer one with one extra
 integer, the denominator for all the elements. To normalise the
 matrix in this sense means to reduce this denominator to the
 smallest positive number possible. All elements are also reduced
 to their smallest possible value.

Precondition: MATRIX_DENOMINATOR(a)!=0

we must find the GCD of all elements of matrix

factor out

ensure denominator is positive

FI: this code is useless because pgcd()always return a positive integer, even if a is the null matrix; its denominator CANNOT be 0

Definition at line 136 of file matrix.c.

 {
   int m = MATRIX_NB_LINES(a);
   int n = MATRIX_NB_COLUMNS(a);
   assert(MATRIX_DENOMINATOR(a) != 0);
  
   /* we must find the GCD of all elements of matrix */
   Value factor = MATRIX_DENOMINATOR(a);
  
   int i, j;
   for(i=1; i<=m; i++)
     for(j=1; j<=n; j++)
             factor = pgcd(factor, MATRIX_ELEM(a,i,j));
  
   /* factor out */
   if (value_notone_p(factor)) {
     for(i=1; i<=m; i++)
             for(j=1; j<=n; j++)
         value_division(MATRIX_ELEM(a,i,j), factor);
     value_division(MATRIX_DENOMINATOR(a),factor);
   }
  
   /* ensure denominator is positive */
   /* FI: this code is useless because pgcd()always return a positive integer,
      even if a is the null matrix; its denominator CANNOT be 0 */
   assert(value_pos_p(MATRIX_DENOMINATOR(a)));
  
 /*
     if(MATRIX_DENOMINATOR(a) < 0) {
         MATRIX_DENOMINATOR(a) = MATRIX_DENOMINATOR(a)*-1;
         for(loop1=1; loop1<=n; loop1++)
             for(loop2=1; loop2<=m; loop2++)
                 MATRIX_ELEM(a,loop1,loop2) = 
                     -1 * MATRIX_ELEM(a,loop1,loop2);
     }*/
 }

References assert, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, pgcd, value_division, value_notone_p, and value_pos_p.

Referenced by make_reindex(), and prepare_reindexing().

Here is the caller graph for this function:

◆ matrix_normalizec()

void matrix_normalizec ( Pmatrix MAT )

void matrix_normalizec(Pmatrix MAT): Normalisation des coefficients de la matrice MAT, i.e.

division des coefficients de la matrice MAT et de son denominateur par leur pgcd

La matrice est modifiee.

Les parametres de la fonction :

!int MAT[] : matrice de dimension (n,m) int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice

??? matrix is supposed to be positive?

Parameters

MAT AT

Definition at line 187 of file matrix.c.

 {
   int m = MATRIX_NB_LINES(MAT);
   int n = MATRIX_NB_COLUMNS(MAT);
   assert( n>0 && m>0);
  
   Value a = MATRIX_DENOMINATOR(MAT);
   int i;
   for (i = 0; i<m*n  && value_gt(a, VALUE_ONE); i++)
     a = pgcd(a, MAT->coefficients[i]);
  
   if (value_gt(a,VALUE_ONE)) {
     for (i = 0; i<m*n; i++)
             value_division(MAT->coefficients[i],a);
   }
 }

References assert, Pmatrix::coefficients, MATRIX_DENOMINATOR, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, pgcd, value_division, value_gt, and VALUE_ONE.

Referenced by sc_resol_smith(), and smith_int().

Here is the caller graph for this function:

◆ matrix_nulle()

void matrix_nulle ( Pmatrix Z )

void matrix_nulle(Pmatrix Z): Initialisation de la matrice Z a la valeur matrice nulle

Post-condition:

QQ i dans [1..n] QQ j dans [1..n] Z(i,j) == 0

Definition at line 293 of file matrix.c.

 {
   int m = MATRIX_NB_LINES(Z);
   int n = MATRIX_NB_COLUMNS(Z);
   int i,j;
   for (i=1; i<=m; i++)
     for (j=1; j<=n; j++)
             MATRIX_ELEM(Z,i,j) = VALUE_ZERO;
   MATRIX_DENOMINATOR(Z) = VALUE_ONE;
 }

References MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, VALUE_ONE, and VALUE_ZERO.

Referenced by build_contraction_matrices(), compute_delay_merged_nest(), compute_delay_tiled_nest(), constraints_to_matrices(), constraints_with_sym_cst_to_matrices(), egalites_to_matrice(), matrix_diagonal_inversion(), matrix_hermite(), matrix_perm_col(), matrix_perm_line(), matrix_triangular_inversion(), my_constraints_with_sym_cst_to_matrices(), sc_resol_smith(), smith_int(), and sys_mat_conv().

Here is the caller graph for this function:

◆ matrix_nulle_p()

bool matrix_nulle_p ( Pmatrix Z )

bool matrix_nulle_p(Pmatrix Z): test de nullite de la matrice Z

QQ i dans [1..n] QQ j dans [1..n] Z(i,j) == 0

Definition at line 311 of file matrix.c.

 {
   int m = MATRIX_NB_LINES(Z);
   int n = MATRIX_NB_COLUMNS(Z);
   int i, j;
   for (i=1; i<=m; i++)
     for (j=1; j<=n; j++)
             if (MATRIX_ELEM(Z,i,j) != VALUE_ZERO)
         return false;
   return true;
 }

References MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, and VALUE_ZERO.

◆ matrix_perm_col()

void matrix_perm_col	(	Pmatrix	MAT,
		int	k,
		int	level
	)

void matrix_perm_col(Pmatrix MAT, int k, int level): Calcul de la matrice de permutation permettant d'amener la k-ieme ligne de la matrice MAT(1..n,1..m) a la ligne (level + 1).

Si l'on veut amener la k-ieme ligne de la matrice en premiere ligne 'level' doit avoir la valeur 0

parametres de la fonction :

!int MAT[] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice (unused) int k : numero de la ligne a remonter a la premiere ligne int level : niveau de la matrice i.e. numero de la premiere ligne et de la premiere colonne a partir duquel on commence a prendre en compte les elements de la matrice

Note: pour eviter une multiplication de matrice en O(n**3), il vaudrait mieux programmer directement la permutation en O(n**2) sans multiplications Il est inutile de faire souffrir notre chip SPARC! (FI) RGSUSED

Parameters

MAT	AT
level	evel

Definition at line 115 of file sub-matrix.c.

 {
     int i,j;
     int n = MATRIX_NB_LINES(MAT);
     matrix_nulle(MAT);
     if (level > 0) {
         for (i=1;i<=level; i++)
             MATRIX_ELEM(MAT,i,i) = VALUE_ONE;
     }
  
     for (i=1+level,j=k; i<=n; i++,j++)
     {
         if (j == n+1) j = 1 + level;
         MATRIX_ELEM(MAT,i,j)=VALUE_ONE;
     }
 }

References level, MATRIX_ELEM, MATRIX_NB_LINES, matrix_nulle(), and VALUE_ONE.

Referenced by smith_int().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_perm_line()

void matrix_perm_line	(	Pmatrix	MAT,
		int	k,
		int	level
	)

void matrix_perm_line(Pmatrix MAT, int k, int level): Calcul de la matrice de permutation permettant d'amener la k-ieme colonne de la sous-matrice MAT(1..n,1..m) a la colonne 'level + 1' (premiere colonne de la sous matrice MAT(level+1 ..n,level+1 ..m)).

parametres de la fonction :

!int MAT[] : matrice int n : nombre de lignes de la matrice (unused) int m : nombre de colonnes de la matrice int k : numero de la colonne a placer a la premiere colonne int level : niveau de la matrice i.e. numero de la premiere ligne et de la premiere colonne a partir duquel on commence a prendre en compte les elements de la matrice RGSUSED

Parameters

MAT	AT
level	evel

Definition at line 150 of file sub-matrix.c.

 {
     int i,j;
     int m= MATRIX_NB_COLUMNS(MAT);
     matrix_nulle(MAT);
     if(level > 0) {
         for (i = 1; i <= level;i++)
             MATRIX_ELEM(MAT,i,i) = VALUE_ONE;
     }
  
     for(j=1,i=k-level; j <= m - level; j++,i++) {
         if(i == m-level+1)
             i = 1;
         SUB_MATRIX_ELEM(MAT,i,j,level) = VALUE_ONE;
     }
 }

References level, MATRIX_ELEM, MATRIX_NB_COLUMNS, matrix_nulle(), SUB_MATRIX_ELEM, and VALUE_ONE.

Referenced by smith_int().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_pr_quot()

void matrix_pr_quot	(	FILE *	,
		Value	,
		Value
	)

◆ matrix_print()

void matrix_print ( Pmatrix a )

void matrix_print(matrice a): print an (nxm) rational matrix

Note: the output format is incompatible with matrix_fscan() this should be implemented as a macro, but it's a function for dbx's sake

Definition at line 70 of file matrix_io.c.

 {
     matrix_fprint(stdout,a);
 }

References matrix_fprint().

Referenced by Hierarchical_tiling(), matrix_smith(), sc_resol_smith(), smith_int(), and Tiling2_buffer().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_rm()

void matrix_rm ( Pmatrix a )

Definition at line 52 of file alloc.c.

 {
   if (a) {
     free(a->coefficients);
     free(a);
   }
 }

References Pmatrix::coefficients, and free().

Here is the call graph for this function:

◆ matrix_smith()

void matrix_smith	(	Pmatrix	MAT,
		Pmatrix	P,
		Pmatrix	D,
		Pmatrix	Q
	)

smith.c

D est la forme reduite de Smith, P et Q sont des matrices unimodulaires; telles que D == P x MAT x Q

(c.f. Programmation Lineaire. M.MINOUX. (83))

int MAT[n,m] : matrice int n : nombre de lignes de la matrice MAT int m : nombre de colonnes de la matrice MAT int P[n,n] : matrice int D[n,m] : matrice (quasi-diagonale) reduite de Smith int Q[m,m] : matrice

Les 3 matrices P(nxn), Q(mxm) et D(nxm) doivent etre allouees avant le calcul.

Note: les determinants des matrices MAT, P, Q et D ne sont pas utilises.

le plus petit element sur la diagonale

le rest de la division par ALL

precondition sur les parametres

le transformation n'est pas fini.

Parameters

MAT AT

Definition at line 68 of file smith.c.

 {
     int n_min,m_min;
     int level = 0;
     Value ALL;        /* le plus petit element sur la diagonale */
     Value x=VALUE_ZERO;          /* le rest de la division par ALL */
     int i;
     
     bool stop = false;
     bool next = true;
  
     /* precondition sur les parametres */
     int n = MATRIX_NB_LINES(MAT);
     int m = MATRIX_NB_COLUMNS(MAT);
     assert(m > 0 && n >0);
     matrix_assign(MAT,D);
     assert(value_one_p(MATRIX_DENOMINATOR(D)));
  
     matrix_identity(P,0);
     matrix_identity(Q,0);
  
     while (!stop) {
         matrix_min(D,&n_min,&m_min,level);
                 
         if ((n_min == 0) && (m_min == 0))
             stop = true;
         else {
             /* le transformation n'est pas fini. */
             if (n_min > level +1) {
                 matrix_swap_rows(D,level+1,n_min);
                 matrix_swap_rows(P,level+1,n_min);
             }
 #ifdef TRACE
             (void) printf (" apres alignement du plus petit element a la premiere ligne \n");
             matrix_print(D);
 #endif
             if (m_min >1+level) {
                 matrix_swap_columns(D,level+1,m_min);
                 matrix_swap_columns(Q,level+1,m_min);
             }
 #ifdef TRACE
             (void) printf (" apres alignement du plus petit element a la premiere colonne\n");
             matrix_print(D);
 #endif
            
             ALL = SUB_MATRIX_ELEM(D,1,1,level);
             if (matrix_line_el(D,level) != 0) 
                 for (i=level+2; i<=m; i++) {
                     x = value_div(MATRIX_ELEM(D,level+1,i),ALL);
                     matrix_subtraction_column(D,i,level+1,x);
                     matrix_subtraction_column(Q,i,level+1,x);
                     next = false;
                 }
             if (matrix_col_el(D,level) != 0) 
                 for(i=level+2;i<=n;i++) {
                     x = value_div(MATRIX_ELEM(D,i,level+1),ALL);
                     matrix_subtraction_line(D,i,level+1,x);
                     matrix_subtraction_line(P,i,level+1,x);
                     next = false;
                 }
 #ifdef TRACE
                 (void) printf("apres division par A(%d,%d) des termes de la %d-ieme ligne et de la %d-em colonne \n",level+1,level+1,level+1,level+1);
                 matrix_print(D);
 #endif
             if (next) level++;
             next = true;
         }
     }
  
 #ifdef TRACE
     (void) printf (" la  matrice D apres transformation est la suivante :");
     matrix_print(D);
  
     (void) printf (" la matrice P est \n");
     matrix_print(P);
  
     (void) printf (" la matrice Q est \n");
     matrix_print(Q);
 #endif
 }

References ALL, assert, D, level, matrix_assign(), matrix_col_el(), MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_identity(), matrix_line_el(), matrix_min(), MATRIX_NB_COLUMNS, MATRIX_NB_LINES, matrix_print(), matrix_subtraction_column(), matrix_subtraction_line(), matrix_swap_columns(), matrix_swap_rows(), printf(), Q, SUB_MATRIX_ELEM, value_div, value_one_p, VALUE_ZERO, and x.

Referenced by main(), matrices_to_1D_lattice(), and sc_resol_smith().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_sub_determinant()

void matrix_sub_determinant	(	Pmatrix	,
		int	,
		int	,
		Value	[]
	)

◆ matrix_substract()

void matrix_substract	(	Pmatrix	a,
		Pmatrix	b,
		Pmatrix	c
	)

void matrix_substract(Pmatrix a, Pmatrix b, Pmatrix c): substract rational matrix c from rational matrix b and store result in matrix a

 a is a (nxm) matrix, b a (nxm) and c a (nxm)

 a = b - c ;

Algorithm used is directly from definition, and space has to be provided for output matrix a by caller. Matrix a is not necessarily normalized: its denominator may divide all its elements (see matrix_normalize()).

Precondition: n > 0; m > 0; Note: aliasing between a and b or c is supported

denominators of b, c

ppcm of b,c

precondition

Definition at line 435 of file matrix.c.

 {
   Value d1,d2;   /* denominators of b, c */
   Value lcm;     /* ppcm of b,c */
   int i,j;
  
   /* precondition */
   int m = MATRIX_NB_LINES(a);
   int n = MATRIX_NB_COLUMNS(a);
   assert(n>0 && m>0);
   assert(value_pos_p(MATRIX_DENOMINATOR(b)));
   assert(value_pos_p(MATRIX_DENOMINATOR(c)));
  
   d1 = MATRIX_DENOMINATOR(b);
   d2 = MATRIX_DENOMINATOR(c);
   if (value_eq(d1,d2)){
     for (i=1; i<=m; i++)
             for (j=1; j<=n; j++)
         MATRIX_ELEM(a,i,j) =
           value_minus(MATRIX_ELEM(b,i,j),MATRIX_ELEM(c,i,j));
     MATRIX_DENOMINATOR(a) = d1;
   }
   else {
     lcm = ppcm(d1,d2);
     d1 = value_div(lcm,d1);
     d2 = value_div(lcm,d2);
     for (i=1; i<=m; i++)
       for (j=1; j<=n; j++)
         MATRIX_ELEM(a,i,j) =
           value_minus(value_mult(MATRIX_ELEM(b,i,j),d1),
                       value_mult(MATRIX_ELEM(c,i,j),d2));
     MATRIX_DENOMINATOR(a) = lcm;
   }
 }

References assert, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, ppcm(), value_div, value_eq, value_minus, value_mult, and value_pos_p.

Referenced by compute_delay_merged_nest(), compute_delay_tiled_nest(), fusion_buffer(), and Tiling_buffer_allocation().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_subtraction_column()

void matrix_subtraction_column	(	Pmatrix	MAT,
		int	c1,
		int	c2,
		Value	x
	)

void matrix_subtraction_column(Pmatrix MAT,int c1,int c2,int x): Soustrait x fois la colonne c2 de la colonne c1 Precondition: n > 0; m > 0; 0 < c1, c2 < m; Effet: c1[0..n-1] = c1[0..n-1] - x*c2[0..n-1].

Les parametres de la fonction :

int MAT[] : matrice int c1 : numero du colonne int c2 : numero du colonne int x :

Parameters

MAT	AT
c1	1
c2	2

Definition at line 518 of file matrix.c.

 {
   int m = MATRIX_NB_LINES(MAT);
   int i;
   for (i=1; i<=m; i++)
     value_substract(MATRIX_ELEM(MAT,i,c1),
                     value_mult(x, MATRIX_ELEM(MAT,i,c2)));
 }

References MATRIX_ELEM, MATRIX_NB_LINES, value_mult, value_substract, and x.

Referenced by matrix_hermite(), matrix_smith(), and matrix_unimodular_triangular_inversion().

Here is the caller graph for this function:

◆ matrix_subtraction_line()

void matrix_subtraction_line	(	Pmatrix	MAT,
		int	r1,
		int	r2,
		Value	x
	)

void matrix_subtraction_line(Pmatrix MAT,int r1,int r2,int x): Soustrait x fois la ligne r2 de la ligne r1 Precondition: n > 0; m > 0; 0 < r1, r2 < n; Effet: r1[0..m-1] = r1[0..m-1] - x*r2[0..m-1]

Les parametres de la fonction :

int MAT[] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice int r1 : numero du ligne int r2 : numero du ligne int x :

Parameters

MAT	AT
r1	1
r2	2

Definition at line 541 of file matrix.c.

 {
   int n = MATRIX_NB_COLUMNS(MAT);
   int i;
   for (i=1; i<=n; i++)
     value_substract(MATRIX_ELEM(MAT,r1,i),
                     value_mult(x,MATRIX_ELEM(MAT,r2,i)));
 }

References MATRIX_ELEM, MATRIX_NB_COLUMNS, value_mult, value_substract, and x.

Referenced by matrix_smith().

Here is the caller graph for this function:

◆ matrix_swap_columns()

void matrix_swap_columns	(	Pmatrix	A,
		int	c1,
		int	c2
	)

void matrix_swap_columns(Pmatrix a, int c1, int c2): exchange columns c1,c2 of an (nxm) rational matrix

 Precondition:      n > 0; m > 0; 0 < c1 <= m; 0 < c2 <= m;

Parameters

c1	1
c2	2

Definition at line 209 of file matrix.c.

 {
   int m = MATRIX_NB_LINES(A);
   int n = MATRIX_NB_COLUMNS(A);
   assert(n > 0 && m > 0);
   assert(0 < c1 && c1 <= n);
   assert(0 < c2 && c2 <= n);
  
   int i;
   for(i=1; i<=m; i++) {
     Value temp = MATRIX_ELEM(A,i,c1);
     MATRIX_ELEM(A,i,c1) = MATRIX_ELEM(A,i,c2);
     MATRIX_ELEM(A,i,c2) = temp;
   }
 }

References assert, MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.

Referenced by matrix_hermite(), and matrix_smith().

Here is the caller graph for this function:

◆ matrix_swap_rows()

void matrix_swap_rows	(	Pmatrix	A,
		int	r1,
		int	r2
	)

void matrix_swap_rows(Pmatrix a, int r1, int r2): exchange rows r1 and r2 of an (nxm) rational matrix a

Precondition: n > 0; m > 0; 1 <= r1 <= n; 1 <= r2 <= n

Parameters

r1	1
r2	2

Definition at line 230 of file matrix.c.

 {
   int m = MATRIX_NB_LINES(A);
   int n = MATRIX_NB_COLUMNS(A);
   assert(n > 0);
   assert(m > 0);
   assert(0 < r1 && r1 <= m);
   assert(0 < r2 && r2 <= m);
  
   int i;
   for(i=1; i<=n; i++) {
     Value temp = MATRIX_ELEM(A,r1,i);
     MATRIX_ELEM(A,r1,i) = MATRIX_ELEM(A,r2,i);
     MATRIX_ELEM(A,r2,i) = temp;
   }
 }

References assert, MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.

Referenced by matrix_hermite(), and matrix_smith().

Here is the caller graph for this function:

◆ matrix_transpose()

void matrix_transpose	(	const Pmatrix	A,
		Pmatrix	At
	)

void matrix_transpose(Pmatrix a, Pmatrix a_t): transpose an (nxm) rational matrix a into a (mxn) rational matrix a_t

At := A ;

verification step

copy from a to a_t

Parameters

At t

Definition at line 64 of file matrix.c.

 {
   /* verification step */
   int m = MATRIX_NB_LINES(A);
   int n = MATRIX_NB_COLUMNS(A);
   assert(n >= 0 && m >= 0);
  
   /* copy from a to a_t */
   MATRIX_DENOMINATOR(At) = MATRIX_DENOMINATOR(A);
   int i, j;
   for(i=1; i<=m; i++)
     for(j=1; j<=n; j++)
             MATRIX_ELEM(At,j,i) = MATRIX_ELEM(A,i,j);
 }

References assert, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.

Referenced by region_sc_minimal().

Here is the caller graph for this function:

◆ matrix_triangular_inversion()

void matrix_triangular_inversion	(	Pmatrix	h,
		Pmatrix	inv_h,
		bool	infer
	)

void matrix_triangular_inversion(Pmatrix h, Pmatrix inv_h,bool infer) calcul de l'inversion du matrice en forme triangulaire.

soit h matrice de la reduite triangulaire; inv_h est l'inversion de h ; telle que : h * inv_h = I. selon les proprietes de la matrice triangulaire: Aii = a11* ...aii-1*aii+1...*ann; Aij = 0 i>j pour la matrice triangulaire inferieure (infer==true) i<j pour la matrice triangulaire superieure (infer==false)

les parametres de la fonction : matrice h : matrice en forme triangulaire – input matrice inv_h : l'inversion de h – output int n : dimension de la matrice caree – input bool infer : le type de triangulaire – input

denominateur

determinant

tests des preconditions

calcul du determinant de h

calcul du denominateur de inv_h

calcul des sub_determinants des Aii

calcul des sub_determinants des Aij (i<j)

Parameters

inv_h	nv_h
infer	nfer

Definition at line 137 of file inversion.c.

 {
     Value deno,deno1;                    /* denominateur */
     Value determinant,sub_determinant;  /* determinant */
     Value gcd;
     int i,j;
     Value aij[2];
     
     /* tests des preconditions */
     int n = MATRIX_NB_LINES(h);
     assert(matrix_triangular_p(h,infer));
     assert(matrix_hermite_rank(h)==n);
     assert(value_pos_p(MATRIX_DENOMINATOR(h)));
  
     matrix_nulle(inv_h);
     deno = MATRIX_DENOMINATOR(h);
     deno1 = deno;
     MATRIX_DENOMINATOR(h) = VALUE_ONE;
     /* calcul du determinant de h */
     determinant = VALUE_ONE;
     for (i= 1; i<=n; i++)
         value_product(determinant, MATRIX_ELEM(h,i,i));
  
     /* calcul du denominateur de inv_h */
     gcd = pgcd(deno1,determinant);
     if (value_notone_p(gcd)){
         value_division(deno1,gcd);
         value_division(determinant,gcd);
     }
     if (value_neg_p(determinant)){
         value_oppose(deno1); 
         value_oppose(determinant);
     }
     MATRIX_DENOMINATOR(inv_h) = determinant;
     /* calcul des sub_determinants des Aii */
     for (i=1; i<=n; i++){
         sub_determinant = VALUE_ONE;
         for (j=1; j<=n; j++)
             if (j != i)
                 value_product(sub_determinant, MATRIX_ELEM(h,j,j));
         MATRIX_ELEM(inv_h,i,i) = value_mult(sub_determinant,deno1);
     }
     /* calcul des sub_determinants des Aij (i<j) */
     switch(infer) {
     case true:
         for (i=1; i<=n; i++)
             for(j=i+1; j<=n;j++){
                 matrix_sub_determinant(h,i,j,aij);
                 assert(value_one_p(aij[0]));
                 MATRIX_ELEM(inv_h,j,i) = value_mult(aij[1],deno1);
             }
         break;
     case false:
         for (i=1; i<=n; i++)
             for(j=1; j<i; j++){
                 matrix_sub_determinant(h,i,j,aij);
                 assert(value_one_p(aij[0]));
                 MATRIX_ELEM(inv_h,j,i) = value_mult(aij[1],deno1);
             }
         break;
    }
     MATRIX_DENOMINATOR(h) = deno;
 }

References assert, MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_hermite_rank(), MATRIX_NB_LINES, matrix_nulle(), matrix_sub_determinant(), matrix_triangular_p(), pgcd, value_division, value_mult, value_neg_p, value_notone_p, VALUE_ONE, value_one_p, value_oppose, value_pos_p, and value_product.

Referenced by matrix_general_inversion().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_triangular_p()

bool matrix_triangular_p	(	Pmatrix	Z,
		bool	inferieure
	)

bool matrix_triangular_p(Pmatrix Z, bool inferieure): test de triangularite de la matrice Z

si inferieure == true QQ i dans [1..n] QQ j dans [i+1..m] Z(i,j) == 0

si inferieure == false (triangulaire superieure) QQ i dans [1..n] QQ j dans [1..i-1] Z(i,j) == 0

Les parametres de la fonction :

int Z[] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice

Parameters

inferieure nferieure

Definition at line 367 of file matrix.c.

 {
   int m = MATRIX_NB_LINES(Z);
   int n = MATRIX_NB_COLUMNS(Z);
   int i,j;
   for (i=1; i<=m; i++)
     if(inferieure) {
             for (j=i+1; j<=n; j++)
         if(MATRIX_ELEM(Z,i,j)!=0)
           return false;
     }
     else
             for (j=1; j<=i-1; j++)
         if(MATRIX_ELEM(Z,i,j)!=0)
           return false;
   return true;
 }

References MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.

Referenced by matrix_triangular_inversion(), and matrix_triangular_unimodular_p().

Here is the caller graph for this function:

◆ matrix_triangular_unimodular_p()

bool matrix_triangular_unimodular_p	(	Pmatrix	Z,
		bool	inferieure
	)

bool matrix_triangular_unimodular_p(Pmatrix Z, bool inferieure) test de la triangulaire et unimodulaire de la matrice Z.

si inferieure == true QQ i dans [1..n] QQ j dans [i+1..n] Z(i,j) == 0 i dans [1..n] Z(i,i) == 1

si inferieure == false (triangulaire superieure) QQ i dans [1..n] QQ j dans [1..i-1] Z(i,j) == 0 i dans [1..n] Z(i,i) == 1 les parametres de la fonction : matrice Z : la matrice entre

Parameters

inferieure nferieure

Definition at line 403 of file matrix.c.

 {
   int m = MATRIX_NB_LINES(Z);
   assert(MATRIX_NB_COLUMNS(Z) == m);
   bool triangulaire = matrix_triangular_p(Z,inferieure);
   if (triangulaire) {
     int i;
     for(i=1; i<=m; i++)
             if (value_notone_p(MATRIX_ELEM(Z,i,i)))
         return false;
     return true;
   }
   else
     return false;
 }

References assert, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, matrix_triangular_p(), and value_notone_p.

Referenced by extract_lattice(), matrix_unimodular_inversion(), and matrix_unimodular_triangular_inversion().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ matrix_uminus()

void matrix_uminus	(	Pmatrix	A,
		Pmatrix	mA
	)

void matrix_uminus(A, mA)

computes mA = - A

input: A, larger allocated mA output: none modifies: mA

Parameters

mA A

Definition at line 558 of file matrix.c.

 {
   assert(MATRIX_NB_LINES(mA)>=MATRIX_NB_LINES(A) &&
          MATRIX_NB_COLUMNS(mA)>=MATRIX_NB_COLUMNS(A));
  
   int i,j;
   for (i=1; i<=MATRIX_NB_LINES(A); i++)
     for (j=1; j<=MATRIX_NB_COLUMNS(A); j++)
             MATRIX_ELEM(mA, i, j) = value_uminus(MATRIX_ELEM(A, i, j));
 }

References assert, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, and value_uminus.

Referenced by extract_lattice().

Here is the caller graph for this function:

◆ matrix_unimodular_inversion()

void matrix_unimodular_inversion	(	Pmatrix	u,
		Pmatrix	inv_u
	)

void matrix_unimodular_inversion(Pmatrix u, Pmatrix inv_u) calcul de l'inversion de la matrice unimodulaire.

algorithme :

calcul la forme hermite de la matrice u : PUQ = H_U (unimodulaire triangulaire); -1 -1
U = Q (H_U) P.

les parametres de la fonction : matrice u : matrice unimodulaire -— input matrice inv_u : l'inversion de u -— output int n : dimension de la matrice -— input

ne utilise pas

test

Parameters

inv_u nv_u

Definition at line 261 of file inversion.c.

 {
     int n = MATRIX_NB_LINES(u);
     Pmatrix p = matrix_new(n,n);
     Pmatrix q = matrix_new(n,n);
     Pmatrix h_u = matrix_new(n,n);
     Pmatrix inv_h_u = matrix_new(n,n);
     Pmatrix temp = matrix_new(n,n);
     Value det_p,det_q;  /* ne utilise pas */
    
     /* test */
     assert(value_one_p(MATRIX_DENOMINATOR(u)));
  
     matrix_hermite(u,p,h_u,q,&det_p,&det_q);
     assert(matrix_triangular_unimodular_p(h_u,true));
     matrix_unimodular_triangular_inversion(h_u,inv_h_u,true);
     matrix_multiply(q,inv_h_u,temp);
     matrix_multiply(temp,p,inv_u);
 }

References assert, MATRIX_DENOMINATOR, matrix_hermite(), matrix_multiply(), MATRIX_NB_LINES, matrix_new(), matrix_triangular_unimodular_p(), matrix_unimodular_triangular_inversion(), and value_one_p.

Here is the call graph for this function:

◆ matrix_unimodular_triangular_inversion()

void matrix_unimodular_triangular_inversion	(	Pmatrix	u,
		Pmatrix	inv_u,
		bool	infer
	)

inversion.c

void matrix_unimodular_triangular_inversion(Pmatrix u ,Pmatrix inv_u,

bool infer) u soit le matrice unimodulaire triangulaire. si infer = true (triangulaire inferieure), infer = false (triangulaire superieure). calcul de l'inversion de matrice u telle que I = U x INV_U . Les parametres de la fonction :

Pmatrix u : matrice unimodulaire triangulaire – inpout int n : dimension de la matrice caree – inpout bool infer : type de triangulaire – input matrice inv_u : l'inversion de matrice u – output

test de l'unimodularite et de la trangularite de u

Parameters

inv_u	nv_u
infer	nfer

Definition at line 53 of file inversion.c.

 {
     int i, j;
     Value x;
     int n = MATRIX_NB_LINES(u);
     /* test de l'unimodularite et de la trangularite de u */
     assert(matrix_triangular_unimodular_p(u,infer));
  
     matrix_identity(inv_u,0);
     if (infer){
         for (i=n; i>=1;i--)
             for (j=i-1; j>=1; j--){
                 x = MATRIX_ELEM(u,i,j);
                 if (value_notzero_p(x))
                     matrix_subtraction_column(inv_u,j,i,x); 
             }
     }
     else{
         for (i=1; i<=n; i++)
             for(j=i+1; j<=n; j++){
                 x = MATRIX_ELEM(u,i,j);
                 if (value_notzero_p(x))
                     matrix_subtraction_column(inv_u,j,i,x);
             }
     }
 }

References assert, MATRIX_ELEM, matrix_identity(), MATRIX_NB_LINES, matrix_subtraction_column(), matrix_triangular_unimodular_p(), value_notzero_p, and x.

Referenced by extract_lattice(), and matrix_unimodular_inversion().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ordinary_sub_matrix()

void ordinary_sub_matrix	(	Pmatrix	A,
		Pmatrix	A_sub,
		int	i1,
		int	i2,
		int	j1,
		int	j2
	)

void ordinary_sub_matrix(Pmatrix A, A_sub, int i1, i2, j1, j2) input : a initialized matrix A, an uninitialized matrix A_sub, which dimensions are i2-i1+1 and j2-j1+1.

output : nothing. modifies : A_sub is initialized with the elements of A which coordinates range within [i1,i2] and [j1,j2]. comment : A_sub must be already allocated.

Parameters

A_sub	_sub
i1	1
i2	2
j1	1
j2	2

Definition at line 469 of file sub-matrix.c.

 {
     int i, j, i_sub, j_sub;
  
     for(i = i1, i_sub = 1; i <= i2; i++, i_sub ++)
         for(j = j1, j_sub = 1; j <= j2; j++, j_sub ++)
             MATRIX_ELEM(A_sub,i_sub,j_sub) = MATRIX_ELEM(A,i,j);
     
 }

References MATRIX_ELEM.

Referenced by extract_lattice(), and region_sc_minimal().

Here is the caller graph for this function:

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ MATRIX_DENOMINATOR

◆ MATRIX_ELEM

◆ matrix_free

◆ MATRIX_NB_COLUMNS

◆ MATRIX_NB_LINES

◆ matrix_triangular_inferieure_p

◆ matrix_triangular_superieure_p

◆ MATRIX_UNDEFINED

◆ SUB_MATRIX_ELEM

Typedef Documentation

◆ Smatrix

Function Documentation

◆ insert_sub_matrix()

◆ matrices_to_1D_lattice()

◆ matrix_add()

◆ matrix_assign()

◆ matrix_coeff_nnul()

◆ matrix_col_el()

◆ matrix_determinant()

◆ matrix_diagonal_inversion()

◆ matrix_diagonal_p()

◆ matrix_dim_hermite()

◆ matrix_elem()

◆ matrix_elem_ref()

◆ matrix_equality()

◆ matrix_fprint()

◆ matrix_fscan()

◆ matrix_general_inversion()

◆ matrix_hermite()

◆ matrix_hermite_rank()

◆ matrix_identity()

◆ matrix_identity_p()

◆ matrix_line_el()

◆ matrix_line_nnul()

◆ matrix_maj_col()

◆ matrix_maj_line()

◆ matrix_min()

◆ matrix_multiply()

◆ matrix_new()

◆ matrix_normalize()

◆ matrix_normalizec()

◆ matrix_nulle()

◆ matrix_nulle_p()

◆ matrix_perm_col()

◆ matrix_perm_line()

◆ matrix_pr_quot()

◆ matrix_print()

◆ matrix_rm()

◆ matrix_smith()

◆ matrix_sub_determinant()

◆ matrix_substract()

◆ matrix_subtraction_column()

◆ matrix_subtraction_line()

◆ matrix_swap_columns()

◆ matrix_swap_rows()

◆ matrix_transpose()

◆ matrix_triangular_inversion()

◆ matrix_triangular_p()

◆ matrix_triangular_unimodular_p()

◆ matrix_uminus()

◆ matrix_unimodular_inversion()

◆ matrix_unimodular_triangular_inversion()

◆ ordinary_sub_matrix()