matrix.h File Reference

Go to the source code of this file.

Data Structures

struct  Smatrix
 package matrice More...

Defines

#define MATRIX_UNDEFINED   ((Pmatrix) NULL)
#define matrix_free(m)   (free((char *) (m)), (m)=(Pmatrix) NULL)
 Allocation et desallocation d'une matrice.
#define MATRIX_ELEM(matrix, i, j)   ((matrix)->coefficients[(((j)-1)*((matrix)->number_of_lines))+(i)])
 Macros d'acces aux elements d'une matrice.
#define MATRIX_DENOMINATOR(matrix)   ((matrix)->denominator)
 int MATRIX_DENONIMATOR(matrix): acces au denominateur global d'une matrice matrix
#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)
 boolean matrix_triangular_inferieure_p(matrice a): test de triangularite de la matrice a
#define matrix_triangular_superieure_p(a)   matrix_triangular_p(a,FALSE)
 boolean matrix_triangular_superieure_p(matrice a, int n, int m): test de triangularite de la matrice a
#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.

Typedefs

typedef struct Smatrix * Pmatrix
 Warning! Do not modify this file that is automatically generated!
typedef struct Smatrix Smatrix

Functions

Pmatrix matrix_new (int, int)
 alloc.c
void matrix_determinant (Pmatrix, Value[])
 determinant.c
void matrix_sub_determinant (Pmatrix, int, int, Value[])
void matrix_hermite (Pmatrix, Pmatrix, Pmatrix, Pmatrix, Value *, Value *)
 hermite.c
int matrix_hermite_rank (Pmatrix)
 int matrix_hermite_rank(Pmatrix a): rang d'une matrice en forme de hermite
int matrix_dim_hermite (Pmatrix)
 Calcul de la dimension de la matrice de Hermite H.
void matrix_unimodular_triangular_inversion (Pmatrix, Pmatrix, boolean)
 inversion.c
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.
void matrix_triangular_inversion (Pmatrix, Pmatrix, boolean)
 void matrix_triangular_inversion(Pmatrix h, Pmatrix inv_h,boolean infer) calcul de l'inversion du matrice en forme triangulaire.
void matrix_general_inversion (Pmatrix, Pmatrix)
 void matrix_general_inversion(Pmatrix a; Pmatrix inv_a) calcul de l'inversion du matrice general.
void matrix_unimodular_inversion (Pmatrix, Pmatrix)
 void matrix_unimodular_inversion(Pmatrix u, Pmatrix inv_u) calcul de l'inversion de la matrice unimodulaire.
void matrix_transpose (Pmatrix, Pmatrix)
 matrix.c
void matrix_multiply (Pmatrix, 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
void matrix_normalize (Pmatrix)
 void matrix_normalize(Pmatrix a)
void matrix_normalizec (Pmatrix)
 void matrix_normalizec(Pmatrix MAT): Normalisation des coefficients de la matrice MAT, i.e.
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
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
void matrix_assign (Pmatrix, Pmatrix)
 void matrix_assign(Pmatrix A, Pmatrix B) Copie de la matrice A dans la matrice B
boolean matrix_equality (Pmatrix, Pmatrix)
 boolean 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
void matrix_nulle (Pmatrix)
 void matrix_nulle(Pmatrix Z): Initialisation de la matrice Z a la valeur matrice nulle
boolean matrix_nulle_p (Pmatrix)
 boolean matrix_nulle_p(Pmatrix Z): test de nullite de la matrice Z
boolean matrix_diagonal_p (Pmatrix)
 boolean matrix_diagonal_p(Pmatrix Z): test de nullite de la matrice Z
boolean matrix_triangular_p (Pmatrix, boolean)
 boolean matrix_triangular_p(Pmatrix Z, boolean inferieure): test de triangularite de la matrice Z
boolean matrix_triangular_unimodular_p (Pmatrix, boolean)
 boolean matrix_triangular_unimodular_p(Pmatrix Z, boolean inferieure) test de la triangulaire et unimodulaire de la matrice Z.
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
void matrix_add (Pmatrix, Pmatrix, Pmatrix)
 input
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].
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]
void matrix_uminus (Pmatrix, Pmatrix)
 void matrix_uminus(A, mA)
void matrix_fprint (FILE *, Pmatrix)
 matrix_io.c
void matrix_print (Pmatrix)
 void matrix_print(matrice a): print an (nxm) rational matrix
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.
void matrix_pr_quot (FILE *, Value, Value)
void matrix_smith (Pmatrix, Pmatrix, Pmatrix, Pmatrix)
 smith.c
int matrix_line_nnul (Pmatrix, int)
 sub-matrix.c
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).
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)).
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.
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
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
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)
boolean matrix_identity_p (Pmatrix, int)
 boolean 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.
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.
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.
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)
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.
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

Define Documentation

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

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

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.

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

Allocation et desallocation d'une matrice.

Definition at line 81 of file matrix.h.

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

Definition at line 96 of file matrix.h.

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

Definition at line 95 of file matrix.h.

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

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

Definition at line 101 of file matrix.h.

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

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

#define MATRIX_UNDEFINED   ((Pmatrix) NULL)

Definition at line 78 of file matrix.h.

#define SUB_MATRIX_ELEM ( matrix,
i,
j,
level   ) 
Value:
(matrix->coefficients[((j)-1+(level))*\
     ((matrix)->number_of_lines) + (i) + (level)])

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

typedef struct Smatrix * Pmatrix

Warning! Do not modify this file that is automatically generated!

Modify src/Libs/matrix/matrix-local.h instead, to add your own modifications. header file built by cprotopackage matrice Neil Butler, Corinne Ancourt, Francois Irigoin, Yi-qing YangLes matrices sont des matrices pleines, a coeffcients rationnels.

Les matrices sont representes par des tableaux d'entiers mono-dimensionnels Elles sont stockees par colonne ("column-major"), comme en Fortran. Les indices commencent a 1, toujours comme en Fortran et non comme en C.

Le denominateur doit etre strictement positif, i.e. plus grand ou egal a un. Un denominateur nul n'aurait pas de sens. Un denominateur negatif doublerait le nombre de representations possibles d'une matrice.

Les matrices renvoyees par certaines routines, comme matrix_multiply(), ne sont pas normalisees par le pgcd des coefficients et du denominateur pour des raisons d'efficacite. Mais les routines de test, comme matrix_identity_p(), supposent leurs arguments normalises.

Il faudrait sans doute introduire deux niveaux de procedure, un niveau externe sur garantissant la normalisation, et un niveau interne efficace sans normalisation automatique.

La bibliotheque utilise une notion de sous-matrice, definie systematiquement par un parametre appele "level". Seuls les elements dont les indices de lignes et de colonnes sont superieurs a level+1 sont pris en consideration. Il s'agit donc de sous-matrice dont le premier element se trouve sur la diagonale de la matrice complete et dont le dernier element et le dernier element de la matrice complete.

