matrice.h File Reference

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

Macro Definition Documentation

ACC_ELEM

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

d'apres ce que je comprends de la suite, ca permet de definir des sous-matrices dont le coin superieur droit (i.e. le premier element) se trouve sur la diagonal?

Definition at line 120 of file matrice.h.

ACCESS

#define ACCESS	(		matrix,
			column,
			i,
			j
	)		((matrix)[(((j)-1)*(column))+(i)])

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.

Definition at line 94 of file matrice.h.

DENOMINATOR

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

#define DENOMINATOR(matrix) *(&((matrix)[0]))

Definition at line 101 of file matrice.h.

matrice_free

#define matrice_free

(

m

)

(free((char *) (m)))

Definition at line 86 of file matrice.h.

matrice_new

#define matrice_new	(		n,
			m
	)		((matrice) malloc(sizeof(Value)*((n*m)+1)))

Allocation et desallocation d'une matrice.

Definition at line 85 of file matrice.h.

MATRICE_NULLE

#define MATRICE_NULLE   ((matrice) NULL)

Definition at line 82 of file matrice.h.

matrice_triangulaire_inferieure_p

#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

Definition at line 106 of file matrice.h.

matrice_triangulaire_superieure_p

#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

Definition at line 112 of file matrice.h.

MATRICE_UNDEFINED

#define MATRICE_UNDEFINED   ((matrice) NULL)

Definition at line 81 of file matrice.h.

MATRIX

#define MATRIX   0

FI #define NULL 0.

Definition at line 128 of file matrice.h.

VALIDATION

#define VALIDATION   0

FI: Corinne, pourrais-tu nous eclairer sur la signification de ces constantes?

Definition at line 126 of file matrice.h.

Typedef Documentation

matrice

typedef Value* matrice

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()

Definition at line 79 of file matrice.h.

Function Documentation

dim_H()

int dim_H	(	matrice	H,
		int	n,
		int	m
	)

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.

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

References ACCESS, and value_zero_p.

Referenced by prototype_dimension(), and sc_image_computation().

Here is the caller graph for this function:

mat_coeff_nnul()

void mat_coeff_nnul	(	matrice	MAT,
		int	n,
		int	m,
		int *	lg_nnul,
		int *	cl_nnul,
		int	level
	)

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

Parameters

MAT	AT
lg_nnul	g_nnul
cl_nnul	l_nnul
level	evel

Definition at line 426 of file sous-matrice.c.

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

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().

Here is the call graph for this function:

Here is the caller graph for this function:

mat_col_el()

int mat_col_el	(	matrice	,
		int	,
		int	,
		int
	)

Referenced by matrice_smith().

Here is the caller graph for this function:

mat_lig_el()

int mat_lig_el	(	matrice	MAT,
		int	n,
		int	m,
		int	level
	)

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)

Parameters

MAT	AT
level	evel

Definition at line 381 of file sous-matrice.c.

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

References ACCESS, level, and value_zero_p.

Referenced by matrice_hermite(), and matrice_smith().

Here is the caller graph for this function:

mat_lig_nnul()

int mat_lig_nnul	(	matrice	MAT,
		int	n,
		int	m,
		int	level
	)

sous-matrice.c

sous-matrice.c

resultat retourne par la fonction :

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

parametres de la fonction :

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

recherche du premier element non nul de la sous-matrice

on dumpe la colonne J...

Parameters

MAT	AT
level	evel

Definition at line 65 of file sous-matrice.c.

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

References ACCESS, level, and value_zero_p.

Referenced by mat_coeff_nnul().

Here is the caller graph for this function:

mat_maj_col()

void mat_maj_col	(	matrice	,
		int	,
		int	,
		matrice	,
		int
	)

mat_maj_lig()

void mat_maj_lig	(	matrice	A,
		int	n,
		int	m,
		matrice	Q,
		int	level
	)

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

Parameters

level

evel

Definition at line 292 of file sous-matrice.c.

{
    register Value A11;
    int j;
    register Value x;
 
    matrice_identite(Q,m,0);
    A11 = ACC_ELEM(A,n,1,1,level);
    for (j=2+level; j<=m; j++) {
        x = ACCESS(A,n,1+level,j);
        value_division(x,A11);
        ACCESS(Q,m,1+level,j) = value_uminus(x);
    }
}

