PIPS
|
Go to the source code of this file.
Macros | |
#define | MATRICE_UNDEFINED ((matrice) NULL) |
#define | MATRICE_NULLE ((matrice) NULL) |
#define | matrice_new(n, m) ((matrice) malloc(sizeof(Value)*((n*m)+1))) |
Allocation et desallocation d'une matrice. More... | |
#define | matrice_free(m) (free((char *) (m))) |
#define | ACCESS(matrix, column, i, j) ((matrix)[(((j)-1)*(column))+(i)]) |
Macros d'acces aux elements d'une matrice. More... | |
#define | DENOMINATOR(matrix) ((matrix)[0]) |
int DENOMINATEUR(matrix): acces au denominateur global d'une matrice matrix La combinaison *(&()) est necessaire pour avoir des parentheses autour de matrix[0] et pour pouvoir simultanement utiliser cette macro comme lhs. More... | |
#define | matrice_triangulaire_inferieure_p(a, n, m) matrice_triangulaire_p(a,n,m,true) |
bool matrice_triangulaire_inferieure_p(matrice a, int n, int m): test de triangularite de la matrice a More... | |
#define | matrice_triangulaire_superieure_p(a, n, m) matrice_triangulaire_p(a,n,m,false) |
bool matrice_triangulaire_superieure_p(matrice a, int n, int m): test de triangularite de la matrice a More... | |
#define | ACC_ELEM(matrix, column, i, j, level) (matrix[((j)-1+(level))*(column) + (i) + (level)]) |
FI: Corinne, peux-tu expliquer la raison d'etre de cette macro? More... | |
#define | VALIDATION 0 |
FI: Corinne, pourrais-tu nous eclairer sur la signification de ces constantes? More... | |
#define | MATRIX 0 |
FI #define NULL 0. More... | |
Typedefs | |
typedef Value * | matrice |
Warning! Do not modify this file that is automatically generated! More... | |
Functions | |
void | matrice_determinant (matrice, int, Value[]) |
definition temporaire d'une vraie fonction pour dbx More... | |
void | matrice_sous_determinant (matrice, int, int, int, Value[]) |
void | matrice_hermite (Value *, int, int, Value *, Value *, Value *, Value *, Value *) |
hermite.c More... | |
int | matrice_hermite_rank (matrice, int, int) |
int | dim_H (matrice, int, int) |
Calcul de la dimension de la matrice de Hermite H. More... | |
void | matrice_unimodulaire_triangulaire_inversion (matrice, matrice, int, bool) |
inversion.c More... | |
void | matrice_diagonale_inversion (matrice, matrice, int) |
void matrice_diagonale_inversion(matrice s,matrice inv_s,int n) calcul de l'inversion du matrice en forme reduite smith. More... | |
void | matrice_triangulaire_inversion (matrice, matrice, int, bool) |
void matrice_triangulaire_inversion(matrice h, matrice inv_h, int n,bool infer) calcul de l'inversion du matrice en forme triangulaire. More... | |
void | matrice_general_inversion (matrice, matrice, int) |
void matrice_general_inversion(matrice a; matrice inv_a; int n) calcul de l'inversion du matrice general. More... | |
void | matrice_unimodulaire_inversion (matrice, matrice, int) |
void matrice_unimodulaire_inversion(matrice u, matrice inv_u, int n) calcul de l'inversion de la matrice unimodulaire. More... | |
void | matrice_transpose (matrice, matrice, int, int) |
matrice.c More... | |
void | matrice_multiply (matrice, matrice, matrice, int, int, int) |
void matrice_multiply(matrice a, matrice b, matrice c, int p, int q, int r): multiply rational matrix a by rational matrix b and store result in matrix c More... | |
void | matrice_normalize (matrice, int, int) |
void matrice_normalize(matrice a, int n, int m) More... | |
void | matrice_normalizec (matrice, int, int) |
void matrice_normalizec(matrice MAT, int n, int m): Normalisation des coefficients de la matrice MAT, i.e. More... | |
void | matrice_swap_columns (matrice, int, int, int, int) |
void matrice_swap_columns(matrice matrix, int n, int m, int c1, int c2): exchange columns c1,c2 of an (nxm) rational matrix More... | |
void | matrice_swap_rows (matrice, int, int, int, int) |
void matrice_swap_rows(matrice a, int n, int m, int r1, int r2): exchange rows r1 and r2 of an (nxm) rational matrix a More... | |
void | matrice_assign (matrice, matrice, int, int) |
void matrice_assign(matrice A, matrice B, int n, int m) Copie de la matrice A dans la matrice B More... | |
bool | matrice_egalite (matrice, matrice, int, int) |
bool matrice_egalite(matrice A, matrice B, int n, int m) 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 | matrice_nulle (matrice, int, int) |
void matrice_nulle(matrice Z, int n, int m): Initialisation de la matrice Z a la valeur matrice nulle More... | |
bool | matrice_nulle_p (matrice, int, int) |
bool matrice_nulle_p(matrice Z, int n, int m): test de nullite de la matrice Z More... | |
bool | matrice_diagonale_p (matrice, int, int) |
bool matrice_diagonale_p(matrice Z, int n, int m): test de nullite de la matrice Z More... | |
bool | matrice_triangulaire_p (matrice, int, int, bool) |
bool matrice_triangulaire_p(matrice Z, int n, int m, bool inferieure): test de triangularite de la matrice Z More... | |
bool | matrice_triangulaire_unimodulaire_p (matrice, int, bool) |
bool matrice_triangulaire_unimodulaire_p(matrice Z, int n, bool inferieure) test de la triangulaire et unimodulaire de la matrice Z. More... | |
void | matrice_substract (matrice, matrice, matrice, int, int) |
void matrice_substract(matrice a, matrice b, matrice c, int n, int m): substract rational matrix c from rational matrix b and store result in matrix a More... | |
void | matrice_soustraction_colonne (matrice, int, int, int, int, Value) |
void | matrice_soustraction_ligne (matrice, int, int, int, int, Value) |
void matrice_soustraction_ligne(matrice MAT,int n,int m,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 | matrice_fprint (FILE *, matrice, int, int) |
matrice_io.c More... | |
void | matrice_print (matrice, int, int) |
void matrice_print(matrice a, int n, int m): print an (nxm) rational matrix More... | |
void | matrice_fscan (FILE *, matrice *, int *, int *) |
void matrice_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 | matrice_smith (matrice, int, int, matrice, matrice, matrice) |
smith.c More... | |
int | mat_lig_nnul (matrice, int, int, int) |
sous-matrice.c More... | |
void | mat_perm_col (matrice, int, int, int, int) |
void | mat_perm_lig (matrice, int, int, int, int) |
void | mat_min (matrice, int, int, int *, int *, int) |
void mat_min(matrice MAT, int n, int m, 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 | mat_maj_col (matrice, int, int, matrice, int) |
void | mat_maj_lig (matrice, int, int, matrice, int) |
void mat_maj_lig(matrice A, int n, int m, 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 | matrice_identite (matrice, int, int) |
void matrice_identite(matrice ID, int n, int level) Construction d'une sous-matrice identite dans ID(level+1..n, level+1..n) More... | |
bool | matrice_identite_p (matrice, int, int) |
bool matrice_identite_p(matrice ID, int n, int level) test d'une sous-matrice dans ID(level+1..n, level+1..n) pour savoir si c'est une matrice identite. More... | |
int | mat_lig_el (matrice, int, int, int) |
int mat_lig_el(matrice MAT, int n, int m, 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 | mat_col_el (matrice, int, int, int) |
void | mat_coeff_nnul (matrice, int, int, int *, int *, int) |
void mat_coeff_nnul(matrice MAT, int n, int m, 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... | |
Macros d'acces aux elements d'une matrice.
int ACCESS(int * matrix, int column, int i, int j): acces a l'element (i,j) de la matrice matrix, dont la taille des colonnes, i.e. le nombre de lignes, est column.
int DENOMINATEUR(matrix): acces au denominateur global d'une matrice matrix La combinaison *(&()) est necessaire pour avoir des parentheses autour de matrix[0] et pour pouvoir simultanement utiliser cette macro comme lhs.
#define DENOMINATOR(matrix) *(&((matrix)[0]))
#define matrice_triangulaire_inferieure_p | ( | a, | |
n, | |||
m | |||
) | matrice_triangulaire_p(a,n,m,true) |
bool matrice_triangulaire_inferieure_p(matrice a, int n, int m): test de triangularite de la matrice a
#define matrice_triangulaire_superieure_p | ( | a, | |
n, | |||
m | |||
) | matrice_triangulaire_p(a,n,m,false) |
bool matrice_triangulaire_superieure_p(matrice a, int n, int m): test de triangularite de la matrice a
#define VALIDATION 0 |
Warning! Do not modify this file that is automatically generated!
Modify src/Libs/matrice/matrice-local.h instead, to add your own modifications. header file built by cproto matrice-local.h package matrice
Neil Butler, Corinne Ancourt, Francois Irigoin, Yi-qing Yang Les matrices sont des matrices pleines, a coefficients rationnels.
Les matrices sont representes par des tableaux d'entiers mono-dimensionnels dont l'element 0 represente le denominateur global. Elles sont stockees par colonne ("column-major"), comme en Fortran. Les indices commencent a 1, toujours comme en Fortran et non comme en C. Les deux dimensions sont implicites et doivent etre passees en parametre avec la matrice dans les appels de procedures.
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 matrice_multiply(), ne sont pas normalisees par le pgcd des coefficients et du denominateur pour des raisons d'efficacite. Mais les routines de test, comme matrice_identite_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 (ou level? FI->CA) 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()
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 197 of file hermite.c.
References ACCESS, and value_zero_p.
Referenced by prototype_dimension(), and sc_image_computation().
void mat_coeff_nnul(matrice MAT, int n, int m, 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
MAT | AT |
lg_nnul | g_nnul |
cl_nnul | l_nnul |
level | evel |
Definition at line 426 of file sous-matrice.c.
References ACCESS, level, mat_lig_nnul(), min, value_absolute, value_gt, value_lt, value_notzero_p, VALUE_ONE, and VALUE_ZERO.
Referenced by matrice_hermite().
int mat_lig_el(matrice MAT, int n, int m, 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)
MAT | AT |
level | evel |
Definition at line 381 of file sous-matrice.c.
References ACCESS, level, and value_zero_p.
Referenced by matrice_hermite(), and matrice_smith().
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...
MAT | AT |
level | evel |
Definition at line 65 of file sous-matrice.c.
References ACCESS, level, and value_zero_p.
Referenced by mat_coeff_nnul().
void mat_maj_lig(matrice A, int n, int m, 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
level | evel |
Definition at line 292 of file sous-matrice.c.
References ACC_ELEM, ACCESS, level, matrice_identite(), Q, value_division, value_uminus, and x.
void mat_min(matrice MAT, int n, int m, 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
MAT | AT |
i_min | _min |
j_min | _min |
level | evel |
Definition at line 193 of file sous-matrice.c.
References ACCESS, level, min, value_absolute, value_gt, value_lt, value_notzero_p, VALUE_ONE, and VALUE_ZERO.
Referenced by matrice_smith().
void matrice_assign(matrice A, matrice B, int n, int m) 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: mat_dup
Definition at line 264 of file matrice.c.
References B.
Referenced by matrice_hermite(), and matrice_smith().
definition temporaire d'une vraie fonction pour dbx
#define matrice_print(a,n,m) matrice_fprint(stdout,a,n,m) cproto-generated files determinant.c
void matrice_diagonale_inversion(matrice s,matrice inv_s,int n) 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])
inv_s | nv_s |
Definition at line 95 of file inversion.c.
References ACCESS, assert, DENOMINATOR, matrice_diagonale_p(), matrice_hermite_rank(), matrice_nulle(), pgcd_slow(), ppcm(), value_div, value_mult, and value_pos_p.
bool matrice_diagonale_p(matrice Z, int n, int m): 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 362 of file matrice.c.
References ACCESS, and value_notzero_p.
Referenced by matrice_diagonale_inversion().
bool matrice_egalite(matrice A, matrice B, int n, int m) 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 285 of file matrice.c.
Note: the output format is incompatible with matrice_fscan() row size
m | Note: the output format is incompatible with matrice_fscan() column size |
Definition at line 62 of file matrice_io.c.
References ACCESS, assert, DENOMINATOR, f(), fprint_Value(), fprintf(), loop1, pr_quot(), and value_notzero_p.
Referenced by average_probability_matrix(), hyperplane(), interactive_partitioning_matrix(), local_tile_constraints(), make_tile_constraints(), matrice_print(), parallel_tiling(), partial_broadcast_coefficients(), prototype_dimension(), sc_image_computation(), tile_hyperplane_constraints(), tile_membership(), tile_membership_constraints(), tiling_transformation(), transformer_equality_fix_point(), and unstructured_to_complexity().
void matrice_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
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 115 of file matrice_io.c.
References ACCESS, assert, DENOMINATOR, f(), fscan_Value(), matrice_new, value_notzero_p, and value_pos_p.
Referenced by unimodular().
void matrice_general_inversion(matrice a; matrice inv_a; int n) 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
inv_a | nv_a |
Definition at line 222 of file inversion.c.
References assert, DENOMINATOR, exit, matrice_hermite(), matrice_hermite_rank(), matrice_multiply(), matrice_new, matrice_triangulaire_inversion(), printf(), VALUE_ONE, and value_pos_p.
Referenced by base_G_h1_unnull(), broadcast_conditions(), local_tile_constraints(), make_tile_constraints(), parallel_tiling(), system_inversion_restrict(), tile_membership(), tiling_transformation(), and unimodular().
void matrice_hermite | ( | Value * | MAT, |
int | n, | ||
int | m, | ||
Value * | P, | ||
Value * | H, | ||
Value * | Q, | ||
Value * | det_p, | ||
Value * | det_q | ||
) |
hermite.c
hermite.c
void matrice_hermite(matrice MAT, int n, int m, matrice P, matrice H, matrice 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:
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 rest 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
MAT | AT |
det_p | et_p |
det_q | et_q |
Definition at line 78 of file hermite.c.
References ACC_ELEM, ACCESS, ALL, assert, DENOMINATOR, level, mat_coeff_nnul(), mat_lig_el(), matrice_assign(), matrice_free, matrice_identite(), matrice_new, matrice_nulle(), matrice_soustraction_colonne(), matrice_swap_columns(), matrice_swap_rows(), Q, value_division, VALUE_ONE, value_one_p, value_oppose, and x.
Referenced by broadcast_of_dataflow(), matrice_determinant(), matrice_general_inversion(), matrice_unimodulaire_inversion(), prototype_dimension(), sc_image_computation(), and vecteurs_libres_p().
void matrice_identite(matrice ID, int n, int level) Construction d'une sous-matrice identite 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
ID | D |
level | evel |
Definition at line 322 of file sous-matrice.c.
References ACCESS, DENOMINATOR, level, VALUE_ONE, and VALUE_ZERO.
Referenced by check_tiling_legality(), local_tile_constraints(), mat_maj_col(), mat_maj_lig(), matrice_hermite(), matrice_smith(), matrice_unimodulaire_triangulaire_inversion(), sc_image_computation(), tile_hyperplane_constraints(), tiling_transformation(), and unstructured_to_complexity().
bool matrice_identite_p(matrice ID, int n, int level) test d'une sous-matrice dans ID(level+1..n, level+1..n) pour savoir si c'est une matrice identite.
Le test n'est correct que si la matrice ID passee en argument est normalisee (cf. matrice_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
ID | D |
level | evel |
Definition at line 353 of file sous-matrice.c.
References ACCESS, level, value_notone_p, and value_notzero_p.
void matrice_multiply(matrice a, matrice b, matrice c, int p, int q, int r): 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 matrice_normalize()).
Precondition: p > 0; q > 0; r > 0; c != a; c != b; – aliasing between c and a or b – is not supported input
validate dimensions
simplified aliasing test
set denominator
use ordinary school book algorithm
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 matrice_normalize()). |
Precondition: p > 0; q > 0; r > 0; c != a; c != b; – aliasing between c and a or b – is not supported input
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 matrice_normalize()). |
Precondition: p > 0; q > 0; r > 0; c != a; c != b; – aliasing between c and a or b – is not supported input
p | 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 matrice_normalize()). |
Precondition: p > 0; q > 0; r > 0; c != a; c != b; – aliasing between c and a or b – is not supported output
q | 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 matrice_normalize()). |
Precondition: p > 0; q > 0; r > 0; c != a; c != b; – aliasing between c and a or b – is not supported input
r | 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 matrice_normalize()). |
Precondition: p > 0; q > 0; r > 0; c != a; c != b; – aliasing between c and a or b – is not supported input
Definition at line 82 of file matrice.c.
References ACCESS, assert, DENOMINATOR, loop1, value_addto, value_mult, and VALUE_ZERO.
Referenced by hyperplane(), matrice_general_inversion(), matrice_unimodulaire_inversion(), sc_image_computation(), and unimodular().
void matrice_normalize(matrice a, int n, int m)
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: DENOMINATOR(a)!=0 output
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
n | 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: DENOMINATOR(a)!=0 input |
m | 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: DENOMINATOR(a)!=0 input |
Definition at line 125 of file matrice.c.
References ACCESS, assert, DENOMINATOR, loop1, pgcd, value_division, value_notone_p, value_notzero_p, and value_pos_p.
Referenced by average_probability_matrix(), make_tile_constraints(), and tile_membership().
void matrice_normalizec(matrice MAT, int n, int m): 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
FI What an awful test! It should be an assert()
MAT | AT |
Definition at line 175 of file matrice.c.
References pgcd, value_division, value_gt, and VALUE_ONE.
void matrice_nulle(matrice Z, int n, int m): 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 311 of file matrice.c.
References ACCESS, DENOMINATOR, VALUE_ONE, and VALUE_ZERO.
Referenced by average_probability_matrix(), base_G_h1_unnull(), broadcast_conditions(), build_transfer_matrix(), contraintes_with_sym_cst_to_matrices(), loop_nest_to_tile(), loop_sc_to_matrices(), make_primal(), mat_perm_col(), mat_perm_lig(), matrice_diagonale_inversion(), matrice_hermite(), matrice_triangulaire_inversion(), partial_broadcast_coefficients(), pu_contraintes_to_matrices(), sc_image_computation(), sc_to_matrices(), sys_matrice_index(), and system_inversion_restrict().
bool matrice_nulle_p(matrice Z, int n, int m): 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 336 of file matrice.c.
References ACCESS, and value_notzero_p.
void matrice_print(matrice a, int n, int m): print an (nxm) rational matrix
Note: the output format is incompatible with matrice_fscan() this should be implemented as a macro, but it's a function for dbx's sake row size
m | Note: the output format is incompatible with matrice_fscan() this should be implemented as a macro, but it's a function for dbx's sake column size |
Definition at line 90 of file matrice_io.c.
References matrice_fprint().
Referenced by matrice_smith().
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.
MAT | AT |
Definition at line 68 of file smith.c.
References ACC_ELEM, ACCESS, ALL, assert, D, DENOMINATOR, level, mat_col_el(), mat_lig_el(), mat_min(), matrice_assign(), matrice_identite(), matrice_print(), matrice_soustraction_colonne(), matrice_soustraction_ligne(), matrice_swap_columns(), matrice_swap_rows(), printf(), Q, value_division, value_one_p, and x.
Referenced by transformer_equality_fix_point().
void matrice_soustraction_ligne(matrice MAT,int n,int m,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 :
MAT | AT |
r1 | 1 |
r2 | 2 |
Definition at line 554 of file matrice.c.
References ACCESS, value_product, value_substract, and x.
Referenced by matrice_smith().
void matrice_substract(matrice a, matrice b, matrice c, int n, int m): 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 matrice_normalize()).
Precondition: n > 0; m > 0; Note: aliasing between a and b or c is supported input
denominators of b, c
ppcm of b,c
precondition
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 matrice_normalize()). |
Precondition: n > 0; m > 0; Note: aliasing between a and b or c is supported output
n | 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 matrice_normalize()). |
Precondition: n > 0; m > 0; Note: aliasing between a and b or c is supported input
Definition at line 468 of file matrice.c.
References ACCESS, assert, DENOMINATOR, ppcm(), value_div, value_minus, value_pos_p, and value_product.
Referenced by unstructured_to_complexity().
void matrice_swap_columns(matrice matrix, int n, int m, 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
validation step
matrix | atrix |
n | Precondition: n > 0; m > 0; 0 < c1 <= m; 0 < c2 <= m;input and output matrix |
m | Precondition: n > 0; m > 0; 0 < c1 <= m; 0 < c2 <= m;number of rows |
c1 | Precondition: n > 0; m > 0; 0 < c1 <= m; 0 < c2 <= m;number of columns |
c2 | 2 |
Definition at line 200 of file matrice.c.
References ACCESS, assert, and loop1.
Referenced by matrice_hermite(), and matrice_smith().
void matrice_swap_rows(matrice a, int n, int m, 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 row numbers
validation
n | Precondition: n > 0; m > 0; 1 <= r1 <= n; 1 <= r2 <= n input and output matrix |
m | Precondition: n > 0; m > 0; 1 <= r1 <= n; 1 <= r2 <= n number of columns |
r1 | Precondition: n > 0; m > 0; 1 <= r1 <= n; 1 <= r2 <= n number of rows |
r2 | 2 |
Definition at line 230 of file matrice.c.
References ACCESS, assert, and loop1.
Referenced by matrice_hermite(), matrice_smith(), and scanning_base_hyperplane().
void matrice_transpose(matrice a, matrice a_t, int n, int m): 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
a_t | _t |
Definition at line 48 of file matrice.c.
References ACCESS, assert, DENOMINATOR, and loop1.
Referenced by base_G_h1_unnull(), broadcast_conditions(), make_primal(), partial_broadcast_coefficients(), and system_inversion_restrict().
void matrice_triangulaire_inversion(matrice h, matrice inv_h, int n,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 sous_determinants des Aii
calcul des sous_determinants des Aij (i<j)
inv_h | nv_h |
infer | nfer |
Definition at line 140 of file inversion.c.
References ACCESS, assert, DENOMINATOR, matrice_hermite_rank(), matrice_nulle(), matrice_sous_determinant(), matrice_triangulaire_p(), pgcd_slow(), value_division, value_mult, value_neg_p, value_notone_p, VALUE_ONE, value_oppose, value_pos_p, and value_product.
Referenced by matrice_general_inversion().
bool matrice_triangulaire_p(matrice Z, int n, int m, 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
inferieure | nferieure |
Definition at line 394 of file matrice.c.
References ACCESS, and value_notzero_p.
Referenced by matrice_triangulaire_inversion(), and matrice_triangulaire_unimodulaire_p().
bool matrice_triangulaire_unimodulaire_p(matrice Z, int n, 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 int n : la dimension de la martice caree
inferieure | nferieure |
Definition at line 434 of file matrice.c.
References ACCESS, matrice_triangulaire_p(), and value_notone_p.
Referenced by matrice_unimodulaire_inversion(), and matrice_unimodulaire_triangulaire_inversion().
void matrice_unimodulaire_inversion(matrice u, matrice inv_u, int n) calcul de l'inversion de la matrice unimodulaire.
algorithme :
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
inv_u | nv_u |
Definition at line 267 of file inversion.c.
References assert, DENOMINATOR, matrice_hermite(), matrice_multiply(), matrice_new, matrice_triangulaire_unimodulaire_p(), matrice_unimodulaire_triangulaire_inversion(), and value_one_p.
inversion.c
inversion.c
void matrice_unimodulaire_triangulaire_inversion(matrice u ,matrice inv_u, int n, * 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 :
matrice 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
inv_u | nv_u |
infer | nfer |
Definition at line 54 of file inversion.c.
References ACCESS, assert, matrice_identite(), matrice_soustraction_colonne(), matrice_triangulaire_unimodulaire_p(), value_notzero_p, and x.
Referenced by matrice_unimodulaire_inversion().