Note: en cas detection d'incoherence, Neil Butler renvoyait un code d'erreur particulier; Francois Irigoin a supprime ces codes de retour et a traite les exceptions par des appels a assert(), et indirectement a abort()

typedef struct Smatrix Smatrix

Function Documentation

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

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

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

Referenced by extract_lattice().

00488 {
00489     int i,j,i_sub,j_sub;
00490 
00491     assert(i1>=1 && j1>=1 && 
00492            i2<=MATRIX_NB_LINES(A) && j2<=MATRIX_NB_COLUMNS(A) &&
00493            i2-i1<MATRIX_NB_LINES(A_sub) && j2-j1<MATRIX_NB_COLUMNS(A_sub));
00494 
00495     for (i = i1, i_sub = 1; i <= i2; i++, i_sub ++)
00496         for(j = j1, j_sub = 1; j <= j2; j++, j_sub ++)
00497             MATRIX_ELEM(A,i,j) = MATRIX_ELEM(A_sub,i_sub,j_sub) ;
00498 }

Here is the caller graph for this function:

void matrix_add ( Pmatrix  ,
Pmatrix  ,
Pmatrix   
)

input

denominators of b, c

ppcm of b,c

precondition

Definition at line 498 of file matrix.c.

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

Referenced by make_reindex(), and prepare_reindexing().