References ACC_ELEM, ACCESS, level, matrice_identite(), Q, value_division, value_uminus, and x.

Here is the call graph for this function:

mat_min()

void mat_min	(	matrice	MAT,
		int	n,
		int	m,
		int *	i_min,
		int *	j_min,
		int	level
	)

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

Parameters

MAT	AT
i_min	_min
j_min	_min
level	evel

Definition at line 193 of file sous-matrice.c.

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

References ACCESS, level, min, value_absolute, value_gt, value_lt, value_notzero_p, VALUE_ONE, and VALUE_ZERO.

Referenced by matrice_smith().

Here is the caller graph for this function:

mat_perm_col()

void mat_perm_col	(	matrice	,
		int	,
		int	,
		int	,
		int
	)

mat_perm_lig()

void mat_perm_lig	(	matrice	,
		int	,
		int	,
		int	,
		int
	)

matrice_assign()

void matrice_assign	(	matrice	A,
		matrice	B,
		int	n,
		int	m
	)

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.

{
    int i, size=n*m;
    for (i = 0 ;i<=size;i++)
        B[i] = A[i];
}

References B.

Referenced by matrice_hermite(), and matrice_smith().

Here is the caller graph for this function:

matrice_determinant()

void matrice_determinant	(	matrice	,
		int	,
		Value	[]
	)

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

matrice_diagonale_inversion()

void matrice_diagonale_inversion	(	matrice	s,
		matrice	inv_s,
		int	n
	)

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])

Parameters

inv_s

nv_s

Definition at line 95 of file inversion.c.

{
    Value d, d1; 
    Value gcd, lcm;
    int i;
 
    /* tests des preconditions */
    assert(matrice_diagonale_p(s,n,n));
    assert(matrice_hermite_rank(s,n,n)==n);
    assert(value_pos_p(DENOMINATOR(s)));
 
    matrice_nulle(inv_s,n,n);
    /* calcul de la ppcm(s[1,1],s[2,2],...s[n,n]) */
    lcm = ACCESS(s,n,1,1);
    for (i=2; i<=n; i++)
        lcm = ppcm(lcm,ACCESS(s,n,i,i));
    
    d = DENOMINATOR(s);
    gcd = pgcd_slow(lcm,d);
    d1 = value_div(d,gcd);
    for (i=1; i<=n; i++) {
        Value tmp = value_div(lcm,ACCESS(s,n,i,i));
        ACCESS(inv_s,n,i,i) = value_mult(d1,tmp);
    }
    DENOMINATOR(inv_s) = value_div(lcm,gcd);
}

References ACCESS, assert, DENOMINATOR, matrice_diagonale_p(), matrice_hermite_rank(), matrice_nulle(), pgcd_slow(), ppcm(), value_div, value_mult, and value_pos_p.

Here is the call graph for this function:

matrice_diagonale_p()

bool matrice_diagonale_p	(	matrice	Z,
		int	n,
		int	m
	)

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.

{
    int i,j;
 
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if(i!=j && value_notzero_p(ACCESS(Z,n,i,j)))
                return(false);
    return(true);
}

References ACCESS, and value_notzero_p.

Referenced by matrice_diagonale_inversion().

Here is the caller graph for this function:

matrice_egalite()

bool matrice_egalite	(	matrice	A,
		matrice	B,
		int	n,
		int	m
	)

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.

{
    int i;
    for (i = 0 ;i<= n*m;i++)
        if(value_ne(B[i],A[i]))
            return(false);
    return(true);
}

References B, and value_ne.

matrice_fprint()

void matrice_fprint	(	FILE *	f,
		matrice	a,
		int	n,
		int	m
	)

matrice_io.c

matrice_io.c

Note: the output format is incompatible with matrice_fscan() row size

Parameters

m	Note: the output format is incompatible with matrice_fscan() column size

Definition at line 62 of file matrice_io.c.

