PIPS
|
#include <stdio.h>
#include <stdlib.h>
#include "linear_assert.h"
#include "boolean.h"
#include "arithmetique.h"
#include "matrix.h"
Go to the source code of this file.
Functions | |
Value * | matrix_elem_ref (Pmatrix M, int r, int c) |
package matrix More... | |
Value | matrix_elem (Pmatrix M, int r, int c) |
void | matrix_transpose (const Pmatrix A, Pmatrix At) |
void matrix_transpose(Pmatrix a, Pmatrix a_t): transpose an (nxm) rational matrix a into a (mxn) rational matrix a_t More... | |
void | matrix_multiply (const Pmatrix a, const Pmatrix b, Pmatrix c) |
void matrix_multiply(Pmatrix a, Pmatrix b, Pmatrix c): multiply rational matrix a by rational matrix b and store result in matrix c More... | |
void | matrix_normalize (Pmatrix a) |
void matrix_normalize(Pmatrix a) More... | |
void | matrix_normalizec (Pmatrix MAT) |
void matrix_normalizec(Pmatrix MAT): Normalisation des coefficients de la matrice MAT, i.e. More... | |
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 More... | |
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 More... | |
void | matrix_assign (Pmatrix A, Pmatrix B) |
void matrix_assign(Pmatrix A, Pmatrix B) Copie de la matrice A dans la matrice B More... | |
bool | matrix_equality (Pmatrix A, Pmatrix B) |
bool matrix_equality(Pmatrix A, Pmatrix B) test de l'egalite de deux matrices A et B; elles doivent avoir ete normalisees au prealable pour que le test soit mathematiquement exact More... | |
void | matrix_nulle (Pmatrix Z) |
void matrix_nulle(Pmatrix Z): Initialisation de la matrice Z a la valeur matrice nulle More... | |
bool | matrix_nulle_p (Pmatrix Z) |
bool matrix_nulle_p(Pmatrix Z): test de nullite de la matrice Z More... | |
bool | matrix_diagonal_p (Pmatrix Z) |
bool matrix_diagonal_p(Pmatrix Z): test de nullite de la matrice Z More... | |
bool | matrix_triangular_p (Pmatrix Z, bool inferieure) |
bool matrix_triangular_p(Pmatrix Z, bool inferieure): test de triangularite de la matrice Z More... | |
bool | matrix_triangular_unimodular_p (Pmatrix Z, bool inferieure) |
bool matrix_triangular_unimodular_p(Pmatrix Z, bool inferieure) test de la triangulaire et unimodulaire de la matrice Z. More... | |
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 More... | |
void | matrix_add (Pmatrix a, Pmatrix b, Pmatrix c) |
a = b + c More... | |
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]. More... | |
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] More... | |
void | matrix_uminus (Pmatrix A, Pmatrix mA) |
void matrix_uminus(A, mA) More... | |
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().
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().
package matrix
Definition at line 41 of file matrix.c.
References assert, Pmatrix::coefficients, and MATRIX_ELEM.
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_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().
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_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().
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().