00501 {
00502     Value d1,d2;   /* denominators of b, c */
00503     Value lcm,t1,t2;     /* ppcm of b,c */
00504     int i,j;
00505 
00506     /* precondition */
00507     int n= MATRIX_NB_LINES(a);
00508     int m = MATRIX_NB_COLUMNS(a);
00509     assert(n>0 && m>0);
00510     assert(value_pos_p(MATRIX_DENOMINATOR(b)));
00511     assert(value_pos_p(MATRIX_DENOMINATOR(c)));
00512 
00513     d1 = MATRIX_DENOMINATOR(b);
00514     d2 = MATRIX_DENOMINATOR(c);
00515     if (value_eq(d1,d2)){
00516         for (i=1; i<=n; i++)
00517             for (j=1; j<=m; j++)
00518                 MATRIX_ELEM(a,i,j) = 
00519                     value_plus(MATRIX_ELEM(b,i,j),MATRIX_ELEM(c,i,j));
00520         MATRIX_DENOMINATOR(a) = d1;
00521     }
00522     else{
00523         lcm = ppcm(d1,d2);
00524         d1 = value_div(lcm,d1);
00525         d2 = value_div(lcm,d2);
00526         for (i=1; i<=n; i++)
00527             for (j=1; j<=m; j++)
00528                 t1 = value_mult(MATRIX_ELEM(b,i,j),d1),
00529                     t2 = value_mult(MATRIX_ELEM(c,i,j),d2),
00530                     MATRIX_ELEM(a,i,j) = value_plus(t1,t2);
00531         MATRIX_DENOMINATOR(a) = lcm;
00532     }
00533 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 255 of file matrix.c.

References i, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, and n.

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

00257 {
00258     int i;
00259     int n = MATRIX_NB_LINES(A);
00260     int m = MATRIX_NB_COLUMNS(A);
00261     for (i = 0 ;i<= n*m;i++)
00262         B->coefficients[i] = A->coefficients[i];
00263 }

Here is the caller graph for this function:

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 417 of file sub-matrix.c.

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

Referenced by matrix_hermite().

00421 {
00422     boolean trouve = FALSE;
00423     int j;
00424     Value min = VALUE_ZERO,val=VALUE_ZERO;
00425     int m = MATRIX_NB_COLUMNS(MAT);
00426     *lg_nnul = 0;
00427     *cl_nnul = 0;
00428 
00429     /* recherche de la premiere ligne non nulle de la 
00430        sous-matrice MAT(level+1 .. n,level+1 .. m)      */
00431 
00432     *lg_nnul= matrix_line_nnul(MAT,level);
00433 
00434     /* recherche du plus petit (en valeur absolue) element non nul de cette ligne */
00435     if (*lg_nnul) {
00436         for (j=1+level;j<=m && !trouve; j++) {
00437             min = MATRIX_ELEM(MAT,*lg_nnul,j);
00438             min = value_abs(min);
00439             if (value_notzero_p(min)) {
00440                 trouve = TRUE;
00441                 *cl_nnul=j;
00442             }
00443         }
00444         for (j=1+level;j<=m && value_gt(min,VALUE_ONE); j++) {
00445             val = MATRIX_ELEM(MAT,*lg_nnul,j);
00446             val = value_abs(val);
00447             if (value_notzero_p(val) && value_lt(val,min)) {
00448                 min = val;
00449                 *cl_nnul =j;
00450             }
00451         }
00452     }
00453 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 397 of file sub-matrix.c.

References i, MATRIX_ELEM, MATRIX_NB_LINES, and n.

Referenced by matrix_smith(), and smith_int().

00400 {
00401     int i;
00402     int i_min=0;
00403     int n = MATRIX_NB_LINES(MAT); 
00404     for(i = level+2; i <= n && (MATRIX_ELEM(MAT,i,level+1)==0); i++);
00405     if (i<n+1)
00406         i_min = i-1;
00407     return (i_min);
00408 }

Here is the caller graph for this function:

void matrix_determinant ( Pmatrix  ,
Value  [] 
)

determinant.c

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 89 of file matrix/inversion.c.

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

00092 {
00093     Value d, d1; 
00094     Value gcd, lcm;
00095     int i;
00096     int n = MATRIX_NB_LINES(s);
00097     /* tests des preconditions */
00098     assert(matrix_diagonal_p(s));
00099     assert(matrix_hermite_rank(s)==n);
00100     assert(value_pos_p(MATRIX_DENOMINATOR(s)));
00101 
00102     matrix_nulle(inv_s);
00103     /* calcul de la ppcm(s[1,1],s[2,2],...s[n,n]) */
00104     lcm = MATRIX_ELEM(s,1,1);
00105     for (i=2; i<=n; i++)
00106         lcm = ppcm(lcm,MATRIX_ELEM(s,i,i));
00107     
00108     d = MATRIX_DENOMINATOR(s);
00109     gcd = pgcd(lcm,d);
00110     d1 = value_div(d,gcd);
00111     for (i=1; i<=n; i++) {
00112         Value tmp = value_div(lcm,MATRIX_ELEM(s,i,i));
00113         MATRIX_ELEM(inv_s,i,i) = value_mult(d1,tmp);
00114     }
00115     MATRIX_DENOMINATOR(inv_s) = value_div(lcm,gcd);
00116 }

Here is the call graph for this function:

boolean matrix_diagonal_p ( Pmatrix  Z  ) 

boolean 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 355 of file matrix.c.

References FALSE, i, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, n, and TRUE.

Referenced by extract_lattice(), and matrix_diagonal_inversion().

00357 {
00358     int i,j;
00359     int n = MATRIX_NB_LINES(Z);
00360     int m = MATRIX_NB_COLUMNS(Z);
00361     for (i=1;i<=n;i++)
00362         for (j=1;j<=m;j++)
00363             if(i!=j && MATRIX_ELEM(Z,i,j)!=0)
00364                 return(FALSE);
00365     return(TRUE);
00366 }

Here is the caller graph for this function:

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 190 of file matrix/hermite.c.

References FALSE, i, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, n, and TRUE.

00192 {
00193     int i,j;
00194     boolean trouve_j = FALSE;
00195     int res=0;
00196     int n = MATRIX_NB_LINES(H);
00197     int m = MATRIX_NB_COLUMNS(H);
00198     for (j = 1; j<=m && !trouve_j;j++) {
00199         for (i=1; i<= n && MATRIX_ELEM(H,i,j) == 0; i++);
00200         if (i>n) {
00201             trouve_j = TRUE;
00202             res= j-1;
00203         }
00204     }
00205 
00206 
00207     if (!trouve_j && m>=1) res = m;
00208     return (res);
00209 
00210 }

boolean matrix_equality ( Pmatrix  A,
Pmatrix  B 
)

boolean 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

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

Definition at line 277 of file matrix.c.

References FALSE, i, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, n, and TRUE.

00279 {
00280     int i;  
00281     int n = MATRIX_NB_LINES(A);
00282     int m = MATRIX_NB_COLUMNS(A);
00283     for (i = 0 ;i<= n*m;i++)
00284         if(B->coefficients[i] != A->coefficients[i])
00285             return(FALSE);
00286     return(TRUE);
00287 }

void matrix_fprint ( FILE *  f,
Pmatrix  a 
)

matrix_io.c

matrix_io.c

void matrix_fprint(File * f, matrice a,n,m): print an (nxm) rational matrix Note: the output format is incompatible with matrix_fscan()

Definition at line 41 of file matrix_io.c.

References assert, fprint_Value(), fprintf(), loop1, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, matrix_pr_quot(), and n.

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

00045 {
00046     int loop1,loop2;
00047     int n =MATRIX_NB_LINES(a);
00048     int m = MATRIX_NB_COLUMNS(a);
00049     assert(MATRIX_DENOMINATOR(a)!=0);
00050 
00051     (void) fprintf(f,"\n\n");
00052 
00053     for(loop1=1; loop1<=n; loop1++) {
00054         for(loop2=1; loop2<=m; loop2++)
00055             matrix_pr_quot(f, 
00056                            MATRIX_ELEM(a,loop1,loop2), 
00057                            MATRIX_DENOMINATOR(a));
00058         (void) fprintf(f,"\n\n");
00059     }
00060     (void) fprintf(f," ......denominator = ");
00061     (void) fprint_Value(f, MATRIX_DENOMINATOR(a));
00062     (void) fprintf(f, "\n");
00063 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 6row 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 6column size

Definition at line 94 of file matrix_io.c.

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

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

00099 {
00100     int r;
00101     int c;
00102 
00103     /* number of read elements */
00104     int n_read;
00105 
00106     /* read dimensions */
00107     n_read = fscanf(f,"%d%d", n, m);
00108     assert(n_read==2);
00109     assert(1 <= *n && 1 <= *m);
00110 
00111     /* allocate a */
00112     *a = matrix_new(*n,*m); 
00113 
00114     /* read denominator */
00115     n_read = fscan_Value(f,&(MATRIX_DENOMINATOR(*a)));
00116     assert(n_read == 1);
00117     /* necessaires pour eviter les divisions par zero */
00118     assert(value_notzero_p(MATRIX_DENOMINATOR(*a)));
00119     /* pour "normaliser" un peu les representations */
00120     assert(value_pos_p(MATRIX_DENOMINATOR(*a)));
00121 
00122     for(r = 1; r <= *n; r++) 
00123         for(c = 1; c <= *m; c++) {
00124             n_read = fscan_Value(f, &MATRIX_ELEM(*a,r,c));
00125             assert(n_read == 1);
00126         }
00127 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 212 of file matrix/inversion.c.

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

Referenced by build_contraction_matrices(), and prepare_reindexing().

00215 {
00216     int n = MATRIX_NB_LINES(a);
00217     Pmatrix p = matrix_new(n,n);
00218     Pmatrix q = matrix_new(n,n);
00219     Pmatrix h = matrix_new(n,n);
00220     Pmatrix inv_h = matrix_new(n,n);
00221     Pmatrix temp = matrix_new(n,n);
00222     Value deno;
00223     Value det_p, det_q;                 /* ne utilise pas */
00224 
00225     /* test */
00226     assert(value_pos_p(MATRIX_DENOMINATOR(a)));
00227 
00228     deno = MATRIX_DENOMINATOR(a);
00229     MATRIX_DENOMINATOR(a) = VALUE_ONE;
00230     matrix_hermite(a,p,h,q,&det_p,&det_q);
00231     MATRIX_DENOMINATOR(a) = deno;
00232     if ( matrix_hermite_rank(h) == n){
00233         MATRIX_DENOMINATOR(h) = deno;
00234         matrix_triangular_inversion(h,inv_h,TRUE);
00235         matrix_multiply(q,inv_h,temp);
00236         matrix_multiply(temp,p,inv_a);
00237     }
00238     else{
00239         fprintf(stderr," L'inverse de la matrice a n'existe pas!\n");
00240         exit(1);
00241     }
00242 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

hermite.c

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 74 of file matrix/hermite.c.

References ALL, assert, FALSE, i, 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(), n, NULL, SUB_MATRIX_ELEM, TRUE, 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().

00081 {
00082     Pmatrix PN=NULL;
00083     Pmatrix QN=NULL;
00084     Pmatrix HN = NULL;
00085     int n,m;
00086     /* indice de la ligne et indice de la colonne correspondant
00087        au plus petit element de la sous-matrice traitee */
00088     int ind_n,ind_m;   
00089 
00090     /* niveau de la sous-matrice traitee */
00091     int level = 0;    
00092     
00093     Value ALL;/* le plus petit element sur la diagonale */
00094     Value x=VALUE_ZERO;  /* la quotient de la division par ALL */
00095     boolean stop = FALSE;
00096     int i;
00097     
00098     *det_p = *det_q = VALUE_ONE;
00099     /* if ((n>0) && (m>0) && MAT) */
00100     n = MATRIX_NB_LINES(MAT);
00101     m=MATRIX_NB_COLUMNS(MAT);
00102     assert(n >0 && m > 0);
00103     assert(value_one_p(MATRIX_DENOMINATOR(MAT)));
00104 
00105     HN = matrix_new(n, m);
00106     PN = matrix_new(n, n);
00107     QN = matrix_new(m, m);
00108    
00109     /* Initialisation des matrices */
00110 
00111     matrix_assign(MAT,H);
00112     matrix_identity(PN,0);
00113     matrix_identity(QN,0);
00114     matrix_identity(P,0);
00115     matrix_identity(Q,0);
00116     matrix_nulle(HN);
00117 
00118     while (!stop) {  
00119         /* tant qu'il reste des termes non nuls dans la partie 
00120            triangulaire superieure  de la matrice H,        
00121            on cherche le plus petit element de la sous-matrice     */
00122         matrix_coeff_nnul(H,&ind_n,&ind_m,level);
00123 
00124         if (ind_n == 0 && ind_m == 0)
00125             /* la sous-matrice restante est nulle, on a terminee */
00126             stop = TRUE; 
00127         else { 
00128             /* s'il existe un plus petit element non nul dans la partie
00129                triangulaire superieure de la sous-matrice,
00130                on amene cet element en haut sur la diagonale.
00131                si cet element est deja sur la diagonale, et que  tous les 
00132                termes de la ligne correspondante sont nuls,
00133                on effectue les calculs sur la sous-matrice de rang superieur*/
00134                
00135             if (ind_n > level + 1) {
00136                 matrix_swap_rows(H,level+1,ind_n);
00137                 matrix_swap_rows(PN,level+1,ind_n);
00138                 *det_p = value_uminus(*det_p);
00139             }
00140 
00141             if (ind_m > level+1) {
00142                 matrix_swap_columns(H,level+1,ind_m);
00143                 matrix_swap_columns(QN,level+1,ind_m);  
00144                 *det_q = value_uminus(*det_q);
00145             }
00146 
00147             if(matrix_line_el(H,level) != 0) {
00148                 ALL = SUB_MATRIX_ELEM(H,1,1,level);
00149                 for (i=level+2; i<=m; i++) {
00150                     x = value_div(MATRIX_ELEM(H,level+1,i),ALL);
00151                     matrix_subtraction_column(H,i,level+1,x);
00152                     matrix_subtraction_column(QN,i,level+1,x);
00153                 }
00154 
00155             }
00156             else level++;
00157         }
00158     }
00159 
00160     matrix_assign(PN,P);
00161     matrix_assign(QN,Q);
00162     matrix_free(HN);
00163     matrix_free(PN);
00164     matrix_free(QN);
00165 }

Here is the call graph for this function:

Here is the caller graph for this function:

int matrix_hermite_rank ( Pmatrix   ) 

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

Definition at line 170 of file matrix/hermite.c.

References i, MATRIX_ELEM, MATRIX_NB_LINES, and n.

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

00172 {
00173     int i;
00174     int r = 0;
00175     int n = MATRIX_NB_LINES(a);
00176     for(i=1; i<=n; i++, r++)
00177         if(MATRIX_ELEM(a, i, i) == 0) break;
00178 
00179     return r;
00180 }

Here is the caller graph for this function:

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 318 of file sub-matrix.c.

References i, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_LINES, n, 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().

00321 {
00322     int i,j;
00323     int n = MATRIX_NB_LINES(ID);
00324     for(i = level+1; i <= n; i++) {
00325         for(j = level+1; j <= n; j++)
00326             MATRIX_ELEM(ID,i,j) = VALUE_ZERO;
00327         MATRIX_ELEM(ID,i,i) = VALUE_ONE;
00328     }
00329 
00330     MATRIX_DENOMINATOR(ID) = VALUE_ONE;
00331 }

Here is the caller graph for this function:

boolean matrix_identity_p ( Pmatrix  ID,
int  level 
)

boolean 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 348 of file sub-matrix.c.

References FALSE, i, MATRIX_ELEM, MATRIX_NB_LINES, n, TRUE, value_notone_p, and value_notzero_p.

00351 {
00352     int i,j;
00353     int n = MATRIX_NB_LINES(ID);
00354     for(i = level+1; i <= n; i++) {
00355         for(j = level+1; j <= n; j++) {
00356             if(i==j) {
00357                 if(value_notone_p(MATRIX_ELEM(ID,i,i)))
00358                     return(FALSE);
00359             }
00360             else                        /* i!=j */
00361                 if(value_notzero_p(MATRIX_ELEM(ID,i,j)))
00362                     return(FALSE);
00363         }
00364     }
00365     return(TRUE);
00366 }

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 375 of file sub-matrix.c.

References MATRIX_ELEM, and MATRIX_NB_COLUMNS.

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

00378 {
00379     int j;
00380     int j_min = 0;
00381     int m = MATRIX_NB_COLUMNS(MAT);
00382     /* recherche du premier element non nul de la sous-ligne 
00383        MAT(level+1,level+2..m) */
00384     for(j = level+2; j<=m && (MATRIX_ELEM(MAT,1+level,j)==0) ; j++);
00385     if(j < m+1)
00386         j_min = j-1;
00387     return (j_min);
00388 }

Here is the caller graph for this function:

int matrix_line_nnul ( Pmatrix  MAT,
int  level 
)

sub-matrix.c

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 68 of file sub-matrix.c.

References FALSE, i, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, n, and TRUE.

Referenced by matrix_coeff_nnul().

00071 {
00072     int i,j;
00073     int I = 0;
00074     boolean trouve = FALSE;
00075     int n = MATRIX_NB_LINES(MAT);
00076     int m= MATRIX_NB_COLUMNS(MAT);
00077     /* recherche du premier element non nul de la sous-matrice */
00078     for (i = level+1; i<=n && !trouve ; i++) {
00079         for (j = level+1; j<= m && (MATRIX_ELEM(MAT,i,j) == 0); j++);
00080         if(j <= m) {
00081             /* on dumpe la colonne J... */
00082             trouve = TRUE;
00083             I = i;
00084         }
00085     }
00086     return (I);
00087 }

Here is the caller graph for this function:

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 matriceRGSUSED

Parameters:
level evel

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

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

Referenced by smith_int().

00256 {
00257     Value A11;
00258     int i;
00259     Value x;
00260     int n = MATRIX_NB_LINES(A);
00261     matrix_identity(P,0);
00262 
00263     A11 =SUB_MATRIX_ELEM(A,1,1,level);
00264     for (i=2+level; i<=n; i++) {
00265         x = MATRIX_ELEM(A,i,1+level);
00266         value_division(x,A11);
00267         MATRIX_ELEM(P,i,1+level) = value_uminus(x);
00268     }
00269 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 290 of file sub-matrix.c.

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

Referenced by smith_int().

00294 {
00295     Value A11;
00296     int j;
00297     Value x;
00298     int m= MATRIX_NB_COLUMNS(A);
00299     matrix_identity(Q,0);
00300     A11 =SUB_MATRIX_ELEM(A,1,1,level);
00301     for (j=2+level; j<=m; j++) {
00302         x = value_div(MATRIX_ELEM(A,1+level,j),A11);
00303         MATRIX_ELEM(Q,1+level,j) = value_uminus(x);
00304     }
00305 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 192 of file sub-matrix.c.

References FALSE, i, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, min, n, TRUE, value_abs, value_gt, value_lt, value_notzero_p, VALUE_ONE, and VALUE_ZERO.

Referenced by matrix_smith(), and smith_int().

00196 {
00197     int i,j;
00198     int vali= 0;
00199     int valj=0;
00200     Value min=VALUE_ZERO;
00201     Value val=VALUE_ZERO;
00202     boolean trouve = FALSE;
00203 
00204     int n = MATRIX_NB_LINES(MAT);
00205     int m= MATRIX_NB_COLUMNS(MAT);
00206     /*  initialisation du minimum  car recherche d'un minimum non nul*/
00207     for (i=1+level;i<=n && !trouve;i++)
00208         for(j = level+1; j <= m && !trouve; j++) {
00209             min = MATRIX_ELEM(MAT,i,j);
00210             min = value_abs(min);
00211             if(value_notzero_p(min)) {
00212                 trouve = TRUE;
00213                 vali = i;
00214                 valj = j;
00215             }
00216         }
00217 
00218     for (i=1+level;i<=n;i++)
00219         for (j=1+level;j<=m && value_gt(min,VALUE_ONE); j++) {
00220             val = MATRIX_ELEM(MAT,i,j);
00221             val = value_abs(val);
00222             if (value_notzero_p(val) && value_lt(val,min)) {
00223                 min = val;
00224                 vali= i;
00225                 valj =j;
00226             }
00227         }
00228     *i_min = vali;
00229     *j_min = valj;
00230 }

Here is the caller graph for this function:

void matrix_multiply ( Pmatrix  a,
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 supportedoutput

validate dimensions

simplified aliasing test

set denominator

use ordinary school book algorithm

Parameters:
b 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 supportedinput

Parameters:
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 supportedinput

Definition at line 77 of file matrix.c.

References assert, i, loop1, 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(), matrix_general_inversion(), matrix_unimodular_inversion(), prepare_reindexing(), region_sc_minimal(), sc_resol_smith(), smith_int(), and Tiling_buffer_allocation().

00081 {
00082     register Value va, vb;
00083     int loop1,loop2,loop3;
00084     Value i;
00085 
00086 
00087     /* validate dimensions */
00088     int p= MATRIX_NB_LINES(a);  
00089     int q = MATRIX_NB_COLUMNS(a);       
00090     int r= MATRIX_NB_COLUMNS(b);        
00091     assert(p > 0 && q > 0 && r > 0);
00092     /* simplified aliasing test */
00093     assert(c != a && c != b);
00094 
00095     /* set denominator */
00096     MATRIX_DENOMINATOR(c) = 
00097         value_mult(MATRIX_DENOMINATOR(a),MATRIX_DENOMINATOR(b));
00098 
00099     /* use ordinary school book algorithm */
00100     for(loop1=1; loop1<=p; loop1++)
00101         for(loop2=1; loop2<=r; loop2++) {
00102             i = VALUE_ZERO;
00103             for(loop3=1; loop3<=q; loop3++) 
00104             {
00105                 va = MATRIX_ELEM(a,loop1,loop3), 
00106                 vb = MATRIX_ELEM(b,loop3,loop2);
00107                 value_addto(i, value_mult(va, vb));
00108             }
00109             MATRIX_ELEM(c,loop1,loop2) = i;
00110         }
00111 }

Here is the caller graph for this function:

Pmatrix matrix_new ( int  n,
int  m 
)

alloc.c

Definition at line 37 of file matrix/alloc.c.

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

Referenced by call_rwt(), compute_delay_merged_nest(), compute_delay_tiled_nest(), extract_lattice(), fusion_buffer(), make_reindex(), 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(), xml_Connection(), xml_ConstOffset(), and xml_LoopOffset().

00039 { 
00040     Pmatrix a = (Pmatrix) malloc(sizeof(Smatrix));
00041     a->denominator = VALUE_ONE;
00042     a->number_of_lines = n;
00043     a->number_of_columns = m;
00044     a->coefficients = (Value *) malloc(sizeof(Value)*((n*m)+1));
00045     return (a);
00046 }

Here is the call graph for this function:

Here is the caller graph for this function:

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)!=0input

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 123 of file matrix.c.

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

Referenced by make_reindex(), and prepare_reindexing().

00125 {
00126     int loop1,loop2;
00127     Value       factor;
00128     int n = MATRIX_NB_LINES(a);
00129     int m = MATRIX_NB_COLUMNS(a);
00130     assert(MATRIX_DENOMINATOR(a) != 0);
00131 
00132     /* we must find the GCD of all elements of matrix */
00133     factor = MATRIX_DENOMINATOR(a);
00134 
00135     for(loop1=1; loop1<=n; loop1++)
00136         for(loop2=1; loop2<=m; loop2++) 
00137             factor = pgcd(factor,MATRIX_ELEM(a,loop1,loop2));
00138 
00139     /* factor out */
00140     if (value_notone_p(factor)) {
00141         for(loop1=1; loop1<=n; loop1++)
00142             for(loop2=1; loop2<=m; loop2++)
00143                 value_division(MATRIX_ELEM(a,loop1,loop2), factor);
00144         value_division(MATRIX_DENOMINATOR(a),factor);
00145     }
00146 
00147     /* ensure denominator is positive */
00148     /* FI: this code is useless because pgcd()always return a positive integer,
00149        even if a is the null matrix; its denominator CANNOT be 0 */
00150     assert(value_pos_p(MATRIX_DENOMINATOR(a)));
00151 
00152 /*
00153     if(MATRIX_DENOMINATOR(a) < 0) {
00154         MATRIX_DENOMINATOR(a) = MATRIX_DENOMINATOR(a)*-1;
00155         for(loop1=1; loop1<=n; loop1++)
00156             for(loop2=1; loop2<=m; loop2++)
00157                 MATRIX_ELEM(a,loop1,loop2) = 
00158                     -1 * MATRIX_ELEM(a,loop1,loop2);
00159     }*/
00160 }

Here is the caller graph for this function:

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

Parameters:
MAT AT

Definition at line 174 of file matrix.c.

References assert, i, MATRIX_DENOMINATOR, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, n, pgcd, value_division, value_gt, and VALUE_ONE.

Referenced by sc_resol_smith(), and smith_int().

00176 {
00177     int i;
00178     Value a;
00179     int n = MATRIX_NB_LINES(MAT);
00180     int m = MATRIX_NB_COLUMNS(MAT);
00181     assert( n>0 && m>0);
00182 
00183     a = MATRIX_DENOMINATOR(MAT);
00184     for (i = 1;(i<=n*m) && value_gt(a,VALUE_ONE);i++)
00185         a = pgcd(a,MAT->coefficients[i]);
00186 
00187     if (value_gt(a,VALUE_ONE)) {
00188         for (i = 0;i<=n*m;i++)
00189             value_division(MAT->coefficients[i],a);
00190     }
00191 }

Here is the caller graph for this function:

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

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 304 of file matrix.c.

References i, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, n, 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().

00306 {
00307     int i,j;
00308     int n = MATRIX_NB_LINES(Z);
00309     int m = MATRIX_NB_COLUMNS(Z);
00310     for (i=1;i<=n;i++)
00311         for (j=1;j<=m;j++)
00312             MATRIX_ELEM(Z,i,j)=VALUE_ZERO;
00313     MATRIX_DENOMINATOR(Z) = VALUE_ONE;
00314 }

Here is the caller graph for this function:

boolean matrix_nulle_p ( Pmatrix  Z  ) 

boolean 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

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 329 of file matrix.c.

References FALSE, i, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, n, and TRUE.

00331 {
00332     int i,j;
00333     int n = MATRIX_NB_LINES(Z);
00334     int m = MATRIX_NB_COLUMNS(Z);
00335     for (i=1;i<=n;i++)
00336         for (j=1;j<=m;j++)
00337             if(MATRIX_ELEM(Z,i,j)!=0)
00338                 return(FALSE);
00339     return(TRUE);
00340 }

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 111 of file sub-matrix.c.

References i, MATRIX_ELEM, MATRIX_NB_LINES, matrix_nulle(), n, and VALUE_ONE.

Referenced by smith_int().

00114 {
00115     int i,j;
00116     int n = MATRIX_NB_LINES(MAT);
00117     matrix_nulle(MAT);
00118     if (level > 0) {
00119         for (i=1;i<=level; i++)
00120             MATRIX_ELEM(MAT,i,i) = VALUE_ONE;
00121     }
00122 
00123     for (i=1+level,j=k; i<=n; i++,j++)
00124     {
00125         if (j == n+1) j = 1 + level;
00126         MATRIX_ELEM(MAT,i,j)=VALUE_ONE;
00127     }
00128 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 matriceRGSUSED

Parameters:
MAT AT
level evel

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

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

Referenced by smith_int().

00149 {
00150     int i,j;
00151     int m= MATRIX_NB_COLUMNS(MAT);
00152     matrix_nulle(MAT);
00153     if(level > 0) {
00154         for (i = 1; i <= level;i++)
00155             MATRIX_ELEM(MAT,i,i) = VALUE_ONE;
00156     }
00157 
00158     for(j=1,i=k-level; j <= m - level; j++,i++) {
00159         if(i == m-level+1)
00160             i = 1;
00161         SUB_MATRIX_ELEM(MAT,i,j,level) = VALUE_ONE;
00162     }
00163 }

Here is the call graph for this function:

Here is the caller graph for this function:

void matrix_pr_quot ( FILE *  ,
Value  ,
Value   
)

Referenced by matrix_fprint().

Here is the caller graph for this function:

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 71 of file matrix_io.c.

References matrix_fprint().

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

00073 {
00074     matrix_fprint(stdout,a);
00075 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

smith.c

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 64 of file matrix/smith.c.

References ALL, assert, FALSE, i, 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(), n, printf(), SUB_MATRIX_ELEM, TRUE, value_div, value_one_p, VALUE_ZERO, and x.

Referenced by sc_resol_smith().

00069 {
00070     int n_min,m_min;
00071     int level = 0;
00072     Value ALL;        /* le plus petit element sur la diagonale */
00073     Value x=VALUE_ZERO;          /* le rest de la division par ALL */
00074     int i;
00075     
00076     boolean stop = FALSE;
00077     boolean next = TRUE;
00078 
00079     /* precondition sur les parametres */
00080     int n = MATRIX_NB_LINES(MAT);
00081     int m = MATRIX_NB_COLUMNS(MAT);
00082     assert(m > 0 && n >0);
00083     matrix_assign(MAT,D);
00084     assert(value_one_p(MATRIX_DENOMINATOR(D)));
00085 
00086     matrix_identity(P,0);
00087     matrix_identity(Q,0);
00088  
00089     while (!stop) {
00090         matrix_min(D,&n_min,&m_min,level);
00091                 
00092         if ((n_min == 0) && (m_min == 0))
00093             stop = TRUE;
00094         else {
00095             /* le transformation n'est pas fini. */
00096             if (n_min > level +1) {
00097                 matrix_swap_rows(D,level+1,n_min);
00098                 matrix_swap_rows(P,level+1,n_min);
00099             }
00100 #ifdef TRACE
00101             (void) printf (" apres alignement du plus petit element a la premiere ligne \n");
00102             matrix_print(D);
00103 #endif
00104             if (m_min >1+level) {
00105                 matrix_swap_columns(D,level+1,m_min);
00106                 matrix_swap_columns(Q,level+1,m_min);
00107             }
00108 #ifdef TRACE
00109             (void) printf (" apres alignement du plus petit element a la premiere colonne\n");
00110             matrix_print(D);
00111 #endif
00112            
00113             ALL = SUB_MATRIX_ELEM(D,1,1,level);
00114             if (matrix_line_el(D,level) != 0) 
00115                 for (i=level+2; i<=m; i++) {
00116                     x = value_div(MATRIX_ELEM(D,level+1,i),ALL);
00117                     matrix_subtraction_column(D,i,level+1,x);
00118                     matrix_subtraction_column(Q,i,level+1,x);
00119                     next = FALSE;
00120                 }
00121             if (matrix_col_el(D,level) != 0) 
00122                 for(i=level+2;i<=n;i++) {
00123                     x = value_div(MATRIX_ELEM(D,i,level+1),ALL);
00124                     matrix_subtraction_line(D,i,level+1,x);
00125                     matrix_subtraction_line(P,i,level+1,x);
00126                     next = FALSE;
00127                 }
00128 #ifdef TRACE
00129                 (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);
00130                 matrix_print(D);
00131 #endif
00132             if (next) level++;
00133             next = TRUE;
00134         }
00135     }
00136 
00137 #ifdef TRACE
00138     (void) printf (" la  matrice D apres transformation est la suivante :");
00139     matrix_print(D);
00140 
00141     (void) printf (" la matrice P est \n");
00142     matrix_print(P);
00143 
00144     (void) printf (" la matrice Q est \n");
00145     matrix_print(Q);
00146 #endif
00147 }

Here is the call graph for this function:

Here is the caller graph for this function:

void matrix_sub_determinant ( Pmatrix  ,
int  ,
int  ,
Value  [] 
)
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 supportedinput

denominators of b, c

ppcm of b,c

precondition

Parameters:
b 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 supportedoutput

Definition at line 461 of file matrix.c.

References assert, i, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, n, 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().

00464 {
00465     Value d1,d2;   /* denominators of b, c */
00466     Value lcm;     /* ppcm of b,c */
00467     int i,j;
00468 
00469     /* precondition */
00470     int n= MATRIX_NB_LINES(a);
00471     int m = MATRIX_NB_COLUMNS(a);
00472     assert(n>0 && m>0);
00473     assert(value_pos_p(MATRIX_DENOMINATOR(b)));
00474     assert(value_pos_p(MATRIX_DENOMINATOR(c)));
00475 
00476     d1 = MATRIX_DENOMINATOR(b);
00477     d2 = MATRIX_DENOMINATOR(c);
00478     if (value_eq(d1,d2)){
00479         for (i=1; i<=n; i++)
00480             for (j=1; j<=m; j++)
00481                 MATRIX_ELEM(a,i,j) = 
00482                     value_minus(MATRIX_ELEM(b,i,j),MATRIX_ELEM(c,i,j));
00483         MATRIX_DENOMINATOR(a) = d1;
00484     }
00485     else{
00486         lcm = ppcm(d1,d2);
00487         d1 = value_div(lcm,d1);
00488         d2 = value_div(lcm,d2);
00489         for (i=1; i<=n; i++)
00490             for (j=1; j<=m; j++)
00491                 MATRIX_ELEM(a,i,j) = 
00492                     value_minus(value_mult(MATRIX_ELEM(b,i,j),d1),
00493                                 value_mult(MATRIX_ELEM(c,i,j),d2));
00494         MATRIX_DENOMINATOR(a) = lcm;
00495     }
00496 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 547 of file matrix.c.

References i, MATRIX_ELEM, MATRIX_NB_LINES, n, value_mult, and value_substract.

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

00551 {
00552     int i;
00553     int n = MATRIX_NB_LINES(MAT);
00554     for (i=1; i<=n; i++)
00555         value_substract(MATRIX_ELEM(MAT,i,c1),
00556                         value_mult(x,MATRIX_ELEM(MAT,i,c2)));
00557 }

Here is the caller graph for this function:

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 573 of file matrix.c.

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

Referenced by matrix_smith().

00577 {
00578     int i;
00579     int m = MATRIX_NB_COLUMNS(MAT);
00580     for (i=1; i<=m; i++)
00581         value_substract(MATRIX_ELEM(MAT,r1,i),
00582                         value_mult(x,MATRIX_ELEM(MAT,r2,i)));
00583 }

Here is the caller graph for this function:

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; column numbers

Parameters:
c1 Precondition: n > 0; m > 0; 0 < c1 <= m; 0 < c2 <= m; input and output matrix
c2 2

Definition at line 198 of file matrix.c.

References assert, loop1, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, and n.

Referenced by matrix_hermite(), and matrix_smith().

00201 {
00202     int loop1;
00203     Value       temp;
00204     int n = MATRIX_NB_LINES(a);
00205     int m = MATRIX_NB_COLUMNS(a);
00206     assert(n > 0 && m > 0);
00207     assert(0 < c1 && c1 <= m);
00208     assert(0 < c2 && c2 <= m);
00209 
00210     for(loop1=1; loop1<=n; loop1++) {
00211         temp = MATRIX_ELEM(a,loop1,c1);
00212         MATRIX_ELEM(a,loop1,c1) = MATRIX_ELEM(a,loop1,c2);
00213         MATRIX_ELEM(a,loop1,c2) = temp;
00214     }
00215 }

Here is the caller graph for this function:

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 <= nrow numbers

validation

Parameters:
r1 Precondition: n > 0; m > 0; 1 <= r1 <= n; 1 <= r2 <= ninput and output matrix
r2 2

Definition at line 222 of file matrix.c.

References assert, loop1, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, and n.

Referenced by matrix_hermite(), and matrix_smith().

00225 {
00226     int loop1;
00227     Value       temp;
00228     /* validation */
00229     int n = MATRIX_NB_LINES(a);
00230     int m = MATRIX_NB_COLUMNS(a);
00231     assert(n > 0);
00232     assert(m > 0);
00233     assert(0 < r1 && r1 <= n);
00234     assert(0 < r2 && r2 <= n);
00235 
00236     for(loop1=1; loop1<=m; loop1++) {
00237         temp = MATRIX_ELEM(a,r1,loop1);
00238         MATRIX_ELEM(a,r1,loop1) = MATRIX_ELEM(a,r2,loop1);
00239         MATRIX_ELEM(a,r2,loop1) = temp;
00240     }
00241 }

Here is the caller graph for this function:

void matrix_transpose ( Pmatrix  a,
Pmatrix  a_t 
)

matrix.c

matrix.c

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

verification step

copy from a to a_t

Parameters:
a_t _t

Definition at line 44 of file matrix.c.

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

Referenced by region_sc_minimal().

00047 {
00048     int loop1,loop2;
00049     /* verification step */
00050     int n = MATRIX_NB_LINES(a);
00051     int m = MATRIX_NB_COLUMNS(a);
00052     assert(n >= 0 && m >= 0);
00053 
00054     /* copy from a to a_t */
00055     MATRIX_DENOMINATOR(a_t) = MATRIX_DENOMINATOR(a);
00056     for(loop1=1; loop1<=n; loop1++)
00057         for(loop2=1; loop2<=m; loop2++) 
00058             MATRIX_ELEM(a_t,loop2,loop1) = MATRIX_ELEM(a,loop1,loop2);
00059 }

Here is the caller graph for this function:

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

void matrix_triangular_inversion(Pmatrix h, Pmatrix inv_h,boolean 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 boolean 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 133 of file matrix/inversion.c.

References assert, FALSE, i, MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_hermite_rank(), MATRIX_NB_LINES, matrix_nulle(), matrix_sub_determinant(), matrix_triangular_p(), n, pgcd, TRUE, 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().

00137 {
00138     Value deno,deno1;                    /* denominateur */
00139     Value determinant,sub_determinant;  /* determinant */
00140     Value gcd;
00141     int i,j;
00142     Value aij[2];
00143     
00144     /* tests des preconditions */
00145     int n = MATRIX_NB_LINES(h);
00146     assert(matrix_triangular_p(h,infer));
00147     assert(matrix_hermite_rank(h)==n);
00148     assert(value_pos_p(MATRIX_DENOMINATOR(h)));
00149 
00150     matrix_nulle(inv_h);
00151     deno = MATRIX_DENOMINATOR(h);
00152     deno1 = deno;
00153     MATRIX_DENOMINATOR(h) = VALUE_ONE;
00154     /* calcul du determinant de h */
00155     determinant = VALUE_ONE;
00156     for (i= 1; i<=n; i++)
00157         value_product(determinant, MATRIX_ELEM(h,i,i));
00158 
00159     /* calcul du denominateur de inv_h */
00160     gcd = pgcd(deno1,determinant);
00161     if (value_notone_p(gcd)){
00162         value_division(deno1,gcd);
00163         value_division(determinant,gcd);
00164     }
00165     if (value_neg_p(determinant)){
00166         value_oppose(deno1); 
00167         value_oppose(determinant);
00168     }
00169     MATRIX_DENOMINATOR(inv_h) = determinant;
00170     /* calcul des sub_determinants des Aii */
00171     for (i=1; i<=n; i++){
00172         sub_determinant = VALUE_ONE;
00173         for (j=1; j<=n; j++)
00174             if (j != i)
00175                 value_product(sub_determinant, MATRIX_ELEM(h,j,j));
00176         MATRIX_ELEM(inv_h,i,i) = value_mult(sub_determinant,deno1);
00177     }
00178     /* calcul des sub_determinants des Aij (i<j) */
00179     switch(infer) {
00180     case TRUE:
00181         for (i=1; i<=n; i++)
00182             for(j=i+1; j<=n;j++){
00183                 matrix_sub_determinant(h,i,j,aij);
00184                 assert(value_one_p(aij[0]));
00185                 MATRIX_ELEM(inv_h,j,i) = value_mult(aij[1],deno1);
00186             }
00187         break;
00188     case FALSE:
00189         for (i=1; i<=n; i++)
00190             for(j=1; j<i; j++){
00191                 matrix_sub_determinant(h,i,j,aij);
00192                 assert(value_one_p(aij[0]));
00193                 MATRIX_ELEM(inv_h,j,i) = value_mult(aij[1],deno1);
00194             }
00195         break;
00196    }
00197     MATRIX_DENOMINATOR(h) = deno;
00198 }

Here is the call graph for this function:

Here is the caller graph for this function:

boolean matrix_triangular_p ( Pmatrix  Z,
boolean  inferieure 
)

boolean matrix_triangular_p(Pmatrix Z, boolean 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 387 of file matrix.c.

References FALSE, i, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, n, and TRUE.

Referenced by matrix_triangular_inversion(), and matrix_triangular_unimodular_p().

00390 {
00391     int i,j;
00392     int n = MATRIX_NB_LINES(Z);
00393     int m = MATRIX_NB_COLUMNS(Z);
00394     for (i=1; i <= n; i++)
00395         if(inferieure) {
00396             for (j=i+1; j <= m; j++)
00397                 if(MATRIX_ELEM(Z,i,j)!=0)
00398                     return(FALSE);
00399         }
00400         else
00401             for (j=1; j <= i-1; j++)
00402                 if(MATRIX_ELEM(Z,i,j)!=0)
00403                     return(FALSE);
00404     return(TRUE);
00405 }

Here is the caller graph for this function:

boolean matrix_triangular_unimodular_p ( Pmatrix  Z,
boolean  inferieure 
)

boolean matrix_triangular_unimodular_p(Pmatrix Z, boolean 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 int n : la dimension de la martice caree

Parameters:
inferieure nferieure

Definition at line 427 of file matrix.c.

References FALSE, i, MATRIX_ELEM, MATRIX_NB_LINES, matrix_triangular_p(), n, TRUE, and value_notone_p.

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

00430 {
00431     boolean triangulaire;
00432     int i;  
00433     int n = MATRIX_NB_LINES(Z);
00434     triangulaire = matrix_triangular_p(Z,inferieure);
00435     if (triangulaire == FALSE)
00436         return(FALSE);
00437     else{
00438         for(i=1; i<=n; i++)
00439             if (value_notone_p(MATRIX_ELEM(Z,i,i)))
00440                 return(FALSE);
00441         return(TRUE);
00442     }
00443 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 593 of file matrix.c.

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

Referenced by extract_lattice().

00596 {
00597     int i,j;
00598 
00599     assert(MATRIX_NB_LINES(mA)>=MATRIX_NB_LINES(A) &&
00600            MATRIX_NB_COLUMNS(mA)>=MATRIX_NB_COLUMNS(A));
00601 
00602     for (i=1; i<=MATRIX_NB_LINES(A); i++)
00603         for (j=1; j<=MATRIX_NB_COLUMNS(A); j++)
00604             MATRIX_ELEM(mA, i, j) = value_uminus(MATRIX_ELEM(A, i, j));
00605 }

Here is the caller graph for this function:

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 : 1. calcul la forme hermite de la matrice u : PUQ = H_U (unimodulaire triangulaire); -1 -1 2. 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 257 of file matrix/inversion.c.

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

00261 {
00262     int n = MATRIX_NB_LINES(u);
00263     Pmatrix p = matrix_new(n,n);
00264     Pmatrix q = matrix_new(n,n);
00265     Pmatrix h_u = matrix_new(n,n);
00266     Pmatrix inv_h_u = matrix_new(n,n);
00267     Pmatrix temp = matrix_new(n,n);
00268     Value det_p,det_q;  /* ne utilise pas */
00269    
00270     /* test */
00271     assert(value_one_p(MATRIX_DENOMINATOR(u)));
00272 
00273     matrix_hermite(u,p,h_u,q,&det_p,&det_q);
00274     assert(matrix_triangular_unimodular_p(h_u,TRUE));
00275     matrix_unimodular_triangular_inversion(h_u,inv_h_u,TRUE);
00276     matrix_multiply(q,inv_h_u,temp);
00277     matrix_multiply(temp,p,inv_u);
00278 }

Here is the call graph for this function:

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

inversion.c

inversion.c

void matrix_unimodular_triangular_inversion(Pmatrix u ,Pmatrix inv_u, * boolean 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 boolean 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 49 of file matrix/inversion.c.

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

Referenced by extract_lattice(), and matrix_unimodular_inversion().

00053 {
00054     int i, j;
00055     Value x;
00056     int n = MATRIX_NB_LINES(u);
00057     /* test de l'unimodularite et de la trangularite de u */
00058     assert(matrix_triangular_unimodular_p(u,infer));
00059 
00060     matrix_identity(inv_u,0);
00061     if (infer){
00062         for (i=n; i>=1;i--)
00063             for (j=i-1; j>=1; j--){
00064                 x = MATRIX_ELEM(u,i,j);
00065                 if (value_notzero_p(x))
00066                     matrix_subtraction_column(inv_u,j,i,x); 
00067             }
00068     }
00069     else{
00070         for (i=1; i<=n; i++)
00071             for(j=i+1; j<=n; j++){
00072                 x = MATRIX_ELEM(u,i,j);
00073                 if (value_notzero_p(x))
00074                     matrix_subtraction_column(inv_u,j,i,x);
00075             }
00076     }
00077 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 465 of file sub-matrix.c.

References i, and MATRIX_ELEM.

Referenced by extract_lattice(), and region_sc_minimal().

00468 {
00469     int i, j, i_sub, j_sub;
00470 
00471     for(i = i1, i_sub = 1; i <= i2; i++, i_sub ++)
00472         for(j = j1, j_sub = 1; j <= j2; j++, j_sub ++)
00473             MATRIX_ELEM(A_sub,i_sub,j_sub) = MATRIX_ELEM(A,i,j);
00474     
00475 }

Here is the caller graph for this function:

Generated by  doxygen 1.6.2-20100208