{
    int loop1,loop2;
 
    assert(value_notzero_p(DENOMINATOR(a)));
 
    (void) fprintf(f,"\n\n");
 
    for(loop1=1; loop1<=n; loop1++) {
        for(loop2=1; loop2<=m; loop2++)
            pr_quot(f, ACCESS(a,n,loop1,loop2), DENOMINATOR(a));
        (void) fprintf(f,"\n\n");
    }
    (void) fprintf(f," ......denominator = ");
    fprint_Value(f,DENOMINATOR(a));
    fprintf(f, "\n");
}

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().

Here is the call graph for this function:

Here is the caller graph for this function:

matrice_fscan()

void matrice_fscan	(	FILE *	f,
		matrice *	a,
		int *	n,
		int *	m
	)

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

Parameters

m

Format:

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

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

Definition at line 115 of file matrice_io.c.

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

References ACCESS, assert, DENOMINATOR, f(), fscan_Value(), matrice_new, value_notzero_p, and value_pos_p.

Referenced by unimodular().

Here is the call graph for this function:

Here is the caller graph for this function:

matrice_general_inversion()

void matrice_general_inversion	(	matrice	a,
		matrice	inv_a,
		int	n
	)

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

Parameters

inv_a

nv_a

Definition at line 222 of file inversion.c.

{
    matrice p = matrice_new(n,n);
    matrice q = matrice_new(n,n);
    matrice h = matrice_new(n,n);
    matrice inv_h = matrice_new(n,n);
    matrice temp = matrice_new(n,n);
    Value deno;
    Value det_p, det_q; /* ne utilise pas */
 
    /* test */
    assert(value_pos_p(DENOMINATOR(a)));
 
    deno = DENOMINATOR(a);
    DENOMINATOR(a) = VALUE_ONE;
    matrice_hermite(a,n,n,p,h,q,&det_p,&det_q);
    DENOMINATOR(a) = deno;
    if ( matrice_hermite_rank(h,n,n) == n){
        DENOMINATOR(h) = deno;
        matrice_triangulaire_inversion(h,inv_h,n,true);
        matrice_multiply(q,inv_h,temp,n,n,n);
        matrice_multiply(temp,p,inv_a,n,n,n);
    }
    else{
        printf(" L'inverse de la matrice a n'existe pas!\n");
        exit(1);
    }
}

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().

Here is the call graph for this function:

Here is the caller graph for this function:

matrice_hermite()

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:

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

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

niveau de la sous-matrice traitee

le plus petit element sur la diagonale

la 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

Parameters

MAT	AT
det_p	et_p
det_q	et_q

Definition at line 78 of file hermite.c.

{
    Value *PN=NULL;
    Value *QN=NULL;
    Value *HN = NULL;
 
    /* indice de la ligne et indice de la colonne correspondant
       au plus petit element de la sous-matrice traitee */
    int ind_n,ind_m;   
 
    /* niveau de la sous-matrice traitee */
    int level = 0;    
    
    register Value ALL; /* le plus petit element sur la diagonale */
    register Value x;    /* la rest de la division par ALL */
    bool stop = false;
    int i;
    
    *det_p = VALUE_ONE;
    *det_q = VALUE_ONE;
 
    /* if ((n>0) && (m>0) && MAT) */
    assert((n > 0) && (m > 0));
    assert(value_one_p(DENOMINATOR(MAT)));
 
    HN = matrice_new(n, m);
    PN = matrice_new(n, n);
    QN = matrice_new(m, m);
   
    /* Initialisation des matrices */
 
    matrice_assign(MAT,H,n,m);
    matrice_identite(PN,n,0);
    matrice_identite(QN,m,0);
    matrice_identite(P,n,0);
    matrice_identite(Q,m,0);
    matrice_nulle(HN,n,m);
 
    while (!stop) {  
        /* tant qu'il reste des termes non nuls dans la partie 
           triangulaire superieure  de la matrice H,        
           on cherche le plus petit element de la sous-matrice     */
        mat_coeff_nnul(H,n,m,&ind_n,&ind_m,level);
 
        if (ind_n == 0 && ind_m == 0)
                /* la sous-matrice restante est nulle, on a terminee */
            stop = true; 
        else { 
            /* s'il existe un plus petit element non nul dans la partie
               triangulaire superieure de la sous-matrice,
               on amene cet element en haut sur la diagonale.
               si cet element est deja sur la diagonale, et que  tous les 
               termes de la ligne correspondante sont nuls,
               on effectue les calculs sur la sous-matrice de rang superieur*/
               
            if (ind_n > level + 1) {
                matrice_swap_rows(H,n,m,level+1,ind_n);
                matrice_swap_rows(PN,n,n,level+1,ind_n);
                value_oppose(*det_p);
            }
 
            if (ind_m > level+1) {
                matrice_swap_columns(H,n,m,level+1,ind_m);
                matrice_swap_columns(QN,m,m,level+1,ind_m);     
                value_oppose(*det_q);
            }
 
            if(mat_lig_el(H,n,m,level) != 0) {
                ALL = ACC_ELEM(H,n,1,1,level);
                for (i=level+2; i<=m; i++) {
                    x = ACCESS(H,n,level+1,i);
                    value_division(x,ALL);
                    matrice_soustraction_colonne(H,n,m,i,level+1,x);
                    matrice_soustraction_colonne(QN,m,m,i,level+1,x);
                }
 
            }
            else level++;
        }
    }
 
    matrice_assign(PN,P,n,n);
    matrice_assign(QN,Q,m,m);
 
    matrice_free(HN);
    matrice_free(PN);
    matrice_free(QN);
}

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().

