PIPS
|
Go to the source code of this file.
Data Structures | |
struct | Pmatrix |
package matrice More... | |
Macros | |
#define | MATRIX_UNDEFINED ((Pmatrix) NULL) |
#define | matrix_free(m) (free(m), (m)=(Pmatrix) NULL) |
Allocation et desallocation d'une matrice. More... | |
#define | MATRIX_ELEM(matrix, i, j) ((matrix)->coefficients[(((j)-1)*((matrix)->number_of_lines))+((i)-1)]) |
Macros d'acces aux elements d'une matrice. More... | |
#define | MATRIX_DENOMINATOR(matrix) ((matrix)->denominator) |
int MATRIX_DENONIMATOR(matrix): acces au denominateur global d'une matrice matrix More... | |
#define | MATRIX_NB_LINES(matrix) ((matrix)->number_of_lines) |
#define | MATRIX_NB_COLUMNS(matrix) ((matrix)->number_of_columns) |
#define | matrix_triangular_inferieure_p(a) matrix_triangular_p(a, true) |
bool matrix_triangular_inferieure_p(matrice a): test de triangularite de la matrice a More... | |
#define | matrix_triangular_superieure_p(a) matrix_triangular_p(a, false) |
bool matrix_triangular_superieure_p(matrice a, int n, int m): test de triangularite de la matrice a More... | |
#define | SUB_MATRIX_ELEM(matrix, i, j, level) |
MATRIX_RIGHT_INF_ELEM Permet d'acceder des sous-matrices dont le coin infe'rieur droit (i.e. More... | |
Typedefs | |
typedef struct Pmatrix | Smatrix |
Functions | |
Pmatrix | matrix_new (int, int) |
cproto-generated files More... | |
void | matrix_rm (Pmatrix) |
void | matrix_determinant (Pmatrix, Value[]) |
determinant.c More... | |
void | matrix_sub_determinant (Pmatrix, int, int, Value[]) |
void | matrix_hermite (Pmatrix, Pmatrix, Pmatrix, Pmatrix, Value *, Value *) |
hermite.c More... | |
int | matrix_hermite_rank (Pmatrix) |
int matrix_hermite_rank(Pmatrix a): rang d'une matrice en forme de hermite More... | |
int | matrix_dim_hermite (Pmatrix) |
Calcul de la dimension de la matrice de Hermite H. More... | |
void | matrix_unimodular_triangular_inversion (Pmatrix, Pmatrix, bool) |
inversion.c More... | |
void | matrix_diagonal_inversion (Pmatrix, Pmatrix) |
void matrix_diagonal_inversion(Pmatrix s,Pmatrix inv_s) calcul de l'inversion du matrice en forme reduite smith. More... | |
void | matrix_triangular_inversion (Pmatrix, Pmatrix, bool) |
void matrix_triangular_inversion(Pmatrix h, Pmatrix inv_h,bool infer) calcul de l'inversion du matrice en forme triangulaire. More... | |
void | matrix_general_inversion (Pmatrix, Pmatrix) |
void matrix_general_inversion(Pmatrix a; Pmatrix inv_a) calcul de l'inversion du matrice general. More... | |
void | matrix_unimodular_inversion (Pmatrix, Pmatrix) |
void matrix_unimodular_inversion(Pmatrix u, Pmatrix inv_u) calcul de l'inversion de la matrice unimodulaire. More... | |
Value * | matrix_elem_ref (Pmatrix, int, int) |
matrix.c More... | |
Value | matrix_elem (Pmatrix, int, int) |
void | matrix_transpose (const Pmatrix, Pmatrix) |
void matrix_transpose(Pmatrix a, Pmatrix a_t): transpose an (nxm) rational matrix a into a (mxn) rational matrix a_t More... | |
void | matrix_multiply (const Pmatrix, const Pmatrix, Pmatrix) |
void matrix_multiply(Pmatrix a, Pmatrix b, Pmatrix c): multiply rational matrix a by rational matrix b and store result in matrix c More... | |
void | matrix_normalize (Pmatrix) |
void matrix_normalize(Pmatrix a) More... | |
void | matrix_normalizec (Pmatrix) |
void matrix_normalizec(Pmatrix MAT): Normalisation des coefficients de la matrice MAT, i.e. More... | |
void | matrix_swap_columns (Pmatrix, int, int) |
void matrix_swap_columns(Pmatrix a, int c1, int c2): exchange columns c1,c2 of an (nxm) rational matrix More... | |
void | matrix_swap_rows (Pmatrix, int, int) |
void matrix_swap_rows(Pmatrix a, int r1, int r2): exchange rows r1 and r2 of an (nxm) rational matrix a More... | |
void | matrix_assign (Pmatrix, Pmatrix) |
void matrix_assign(Pmatrix A, Pmatrix B) Copie de la matrice A dans la matrice B More... | |
bool | matrix_equality (Pmatrix, Pmatrix) |
bool matrix_equality(Pmatrix A, Pmatrix B) test de l'egalite de deux matrices A et B; elles doivent avoir ete normalisees au prealable pour que le test soit mathematiquement exact More... | |
void | matrix_nulle (Pmatrix) |
void matrix_nulle(Pmatrix Z): Initialisation de la matrice Z a la valeur matrice nulle More... | |
bool | matrix_nulle_p (Pmatrix) |
bool matrix_nulle_p(Pmatrix Z): test de nullite de la matrice Z More... | |
bool | matrix_diagonal_p (Pmatrix) |
bool matrix_diagonal_p(Pmatrix Z): test de nullite de la matrice Z More... | |
bool | matrix_triangular_p (Pmatrix, bool) |
bool matrix_triangular_p(Pmatrix Z, bool inferieure): test de triangularite de la matrice Z More... | |
bool | matrix_triangular_unimodular_p (Pmatrix, bool) |
bool matrix_triangular_unimodular_p(Pmatrix Z, bool inferieure) test de la triangulaire et unimodulaire de la matrice Z. More... | |
void | matrix_substract (Pmatrix, Pmatrix, Pmatrix) |
void matrix_substract(Pmatrix a, Pmatrix b, Pmatrix c): substract rational matrix c from rational matrix b and store result in matrix a More... | |
void | matrix_add (Pmatrix, Pmatrix, Pmatrix) |
a = b + c More... | |
void | matrix_subtraction_column (Pmatrix, int, int, Value) |
void matrix_subtraction_column(Pmatrix MAT,int c1,int c2,int x): Soustrait x fois la colonne c2 de la colonne c1 Precondition: n > 0; m > 0; 0 < c1, c2 < m; Effet: c1[0..n-1] = c1[0..n-1] - x*c2[0..n-1]. More... | |
void | matrix_subtraction_line (Pmatrix, int, int, Value) |
void matrix_subtraction_line(Pmatrix MAT,int r1,int r2,int x): Soustrait x fois la ligne r2 de la ligne r1 Precondition: n > 0; m > 0; 0 < r1, r2 < n; Effet: r1[0..m-1] = r1[0..m-1] - x*r2[0..m-1] More... | |
void | matrix_uminus (Pmatrix, Pmatrix) |
void matrix_uminus(A, mA) More... | |
void | matrix_fprint (FILE *, Pmatrix) |
matrix_io.c More... | |
void | matrix_print (Pmatrix) |
void matrix_print(matrice a): print an (nxm) rational matrix More... | |
void | matrix_fscan (FILE *, Pmatrix *, int *, int *) |
void matrix_fscan(FILE * f, matrice * a, int * n, int * m): read an (nxm) rational matrix in an ASCII file accessible via file descriptor f; a is allocated as a function of its number of columns and rows, n and m. More... | |
void | matrix_pr_quot (FILE *, Value, Value) |
void | matrix_smith (Pmatrix, Pmatrix, Pmatrix, Pmatrix) |
smith.c More... | |
int | matrices_to_1D_lattice (Pmatrix, Pmatrix, int, int, int, Value *, Value *) |
Under the assumption A x = B, A[n,m] and B[n], compute the 1-D lattice for x_i of x[m] as. More... | |
int | matrix_line_nnul (Pmatrix, int) |
sub-matrix.c More... | |
void | matrix_perm_col (Pmatrix, int, int) |
void matrix_perm_col(Pmatrix MAT, int k, int level): Calcul de la matrice de permutation permettant d'amener la k-ieme ligne de la matrice MAT(1..n,1..m) a la ligne (level + 1). More... | |
void | matrix_perm_line (Pmatrix, int, int) |
void matrix_perm_line(Pmatrix MAT, int k, int level): Calcul de la matrice de permutation permettant d'amener la k-ieme colonne de la sous-matrice MAT(1..n,1..m) a la colonne 'level + 1' (premiere colonne de la sous matrice MAT(level+1 ..n,level+1 ..m)). More... | |
void | matrix_min (Pmatrix, int *, int *, int) |
void matrix_min(Pmatrix MAT, int * i_min, int * j_min, int level): Recherche des coordonnees (*i_min, *j_min) de l'element de la sous-matrice MAT(level+1 ..n, level+1 ..m) dont la valeur absolue est la plus petite et non nulle. More... | |
void | matrix_maj_col (Pmatrix, Pmatrix, int) |
void matrix_maj_col(Pmatrix A, matrice P, int level): Calcul de la matrice permettant de remplacer chaque terme de la premiere ligne de la sous-matrice A(level+1 ..n, level+1 ..m) autre que le premier terme A11=A(level+1,level+1) par le reste de sa division entiere par A11 More... | |
void | matrix_maj_line (Pmatrix, Pmatrix, int) |
void matrix_maj_line(Pmatrix A, matrice Q, int level): Calcul de la matrice permettant de remplacer chaque terme de la premiere ligne autre que le premier terme A11=A(level+1,level+1) par le reste de sa division entiere par A11 More... | |
void | matrix_identity (Pmatrix, int) |
void matrix_identity(Pmatrix ID, int level) Construction d'une sous-matrice identity dans ID(level+1..n, level+1..n) More... | |
bool | matrix_identity_p (Pmatrix, int) |
bool matrix_identity_p(Pmatrix ID, int level) test d'une sous-matrice dans ID(level+1..n, level+1..n) pour savoir si c'est une matrice identity. More... | |
int | matrix_line_el (Pmatrix, int) |
int matrix_line_el(Pmatrix MAT, int level) renvoie le numero de colonne absolu du premier element non nul de la sous-ligne MAT(level+1,level+2..m); renvoie 0 si la sous-ligne est vide. More... | |
int | matrix_col_el (Pmatrix, int) |
int matrix_col_el(Pmatrix MAT, int level) renvoie le numero de ligne absolu du premier element non nul de la sous-colonne MAT(level+2..n,level+1); renvoie 0 si la sous-colonne est vide. More... | |
void | matrix_coeff_nnul (Pmatrix, int *, int *, int) |
void matrix_coeff_nnul(Pmatrix MAT, int * lg_nnul, int * cl_nnul, int level) renvoie les coordonnees du plus petit element non-nul de la premiere sous-ligne non nulle 'lg_nnul' de la sous-matrice MAT(level+1..n, level+1..m) More... | |
void | ordinary_sub_matrix (Pmatrix, Pmatrix, int, int, int, int) |
void ordinary_sub_matrix(Pmatrix A, A_sub, int i1, i2, j1, j2) input : a initialized matrix A, an uninitialized matrix A_sub, which dimensions are i2-i1+1 and j2-j1+1. More... | |
void | insert_sub_matrix (Pmatrix, Pmatrix, int, int, int, int) |
void insert_sub_matrix(A, A_sub, i1, i2, j1, j2) input: matrix A and smaller A_sub output: nothing modifies: A_sub is inserted in A at the specified position comment: A must be pre-allocated More... | |
#define MATRIX_ELEM | ( | matrix, | |
i, | |||
j | |||
) | ((matrix)->coefficients[(((j)-1)*((matrix)->number_of_lines))+((i)-1)]) |
Macros d'acces aux elements d'une matrice.
int MATRIX_ELEM(int * matrix, int i, int j): acces a l'element (i,j) de la matrice matrix.
#define matrix_triangular_inferieure_p | ( | a | ) | matrix_triangular_p(a, true) |
bool matrix_triangular_inferieure_p(matrice a): test de triangularite de la matrice a
#define matrix_triangular_superieure_p | ( | a | ) | matrix_triangular_p(a, false) |
bool matrix_triangular_superieure_p(matrice a, int n, int m): test de triangularite de la matrice a
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
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
A_sub | _sub |
i1 | 1 |
i2 | 2 |
j1 | 1 |
j2 | 2 |
Definition at line 487 of file sub-matrix.c.
References assert, MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.
Referenced by extract_lattice().
int matrices_to_1D_lattice | ( | Pmatrix | A, |
Pmatrix | B, | ||
int | n, | ||
int | m, | ||
int | i, | ||
Value * | gcd_p, | ||
Value * | c_p | ||
) |
Under the assumption A x = B, A[n,m] and B[n], compute the 1-D lattice for x_i of x[m] as.
x_i = gcd_i lambda + c_i
derived from the parametric solution of the system :
x_i = sum_{k<j<=m} q_{i,j} lambda_j + sum_{1<=j,=k} q_{i,j} y_c_{j}
where k is the rank of matrix A (0<=k<=n, k<=m), lambda_j are the free variables and y_c is the solution of the equations. This leads to:
gcd_i = sum_{k<j<=m} q_{i,j} and c_i = sum_{1<=j,=k} q_{i,j} y_c_{j}
when the system has a least one solution.
To compute Q and y_c, We use D[n,m], the Smith form of A, with D = P A Q and P[n,n] and Q[m,m] unimodular
inv(P) D inv(Q) x = b
inv(P) D y = b => D y = P b => some components of y[m] are constants, y_c[m]
y_c = D'{-1} P b, where D'[min(n,m),min(n,m)] is the top left submatrix of D[n,m]
y = inv(Q) x => x = Q (y_c[1..k],y[k+1..m])
where (a,b) represents s the concatenation of vectors a and b, and k<=min(n,m) the .
c_i = sum_j Q_{i,j} y_c_{j}
gcd = gcd_{j s.t. yc_j = 0} Q_{i,j}
Return false if the system Ax=b has no solution
This implements a partial parametric resolution of A x = B. It might be better from an engineering viewpoint to solve the system fully and then to exploit the equation for x_i.
gcd_p | cd_p |
c_p | _p |
Definition at line 195 of file smith.c.
References B, D, DIVIDE, free(), MATRIX_ELEM, matrix_multiply(), matrix_new(), matrix_smith(), modulo, pgcd, Q, value_mult, VALUE_ONE, VALUE_ZERO, and value_zero_p.
Referenced by transformer_to_1D_lattice().
a = b + c
precondition
Definition at line 471 of file matrix.c.
References assert, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, ppcm(), value_div, value_eq, value_mult, value_plus, and value_pos_p.
Referenced by make_reindex(), and prepare_reindexing().
void matrix_assign(Pmatrix A, Pmatrix B) Copie de la matrice A dans la matrice B
Les parametres de la fonction :
int A[] : matrice !int B[] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice
Ancien nom: matrix_dup
Definition at line 259 of file matrix.c.
References B, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.
Referenced by matrix_hermite(), matrix_smith(), sc_resol_smith(), and smith_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)
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 421 of file sub-matrix.c.
References level, MATRIX_ELEM, matrix_line_nnul(), MATRIX_NB_COLUMNS, min, value_abs, value_gt, value_lt, value_notzero_p, VALUE_ONE, and VALUE_ZERO.
Referenced by matrix_hermite().
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
MAT | AT |
level | evel |
Definition at line 401 of file sub-matrix.c.
References level, MATRIX_ELEM, and MATRIX_NB_LINES.
Referenced by matrix_smith(), and smith_int().
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])
inv_s | nv_s |
Definition at line 93 of file inversion.c.
References assert, MATRIX_DENOMINATOR, matrix_diagonal_p(), MATRIX_ELEM, matrix_hermite_rank(), MATRIX_NB_LINES, matrix_nulle(), pgcd, ppcm(), value_div, value_mult, and value_pos_p.
bool matrix_diagonal_p(Pmatrix Z): test de nullite de la matrice Z
QQ i dans [1..n] QQ j dans [1..n] Z(i,j) == 0 && i != j || i == j
Les parametres de la fonction :
int Z[] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice
Definition at line 336 of file matrix.c.
References MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.
Referenced by extract_lattice(), and matrix_diagonal_inversion().
Calcul de la dimension de la matrice de Hermite H.
La matrice de Hermite est une matrice tres particuliere, pour laquelle il est tres facile de calculer sa dimension. Elle est egale au nombre de colonnes non nulles de la matrice.
Definition at line 194 of file hermite.c.
References MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.
bool matrix_equality(Pmatrix A, Pmatrix B) test de l'egalite de deux matrices A et B; elles doivent avoir ete normalisees au prealable pour que le test soit mathematiquement exact
Definition at line 273 of file matrix.c.
References B, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.
void matrix_fprint | ( | FILE * | f, |
Pmatrix | a | ||
) |
void matrix_fprint(File * f, matrix a): print a rational matrix
Note: the output format is compatible with matrix_fscan()
Definition at line 44 of file matrix_io.c.
References assert, f(), fprint_Value(), fprintf(), MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, and VALUE_ZERO.
Referenced by main(), make_reindex(), matrix_print(), and prepare_reindexing().
void matrix_fscan(FILE * f, matrice * a, int * n, int * m): read an (nxm) rational matrix in an ASCII file accessible via file descriptor f; a is allocated as a function of its number of columns and rows, n and m.
Format:
n m denominator a[1,1] a[1,2] ... a[1,m] a[2,1] ... a[2,m] ... a[n,m]
After the two dimensions and the global denominator, the matrix as usually displayed, line by line. Line feed can be used anywhere. Example for a (2x3) integer matrix: 2 3 1 1 2 3 4 5 6 row size
number of read elements
read dimensions
allocate a
read denominator
necessaires pour eviter les divisions par zero
pour "normaliser" un peu les representations
m | Format: |
n m denominator a[1,1] a[1,2] ... a[1,m] a[2,1] ... a[2,m] ... a[n,m]
After the two dimensions and the global denominator, the matrix as usually displayed, line by line. Line feed can be used anywhere. Example for a (2x3) integer matrix: 2 3 1 1 2 3 4 5 6 column size
Definition at line 93 of file matrix_io.c.
References assert, f(), fscan_Value(), MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_new(), value_notzero_p, and value_pos_p.
Referenced by Hierarchical_tiling(), main(), Tiling2_buffer(), and Tiling_buffer_allocation().
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
inv_a | nv_a |
Definition at line 216 of file inversion.c.
References assert, exit, fprintf(), MATRIX_DENOMINATOR, matrix_hermite(), matrix_hermite_rank(), matrix_multiply(), MATRIX_NB_LINES, matrix_new(), matrix_triangular_inversion(), VALUE_ONE, and value_pos_p.
Referenced by build_contraction_matrices(), and prepare_reindexing().
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:
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
MAT | AT |
det_p | et_p |
det_q | et_q |
Definition at line 78 of file hermite.c.
References ALL, assert, level, matrix_assign(), matrix_coeff_nnul(), MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_free, matrix_identity(), matrix_line_el(), MATRIX_NB_COLUMNS, MATRIX_NB_LINES, matrix_new(), matrix_nulle(), matrix_subtraction_column(), matrix_swap_columns(), matrix_swap_rows(), Q, SUB_MATRIX_ELEM, value_div, VALUE_ONE, value_one_p, value_uminus, VALUE_ZERO, and x.
Referenced by extract_lattice(), matrix_determinant(), matrix_general_inversion(), matrix_unimodular_inversion(), prepare_reindexing(), and region_sc_minimal().
int matrix_hermite_rank(Pmatrix a): rang d'une matrice en forme de hermite
Definition at line 174 of file hermite.c.
References MATRIX_ELEM, and MATRIX_NB_LINES.
Referenced by matrix_diagonal_inversion(), matrix_general_inversion(), and matrix_triangular_inversion().
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
ID | D |
level | evel |
Definition at line 322 of file sub-matrix.c.
References level, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_LINES, VALUE_ONE, and VALUE_ZERO.
Referenced by build_contraction_matrices(), extract_lattice(), matrix_hermite(), matrix_maj_col(), matrix_maj_line(), matrix_smith(), matrix_unimodular_triangular_inversion(), and smith_int().
bool matrix_identity_p(Pmatrix ID, int level) test d'une sous-matrice dans ID(level+1..n, level+1..n) pour savoir si c'est une matrice identity.
Le test n'est correct que si la matrice ID passee en argument est normalisee (cf. matrix_normalize())
Pour tester toute la matrice ID, appeler avec level==0
Les parametres de la fonction :
int ID[] : matrice int n : nombre de lignes (et de colonnes) de la matrice ID int level : niveau de la matrice i.e. numero de la premiere ligne et de la premiere colonne a partir duquel on commence a prendre en compte les elements de la matrice
i!=j
ID | D |
level | evel |
Definition at line 352 of file sub-matrix.c.
References level, MATRIX_ELEM, MATRIX_NB_LINES, value_notone_p, and value_notzero_p.
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)
MAT | AT |
level | evel |
Definition at line 379 of file sub-matrix.c.
References level, MATRIX_ELEM, and MATRIX_NB_COLUMNS.
Referenced by matrix_hermite(), matrix_smith(), and smith_int().
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 72 of file sub-matrix.c.
References level, MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.
Referenced by matrix_coeff_nnul().
void matrix_maj_col(Pmatrix A, matrice P, int level): Calcul de la matrice permettant de remplacer chaque terme de la premiere ligne de la sous-matrice A(level+1 ..n, level+1 ..m) autre que le premier terme A11=A(level+1,level+1) par le reste de sa division entiere par A11
La matrice P est modifiee.
Les parametres de la fonction :
int A[1..n,1..m] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice (unused) !int P[] : matrice de dimension au moins P[1..n, 1..n] int level : niveau de la matrice i.e. numero de la premiere ligne et de la premiere colonne a partir duquel on commence a prendre en compte les elements de la matrice RGSUSED
level | evel |
Definition at line 256 of file sub-matrix.c.
References level, MATRIX_ELEM, matrix_identity(), MATRIX_NB_LINES, SUB_MATRIX_ELEM, value_division, value_uminus, and x.
Referenced by smith_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
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 294 of file sub-matrix.c.
References level, MATRIX_ELEM, matrix_identity(), MATRIX_NB_COLUMNS, Q, SUB_MATRIX_ELEM, value_div, value_uminus, and x.
Referenced by smith_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.
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 196 of file sub-matrix.c.
References level, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, min, value_abs, value_gt, value_lt, value_notzero_p, VALUE_ONE, and VALUE_ZERO.
Referenced by matrix_smith(), and smith_int().
void matrix_multiply(Pmatrix a, Pmatrix b, Pmatrix c): multiply rational matrix a by rational matrix b and store result in matrix c
a is a (pxq) matrix, b a (qxr) and c a (pxr) c := a x b ;
Algorithm used is directly from definition, and space has to be provided for output matrix c by caller. Matrix c is not necessarily normalized: its denominator may divide all its elements (see matrix_normalize()).
Precondition: p > 0; q > 0; r > 0; c != a; c != b; – aliasing between c and a or b – is not supported
validate dimensions
simplified aliasing test
set denominator
use ordinary school book algorithm
Definition at line 95 of file matrix.c.
References assert, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, value_addto, value_mult, and VALUE_ZERO.
Referenced by extract_lattice(), fusion_buffer(), make_reindex(), matrices_to_1D_lattice(), matrix_general_inversion(), matrix_unimodular_inversion(), prepare_reindexing(), region_sc_minimal(), sc_resol_smith(), smith_int(), and Tiling_buffer_allocation().
cproto-generated files
alloc.c
cproto-generated files
Definition at line 41 of file alloc.c.
References Pmatrix::coefficients, Pmatrix::denominator, malloc(), Pmatrix::number_of_columns, Pmatrix::number_of_lines, and VALUE_ONE.
Referenced by call_rwt(), compute_delay_merged_nest(), compute_delay_tiled_nest(), extract_lattice(), fusion_buffer(), main(), make_reindex(), matrices_to_1D_lattice(), matrix_determinant(), matrix_fscan(), matrix_general_inversion(), matrix_hermite(), matrix_sub_determinant(), matrix_unimodular_inversion(), prepare_reindexing(), region_sc_minimal(), sc_resol_smith(), smith_int(), Tiling2_buffer(), Tiling_buffer_allocation(), transformer_to_1D_lattice(), xml_Connection(), xml_ConstOffset(), xml_LoopOffset(), and xml_Transposition().
void matrix_normalize | ( | Pmatrix | a | ) |
void matrix_normalize(Pmatrix a)
A rational matrix is stored as an integer one with one extra integer, the denominator for all the elements. To normalise the matrix in this sense means to reduce this denominator to the smallest positive number possible. All elements are also reduced to their smallest possible value.
Precondition: MATRIX_DENOMINATOR(a)!=0
we must find the GCD of all elements of matrix
factor out
ensure denominator is positive
FI: this code is useless because pgcd()always return a positive integer, even if a is the null matrix; its denominator CANNOT be 0
Definition at line 136 of file matrix.c.
References assert, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, pgcd, value_division, value_notone_p, and value_pos_p.
Referenced by make_reindex(), and prepare_reindexing().
void matrix_normalizec | ( | Pmatrix | MAT | ) |
void matrix_normalizec(Pmatrix MAT): Normalisation des coefficients de la matrice MAT, i.e.
division des coefficients de la matrice MAT et de son denominateur par leur pgcd
La matrice est modifiee.
Les parametres de la fonction :
!int MAT[] : matrice de dimension (n,m) int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice
??? matrix is supposed to be positive?
MAT | AT |
Definition at line 187 of file matrix.c.
References assert, Pmatrix::coefficients, MATRIX_DENOMINATOR, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, pgcd, value_division, value_gt, and VALUE_ONE.
Referenced by sc_resol_smith(), and smith_int().
void matrix_nulle | ( | Pmatrix | Z | ) |
void matrix_nulle(Pmatrix Z): Initialisation de la matrice Z a la valeur matrice nulle
Post-condition:
QQ i dans [1..n] QQ j dans [1..n] Z(i,j) == 0
Definition at line 293 of file matrix.c.
References MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, VALUE_ONE, and VALUE_ZERO.
Referenced by build_contraction_matrices(), compute_delay_merged_nest(), compute_delay_tiled_nest(), constraints_to_matrices(), constraints_with_sym_cst_to_matrices(), egalites_to_matrice(), matrix_diagonal_inversion(), matrix_hermite(), matrix_perm_col(), matrix_perm_line(), matrix_triangular_inversion(), my_constraints_with_sym_cst_to_matrices(), sc_resol_smith(), smith_int(), and sys_mat_conv().
bool matrix_nulle_p(Pmatrix Z): test de nullite de la matrice Z
QQ i dans [1..n] QQ j dans [1..n] Z(i,j) == 0
Definition at line 311 of file matrix.c.
References MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, and VALUE_ZERO.
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
MAT | AT |
level | evel |
Definition at line 115 of file sub-matrix.c.
References level, MATRIX_ELEM, MATRIX_NB_LINES, matrix_nulle(), and VALUE_ONE.
Referenced by smith_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)).
parametres de la fonction :
!int MAT[] : matrice int n : nombre de lignes de la matrice (unused) int m : nombre de colonnes de la matrice int k : numero de la colonne a placer a la premiere colonne int level : niveau de la matrice i.e. numero de la premiere ligne et de la premiere colonne a partir duquel on commence a prendre en compte les elements de la matrice RGSUSED
MAT | AT |
level | evel |
Definition at line 150 of file sub-matrix.c.
References level, MATRIX_ELEM, MATRIX_NB_COLUMNS, matrix_nulle(), SUB_MATRIX_ELEM, and VALUE_ONE.
Referenced by smith_int().
void matrix_print | ( | Pmatrix | a | ) |
void matrix_print(matrice a): print an (nxm) rational matrix
Note: the output format is incompatible with matrix_fscan() this should be implemented as a macro, but it's a function for dbx's sake
Definition at line 70 of file matrix_io.c.
References matrix_fprint().
Referenced by Hierarchical_tiling(), matrix_smith(), sc_resol_smith(), smith_int(), and Tiling2_buffer().
void matrix_rm | ( | Pmatrix | a | ) |
Definition at line 52 of file alloc.c.
References Pmatrix::coefficients, and free().
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 ALL, assert, D, level, matrix_assign(), matrix_col_el(), MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_identity(), matrix_line_el(), matrix_min(), MATRIX_NB_COLUMNS, MATRIX_NB_LINES, matrix_print(), matrix_subtraction_column(), matrix_subtraction_line(), matrix_swap_columns(), matrix_swap_rows(), printf(), Q, SUB_MATRIX_ELEM, value_div, value_one_p, VALUE_ZERO, and x.
Referenced by main(), matrices_to_1D_lattice(), and sc_resol_smith().
void matrix_substract(Pmatrix a, Pmatrix b, Pmatrix c): substract rational matrix c from rational matrix b and store result in matrix a
a is a (nxm) matrix, b a (nxm) and c a (nxm) a = b - c ;
Algorithm used is directly from definition, and space has to be provided for output matrix a by caller. Matrix a is not necessarily normalized: its denominator may divide all its elements (see matrix_normalize()).
Precondition: n > 0; m > 0; Note: aliasing between a and b or c is supported
denominators of b, c
ppcm of b,c
precondition
Definition at line 435 of file matrix.c.
References assert, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, ppcm(), value_div, value_eq, value_minus, value_mult, and value_pos_p.
Referenced by compute_delay_merged_nest(), compute_delay_tiled_nest(), fusion_buffer(), and Tiling_buffer_allocation().
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 :
MAT | AT |
c1 | 1 |
c2 | 2 |
Definition at line 518 of file matrix.c.
References MATRIX_ELEM, MATRIX_NB_LINES, value_mult, value_substract, and x.
Referenced by matrix_hermite(), matrix_smith(), and matrix_unimodular_triangular_inversion().
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 :
MAT | AT |
r1 | 1 |
r2 | 2 |
Definition at line 541 of file matrix.c.
References MATRIX_ELEM, MATRIX_NB_COLUMNS, value_mult, value_substract, and x.
Referenced by matrix_smith().
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;
c1 | 1 |
c2 | 2 |
Definition at line 209 of file matrix.c.
References assert, MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.
Referenced by matrix_hermite(), and matrix_smith().
void matrix_swap_rows(Pmatrix a, int r1, int r2): exchange rows r1 and r2 of an (nxm) rational matrix a
Precondition: n > 0; m > 0; 1 <= r1 <= n; 1 <= r2 <= n
r1 | 1 |
r2 | 2 |
Definition at line 230 of file matrix.c.
References assert, MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.
Referenced by matrix_hermite(), and matrix_smith().
void matrix_transpose(Pmatrix a, Pmatrix a_t): transpose an (nxm) rational matrix a into a (mxn) rational matrix a_t
t
At := A ;
verification step
copy from a to a_t
At | t |
Definition at line 64 of file matrix.c.
References assert, MATRIX_DENOMINATOR, MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.
Referenced by region_sc_minimal().
void matrix_triangular_inversion(Pmatrix h, Pmatrix inv_h,bool infer) calcul de l'inversion du matrice en forme triangulaire.
soit h matrice de la reduite triangulaire; inv_h est l'inversion de h ; telle que : h * inv_h = I. selon les proprietes de la matrice triangulaire: Aii = a11* ...aii-1*aii+1...*ann; Aij = 0 i>j pour la matrice triangulaire inferieure (infer==true) i<j pour la matrice triangulaire superieure (infer==false)
les parametres de la fonction : matrice h : matrice en forme triangulaire – input matrice inv_h : l'inversion de h – output int n : dimension de la matrice caree – input bool infer : le type de triangulaire – input
denominateur
determinant
tests des preconditions
calcul du determinant de h
calcul du denominateur de inv_h
calcul des sub_determinants des Aii
calcul des sub_determinants des Aij (i<j)
inv_h | nv_h |
infer | nfer |
Definition at line 137 of file inversion.c.
References assert, MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_hermite_rank(), MATRIX_NB_LINES, matrix_nulle(), matrix_sub_determinant(), matrix_triangular_p(), pgcd, value_division, value_mult, value_neg_p, value_notone_p, VALUE_ONE, value_one_p, value_oppose, value_pos_p, and value_product.
Referenced by matrix_general_inversion().
bool matrix_triangular_p(Pmatrix Z, bool inferieure): test de triangularite de la matrice Z
si inferieure == true QQ i dans [1..n] QQ j dans [i+1..m] Z(i,j) == 0
si inferieure == false (triangulaire superieure) QQ i dans [1..n] QQ j dans [1..i-1] Z(i,j) == 0
Les parametres de la fonction :
int Z[] : matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice
inferieure | nferieure |
Definition at line 367 of file matrix.c.
References MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.
Referenced by matrix_triangular_inversion(), and matrix_triangular_unimodular_p().
bool matrix_triangular_unimodular_p(Pmatrix Z, bool inferieure) test de la triangulaire et unimodulaire de la matrice Z.
si inferieure == true QQ i dans [1..n] QQ j dans [i+1..n] Z(i,j) == 0 i dans [1..n] Z(i,i) == 1
si inferieure == false (triangulaire superieure) QQ i dans [1..n] QQ j dans [1..i-1] Z(i,j) == 0 i dans [1..n] Z(i,i) == 1 les parametres de la fonction : matrice Z : la matrice entre
inferieure | nferieure |
Definition at line 403 of file matrix.c.
References assert, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, matrix_triangular_p(), and value_notone_p.
Referenced by extract_lattice(), matrix_unimodular_inversion(), and matrix_unimodular_triangular_inversion().
void matrix_uminus(A, mA)
computes mA = - A
input: A, larger allocated mA output: none modifies: mA
mA | A |
Definition at line 558 of file matrix.c.
References assert, MATRIX_ELEM, MATRIX_NB_COLUMNS, MATRIX_NB_LINES, and value_uminus.
Referenced by extract_lattice().
void matrix_unimodular_inversion(Pmatrix u, Pmatrix inv_u) 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 261 of file inversion.c.
References assert, MATRIX_DENOMINATOR, matrix_hermite(), matrix_multiply(), MATRIX_NB_LINES, matrix_new(), matrix_triangular_unimodular_p(), matrix_unimodular_triangular_inversion(), and value_one_p.
inversion.c
inversion.c
void matrix_unimodular_triangular_inversion(Pmatrix u ,Pmatrix inv_u,
Pmatrix u : matrice unimodulaire triangulaire – inpout int n : dimension de la matrice caree – inpout bool infer : type de triangulaire – input matrice inv_u : l'inversion de matrice u – output
test de l'unimodularite et de la trangularite de u
inv_u | nv_u |
infer | nfer |
Definition at line 53 of file inversion.c.
References assert, MATRIX_ELEM, matrix_identity(), MATRIX_NB_LINES, matrix_subtraction_column(), matrix_triangular_unimodular_p(), value_notzero_p, and x.
Referenced by extract_lattice(), and matrix_unimodular_inversion().
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.
A_sub | _sub |
i1 | 1 |
i2 | 2 |
j1 | 1 |
j2 | 2 |
Definition at line 469 of file sub-matrix.c.
References MATRIX_ELEM.
Referenced by extract_lattice(), and region_sc_minimal().