sous-matrice.c File Reference

#include <stdio.h>
#include "boolean.h"
#include "arithmetique.h"
#include "matrice.h"

Include dependency graph for sous-matrice.c:

Go to the source code of this file.

Macros
#define	MALLOC(s, t, f)   malloc(s)
	package matrice More...
#define	FREE(s, t, f)   free(s)

Functions
int	mat_lig_nnul (matrice MAT, int n, int m, int level)
	int mat_lig_nnul(matrice MAT, int n, int m, int level): Recherche de la premiere ligne non nulle de la la sous-matrice MAT(level+1 ..n, level+1 ..m) More...
void	mat_perm_col (matrice MAT, int n __attribute__((unused)), int m __attribute__((unused)), int k, int level)
	void mat_perm_col(matrice MAT, int n, int m, 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	mat_perm_lig (matrice MAT, int n __attribute__((unused)), int m __attribute__((unused)), int k, int level)
	void mat_perm_lig(matrice MAT, int n, int m, 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	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. More...
void	mat_maj_col (matrice A, int n __attribute__((unused)), int m __attribute__((unused)), matrice P, int level)
	void mat_maj_col(matrice A, int n, int m, 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	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 More...
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) More...
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. More...
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. More...
int	mat_col_el (matrice MAT, int n, int m __attribute__((unused)), int level)
	int mat_col_el(matrice MAT, int n, int m, 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	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) More...

Macro Definition Documentation

FREE

#define FREE	(		s,
			t,
			f
	)		free(s)

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

MALLOC

#define MALLOC	(		s,
			t,
			f
	)		malloc(s)

package matrice

ce fichier comporte les routines traitant des sous-matrices inferieures droites; ces routines traitent la matrice toute entiere si le parametre level vaut 0; les routines sur les matrices completes se trouvent dans le fichier matrice.c

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

Function Documentation

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	MAT,
		int	n,
		int m	__attribute__(unused),
		int	level
	)

int mat_col_el(matrice MAT, int n, int m, 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

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

{
    int i;
    int i_min=0;
 
    for(i = level+2; i <= n && value_zero_p(ACCESS(MAT,n,i,level+1)); i++);
    if (i<n+1)
        i_min = i-1;
    return (i_min);
}

References ACCESS, level, and value_zero_p.

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
	)

int mat_lig_nnul(matrice MAT, int n, int m, int level): Recherche de la premiere ligne non nulle de la la sous-matrice MAT(level+1 ..n, level+1 ..m)

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	A,
		int n	__attribute__(unused),
		int m	__attribute__(unused),
		matrice	P,
		int	level
	)

void mat_maj_col(matrice A, int n, int m, 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

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

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

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

Here is the call graph for this function:

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	MAT,
		int n	__attribute__(unused),
		int m	__attribute__(unused),
		int	k,
		int	level
	)

void mat_perm_col(matrice MAT, int n, int m, 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

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

{
    int i,j;
 
    matrice_nulle(MAT,n,n);
    if (level > 0) {
        for (i=1;i<=level; i++)
            ACCESS(MAT,n,i,i) = VALUE_ONE;
    }
 
    for (i=1+level,j=k; i<=n; i++,j++)
    {
        if (j == n+1) j = 1 + level;
        ACCESS(MAT,n,i,j)=VALUE_ONE;
    }
}

References ACCESS, level, matrice_nulle(), and VALUE_ONE.

Here is the call graph for this function:

mat_perm_lig()

void mat_perm_lig	(	matrice	MAT,
		int n	__attribute__(unused),
		int m	__attribute__(unused),
		int	k,
		int	level
	)

void mat_perm_lig(matrice MAT, int n, int m, 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

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

{
    int i,j;
 
    matrice_nulle(MAT,m,m);
    if(level > 0) {
        for (i = 1; i <= level;i++)
            ACCESS(MAT,m,i,i) = VALUE_ONE;
    }
 
    for(j=1,i=k-level; j <= m - level; j++,i++) {
        if(i == m-level+1)
            i = 1;
        ACC_ELEM(MAT,m,i,j,level) = VALUE_ONE;
    }
}

References ACC_ELEM, ACCESS, level, matrice_nulle(), and VALUE_ONE.

Here is the call graph for this function:

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.