Here is the call graph for this function:

Here is the caller graph for this function:

matrice_hermite_rank()

int matrice_hermite_rank	(	matrice	,
		int	,
		int
	)

matrice_identite()

void matrice_identite	(	matrice	ID,
		int	n,
		int	level
	)

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

Parameters

ID	D
level	evel

Definition at line 322 of file sous-matrice.c.

{
    int i,j;
 
    for(i = level+1; i <= n; i++) {
        for(j = level+1; j <= n; j++)
            ACCESS(ID,n,i,j) = VALUE_ZERO;
        ACCESS(ID,n,i,i) = VALUE_ONE;
    }
 
    DENOMINATOR(ID) = VALUE_ONE;
}

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().

Here is the caller graph for this function:

matrice_identite_p()

bool matrice_identite_p	(	matrice	ID,
		int	n,
		int	level
	)

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

Parameters

ID	D
level	evel

Definition at line 353 of file sous-matrice.c.

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

References ACCESS, level, value_notone_p, and value_notzero_p.

matrice_multiply()

void matrice_multiply	(	matrice	a,
		matrice	b,
		matrice	c,
		int	p,
		int	q,
		int	r
	)

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

Parameters

b	a is a (pxq) matrix, b a (qxr) and c a (pxr) c := a x b ; Algorithm used is directly from definition, and space has to be provided for output matrix c by caller. Matrix c is not necessarily normalized: its denominator may divide all its elements (see matrice_normalize()).

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

Parameters

c	a is a (pxq) matrix, b a (qxr) and c a (pxr) c := a x b ; Algorithm used is directly from definition, and space has to be provided for output matrix c by caller. Matrix c is not necessarily normalized: its denominator may divide all its elements (see matrice_normalize()).

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

Parameters

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

Parameters

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

Parameters

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.

{
    int loop1,loop2,loop3;
    register Value i,va,vb;
 
    /* validate dimensions */
    assert(p > 0 && q > 0 && r > 0);
    /* simplified aliasing test */
    assert(c != a && c != b);
 
    /* set denominator */
    DENOMINATOR(c) = value_mult(DENOMINATOR(a),DENOMINATOR(b));
 
    /* use ordinary school book algorithm */
    for(loop1=1; loop1<=p; loop1++)
        for(loop2=1; loop2<=r; loop2++) {
            i = VALUE_ZERO;
            for(loop3=1; loop3<=q; loop3++) 
            {
                va = ACCESS(a,p,loop1,loop3);
                vb = ACCESS(b,q,loop3,loop2);
                value_addto(i,value_mult(va,vb));
            }
            ACCESS(c,p,loop1,loop2) = i;
        }
}

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().

Here is the caller graph for this function:

matrice_normalize()

void matrice_normalize	(	matrice	a,
		int	n,
		int	m
	)

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

Parameters

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.

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

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().

Here is the caller graph for this function:

matrice_normalizec()

void matrice_normalizec	(	matrice	MAT,
		int	n,
		int	m
	)

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()

Parameters

MAT

AT

Definition at line 175 of file matrice.c.

{
    int i;
    Value a;
 
    /* FI What an awful test! It should be an assert() */
    if (n && m) {
        a = MAT[0];
        for (i = 1;(i<=n*m) && value_gt(a,VALUE_ONE);i++)
            a = pgcd(a,MAT[i]);
 
        if (value_gt(a,VALUE_ONE)) {
            for (i = 0;i<=n*m;i++)
                value_division(MAT[i],a);
        }
    }
}

References pgcd, value_division, value_gt, and VALUE_ONE.

matrice_nulle()

void matrice_nulle	(	matrice	Z,
		int	n,
		int	m
	)

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.

{
    int i,j;
 
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            ACCESS(Z,n,i,j)=VALUE_ZERO;
    DENOMINATOR(Z) = VALUE_ONE;
}

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().

Here is the caller graph for this function:

matrice_nulle_p()

bool matrice_nulle_p	(	matrice	Z,
		int	n,
		int	m
	)

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.

{
    int i,j;
 
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if(value_notzero_p(ACCESS(Z,n,i,j)))
                return(false);
    return(true);
}

References ACCESS, and value_notzero_p.

matrice_print()

void matrice_print	(	matrice	a,
		int	n,
		int	m
	)

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

Parameters

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.

{
    matrice_fprint(stdout,a,n,m);
}

References matrice_fprint().

Referenced by matrice_smith().

Here is the call graph for this function:

Here is the caller graph for this function:

matrice_smith()

void matrice_smith	(	matrice	MAT,
		int	n,
		int	m,
		matrice	P,
		matrice	D,
		matrice	Q
	)

smith.c

smith.c

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

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

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

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

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

le plus petit element sur la diagonale

le rest de la division par ALL

precondition sur les parametres

le transformation n'est pas fini.

Parameters

MAT

AT

Definition at line 68 of file smith.c.

{
    int n_min,m_min;
    int level = 0;
    register Value ALL;        /* le plus petit element sur la diagonale */
    register Value x;          /* le rest de la division par ALL */
    int i;
    
    bool stop = false;
    bool next = true;
 
    /* precondition sur les parametres */
    assert(m > 0 && n >0);
    matrice_assign(MAT,D,n,m);
    assert(value_one_p(DENOMINATOR(D)));
 
    matrice_identite(P,n,0);
    matrice_identite(Q,m,0);
 
    while (!stop) {
        mat_min(D,n,m,&n_min,&m_min,level);
                
        if ((n_min == 0) && (m_min == 0))
            stop = true;
        else {
            /* le transformation n'est pas fini. */
            if (n_min > level +1) {
                matrice_swap_rows(D,n,m,level+1,n_min);
                matrice_swap_rows(P,n,n,level+1,n_min);
            }
#ifdef TRACE
            (void) printf (" apres alignement du plus petit element a la premiere ligne \n");
            matrice_print(D,n,m);
#endif
            if (m_min >1+level) {
                matrice_swap_columns(D,n,m,level+1,m_min);
                matrice_swap_columns(Q,m,m,level+1,m_min);
            }
#ifdef TRACE
            (void) printf (" apres alignement du plus petit element"
                           " a la premiere colonne\n");
            matrice_print(D,n,m);
#endif
           
            ALL = ACC_ELEM(D,n,1,1,level);
            if (mat_lig_el(D,n,m,level) != 0) 
                for (i=level+2; i<=m; i++) {
                    x = ACCESS(D,n,level+1,i);
                    value_division(x,ALL);
                    matrice_soustraction_colonne(D,n,m,i,level+1,x);
                    matrice_soustraction_colonne(Q,m,m,i,level+1,x);
                    next = false;
                }
            if (mat_col_el(D,n,m,level) != 0) 
                for(i=level+2;i<=n;i++) {
                    x = ACCESS(D,n,i,level+1);
                    value_division(x,ALL);
                    matrice_soustraction_ligne(D,n,m,i,level+1,x);
                    matrice_soustraction_ligne(P,n,n,i,level+1,x);
                    next = false;
                }
#ifdef TRACE
                (void) printf("apres division par A(%d,%d) des termes de la %d-ieme ligne et de la %d-em colonne \n",level+1,level+1,level+1,level+1);
                matrice_print(D,n,m);
#endif
            if (next) level++;
            next = true;
        }
    }
 
#ifdef TRACE
    (void) printf (" la  matrice D apres transformation est la suivante :");
    matrice_print(D,n,m);
 
    (void) printf (" la matrice P est \n");
    matrice_print(P,n,n);
 
    (void) printf (" la matrice Q est \n");
    matrice_print(Q,m,m);
#endif
}

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().

Here is the call graph for this function:

Here is the caller graph for this function:

matrice_sous_determinant()

void matrice_sous_determinant	(	matrice	,
		int	,
		int	,
		int	,
		Value	[]
	)

matrice_soustraction_colonne()

void matrice_soustraction_colonne	(	matrice	,
		int	,
		int	,
		int	,
		int	,
		Value
	)

matrice_soustraction_ligne()

void matrice_soustraction_ligne	(	matrice	MAT,
		int	n,
		int	m,
		int	r1,
		int	r2,
		Value	x
	)

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 :

Parameters

MAT	AT
r1	1
r2	2

Definition at line 554 of file matrice.c.

{
    int i;
    register Value p;
    for (i=1; i<=m; i++)
    {
        p = ACCESS(MAT,n,r2,i);
        value_product(p,x);
        value_substract(ACCESS(MAT,n,r1,i),p);
    }
}

References ACCESS, value_product, value_substract, and x.

Referenced by matrice_smith().

Here is the caller graph for this function:

matrice_substract()

void matrice_substract	(	matrice	a,
		matrice	b,
		matrice	c,
		int	n,
		int	m
	)

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

Parameters

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

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

Parameters

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.

{
    register Value d1,d2;   /* denominators of b, c */
    register Value lcm;     /* ppcm of b,c */
    int i,j;
 
    /* precondition */
    assert(n>0 && m>0);
    assert(value_pos_p(DENOMINATOR(b)));
    assert(value_pos_p(DENOMINATOR(c)));
 
    d1 = DENOMINATOR(b);
    d2 = DENOMINATOR(c);
    if (d1 == d2){
        for (i=1; i<=n; i++)
            for (j=1; j<=m; j++)
                ACCESS(a,n,i,j) = value_minus(ACCESS(b,n,i,j),
                                              ACCESS(c,n,i,j));
        DENOMINATOR(a) = d1;
    }
    else{
        register Value v1,v2;
        lcm = ppcm(d1,d2);
        DENOMINATOR(a) = lcm;
        d1 = value_div(lcm,d1);
        d2 = value_div(lcm,d2);
        for (i=1; i<=n; i++)
            for (j=1; j<=m; j++) 
            {
                v1 = ACCESS(b,n,i,j);
                value_product(v1, d1);
                v2 = ACCESS(c,n,i,j);
                value_product(v2, d2);
                ACCESS(a,n,i,j) = value_minus(v1,v2);
            }
    }
}

References ACCESS, assert, DENOMINATOR, ppcm(), value_div, value_minus, value_pos_p, and value_product.

Referenced by unstructured_to_complexity().

Here is the call graph for this function:

Here is the caller graph for this function:

matrice_swap_columns()

void matrice_swap_columns	(	matrice	matrix,
		int	n,
		int	m,
		int	c1,
		int	c2
	)

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

Parameters

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.

{
    int loop1;
    register Value temp;
 
    /* validation step */
    /*
     * if ((n < 1) || (m < 1))   return(-208);
     * if ((c1 > m) || (c2 > m)) return(-209);
     */
    assert(n > 0 && m > 0);
    assert(0 < c1 && c1 <= m);
    assert(0 < c2 && c2 <= m);
 
    for(loop1=1; loop1<=n; loop1++) {
        temp = ACCESS(matrix,n,loop1,c1);
        ACCESS(matrix,n,loop1,c1) = ACCESS(matrix,n,loop1,c2);
        ACCESS(matrix,n,loop1,c2) = temp;
    }
}       

References ACCESS, assert, and loop1.

Referenced by matrice_hermite(), and matrice_smith().

Here is the caller graph for this function:

matrice_swap_rows()

void matrice_swap_rows	(	matrice	a,
		int	n,
		int	m,
		int	r1,
		int	r2
	)

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

Parameters

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.

{
    int loop1;
    register Value temp;
 
    /* validation */
    assert(n > 0);
    assert(m > 0);
    assert(0 < r1 && r1 <= n);
    assert(0 < r2 && r2 <= n);
 
    for(loop1=1; loop1<=m; loop1++) {
        temp = ACCESS(a,n,r1,loop1);
        ACCESS(a,n,r1,loop1) = ACCESS(a,n,r2,loop1);
        ACCESS(a,n,r2,loop1) = temp;
    }
}

References ACCESS, assert, and loop1.

Referenced by matrice_hermite(), matrice_smith(), and scanning_base_hyperplane().

Here is the caller graph for this function:

matrice_transpose()

void matrice_transpose	(	matrice	a,
		matrice	a_t,
		int	n,
		int	m
	)

matrice.c

matrice.c

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

Parameters

a_t

_t

Definition at line 48 of file matrice.c.

{
    int loop1,loop2;
 
    /* verification step */
    assert(n >= 0 && m >= 0);
 
    /* copy from a to a_t */
    DENOMINATOR(a_t) = DENOMINATOR(a);
    for(loop1=1; loop1<=n; loop1++)
        for(loop2=1; loop2<=m; loop2++) 
            ACCESS(a_t,m,loop2,loop1) = ACCESS(a,n,loop1,loop2);
}

References ACCESS, assert, DENOMINATOR, and loop1.

Referenced by base_G_h1_unnull(), broadcast_conditions(), make_primal(), partial_broadcast_coefficients(), and system_inversion_restrict().

Here is the caller graph for this function:

matrice_triangulaire_inversion()

void matrice_triangulaire_inversion	(	matrice	h,
		matrice	inv_h,
		int	n,
		bool	infer
	)

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)

Parameters

inv_h	nv_h
infer	nfer

Definition at line 140 of file inversion.c.

{
    Value deno,deno1;                    /* denominateur */
    Value determinant,sous_determinant;  /* determinant */
    Value gcd;
    int i,j;
    Value aij[2];
    register Value a;
 
    /* tests des preconditions */
    assert(matrice_triangulaire_p(h,n,n,infer));
    assert(matrice_hermite_rank(h,n,n)==n);
    assert(value_pos_p(DENOMINATOR(h)));
 
    matrice_nulle(inv_h,n,n);
    deno = DENOMINATOR(h);
    deno1 = deno;
    DENOMINATOR(h) = VALUE_ONE;
    /* calcul du determinant de h */
    determinant = VALUE_ONE;
    for (i= 1; i<=n; i++){
        a = ACCESS(h,n,i,i);
        value_product(determinant,a);
    }
    /* calcul du denominateur de inv_h */
    gcd = pgcd_slow(deno1,determinant);
    if (value_notone_p(gcd)){
        value_division(deno1,gcd);
        value_division(determinant,gcd);
    }
    if (value_neg_p(determinant)){
        value_oppose(deno1); 
        value_oppose(determinant);
    }
    DENOMINATOR(inv_h) = determinant;
    /* calcul des sous_determinants des Aii */
    for (i=1; i<=n; i++){
        sous_determinant = VALUE_ONE;
        for (j=1; j<=n; j++)
            if (j != i) {
                a = ACCESS(h,n,j,j);
                value_product(sous_determinant,a) ;
            }
        ACCESS(inv_h,n,i,i) = value_mult(sous_determinant,deno1);
    }
    /* calcul des sous_determinants des Aij (i<j) */
    if (infer) {
        for (i=1; i<=n; i++)
            for(j=i+1; j<=n;j++){
                matrice_sous_determinant(h,n,i,j,aij);
                assert(aij[0] == VALUE_ONE);
                ACCESS(inv_h,n,j,i) = value_mult(aij[1],deno1);
            }
    }
    else {
        for (i=1; i<=n; i++)
            for(j=1; j<i; j++){
                matrice_sous_determinant(h,n,i,j,aij);
                assert(aij[0] == VALUE_ONE);
                ACCESS(inv_h,n,j,i) = value_mult(aij[1],deno1);
            }
    }
    
    DENOMINATOR(h) = deno;
}

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().

Here is the call graph for this function:

Here is the caller graph for this function:

matrice_triangulaire_p()

bool matrice_triangulaire_p	(	matrice	Z,
		int	n,
		int	m,
		bool	inferieure
	)

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

Parameters

inferieure

nferieure

Definition at line 394 of file matrice.c.

{
    int i,j;
 
    for (i=1; i <= n; i++)
        if(inferieure) {
            for (j=i+1; j <= m; j++)
                if(value_notzero_p(ACCESS(Z,n,i,j)))
                    return(false);
        }
        else
            for (j=1; j <= i-1; j++)
                if(value_notzero_p(ACCESS(Z,n,i,j)))
                    return(false);
    return(true);
}

References ACCESS, and value_notzero_p.

Referenced by matrice_triangulaire_inversion(), and matrice_triangulaire_unimodulaire_p().

Here is the caller graph for this function:

matrice_triangulaire_unimodulaire_p()

bool matrice_triangulaire_unimodulaire_p	(	matrice	Z,
		int	n,
		bool	inferieure
	)

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

Parameters

inferieure

nferieure

Definition at line 434 of file matrice.c.

{
    bool triangulaire;
    int i;
    triangulaire = matrice_triangulaire_p(Z,n,n,inferieure);
    if (triangulaire == false)
        return(false);
    else{
        for(i=1; i<=n; i++)
            if (value_notone_p(ACCESS(Z,n,i,i)))
                return(false);
        return(true);
    }
}           

References ACCESS, matrice_triangulaire_p(), and value_notone_p.

Referenced by matrice_unimodulaire_inversion(), and matrice_unimodulaire_triangulaire_inversion().

Here is the call graph for this function:

Here is the caller graph for this function:

matrice_unimodulaire_inversion()

void matrice_unimodulaire_inversion	(	matrice	u,
		matrice	inv_u,
		int	n
	)

void matrice_unimodulaire_inversion(matrice u, matrice inv_u, int n) calcul de l'inversion de la matrice unimodulaire.

algorithme :

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

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

ne utilise pas

test

Parameters

inv_u

nv_u

Definition at line 267 of file inversion.c.

{
    matrice p = matrice_new(n,n);
    matrice q = matrice_new(n,n);
    matrice h_u = matrice_new(n,n);
    matrice inv_h_u = matrice_new(n,n);
    matrice temp = matrice_new(n,n);
    Value det_p,det_q;  /* ne utilise pas */
   
    /* test */
    assert(value_one_p(DENOMINATOR(u)));
 
    matrice_hermite(u,n,n,p,h_u,q,&det_p,&det_q);
    assert(matrice_triangulaire_unimodulaire_p(h_u,n,true));
    matrice_unimodulaire_triangulaire_inversion(h_u,inv_h_u,n,true);
    matrice_multiply(q,inv_h_u,temp,n,n,n);
    matrice_multiply(temp,p,inv_u,n,n,n);
}

References assert, DENOMINATOR, matrice_hermite(), matrice_multiply(), matrice_new, matrice_triangulaire_unimodulaire_p(), matrice_unimodulaire_triangulaire_inversion(), and value_one_p.

Here is the call graph for this function:

matrice_unimodulaire_triangulaire_inversion()

void matrice_unimodulaire_triangulaire_inversion	(	matrice	u,
		matrice	inv_u,
		int	n,
		bool	infer
	)

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

Parameters

inv_u	nv_u
infer	nfer

Definition at line 54 of file inversion.c.

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

References ACCESS, assert, matrice_identite(), matrice_soustraction_colonne(), matrice_triangulaire_unimodulaire_p(), value_notzero_p, and x.

Referenced by matrice_unimodulaire_inversion().

Here is the call graph for this function:

Here is the caller graph for this function: