PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include "linear_assert.h"
#include "boolean.h"
#include "arithmetique.h"
#include "matrix.h"
Go to the source code of this file.
Functions | |
void | matrix_hermite (Pmatrix MAT, Pmatrix P, Pmatrix H, Pmatrix Q, Value *det_p, Value *det_q) |
package matrix More... | |
int | matrix_hermite_rank (Pmatrix a) |
int matrix_hermite_rank(Pmatrix a): rang d'une matrice en forme de hermite More... | |
int | matrix_dim_hermite (Pmatrix H) |
Calcul de la dimension de la matrice de Hermite H. More... | |
Calcul de la dimension de la matrice de Hermite H.
La matrice de Hermite est une matrice tres particuliere, pour laquelle il est tres facile de calculer sa dimension. Elle est egale au nombre de colonnes non nulles de la matrice.
Definition at line 194 of file hermite.c.
References MATRIX_ELEM, MATRIX_NB_COLUMNS, and MATRIX_NB_LINES.
package matrix
hermite.c
void matrix_hermite(matrix MAT, matrix P, matrix H, matrix Q, int *det_p, int *det_q): calcul de la forme reduite de Hermite H de la matrice MAT avec les deux matrices de changement de base unimodulaire P et Q, telles que H = P x MAT x Q et en le meme temp, produit les determinants des P et Q. det_p = |P|, det_q = |Q|.
(c.f. Programmation Lineaire. Theorie et algorithmes. tome 2. M.MINOUX. Dunod (1983)) FI: Quels est l'invariant de l'algorithme? MAT = P x H x Q? FI: Quelle est la norme decroissante? La condition d'arret?
Les parametres de la fonction :
int MAT[n,m]: matrice int n : nombre de lignes de la matrice int m : nombre de colonnes de la matrice int P[n,n] : matrice int H[n,m] : matrice reduite de Hermite int Q[m,m] : matrice int *det_p : determinant de P (nombre de permutation de ligne) int *det_q : determinant de Q (nombre de permutation de colonne)
Les 3 matrices P(nxn), Q(mxm) et H(nxm) doivent etre allouees avant le calcul.
Note: les denominateurs de MAT, P, A et H ne sont pas utilises.
Auteurs: Corinne Ancourt, Yi-qing Yang
Modifications:
indice de la ligne et indice de la colonne correspondant au plus petit element de la sous-matrice traitee
niveau de la sous-matrice traitee
le plus petit element sur la diagonale
la quotient de la division par ALL
if ((n>0) && (m>0) && MAT)
Initialisation des matrices
tant qu'il reste des termes non nuls dans la partie triangulaire superieure de la matrice H,
on cherche le plus petit element de la sous-matrice
la sous-matrice restante est nulle, on a terminee
s'il existe un plus petit element non nul dans la partie triangulaire superieure de la sous-matrice, on amene cet element en haut sur la diagonale. si cet element est deja sur la diagonale, et que tous les termes de la ligne correspondante sont nuls, on effectue les calculs sur la sous-matrice de rang superieur
MAT | AT |
det_p | et_p |
det_q | et_q |
Definition at line 78 of file hermite.c.
References ALL, assert, level, matrix_assign(), matrix_coeff_nnul(), MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_free, matrix_identity(), matrix_line_el(), MATRIX_NB_COLUMNS, MATRIX_NB_LINES, matrix_new(), matrix_nulle(), matrix_subtraction_column(), matrix_swap_columns(), matrix_swap_rows(), Q, SUB_MATRIX_ELEM, value_div, VALUE_ONE, value_one_p, value_uminus, VALUE_ZERO, and x.
Referenced by extract_lattice(), matrix_determinant(), matrix_general_inversion(), matrix_unimodular_inversion(), prepare_reindexing(), and region_sc_minimal().
int matrix_hermite_rank(Pmatrix a): rang d'une matrice en forme de hermite
Definition at line 174 of file hermite.c.
References MATRIX_ELEM, and MATRIX_NB_LINES.
Referenced by matrix_diagonal_inversion(), matrix_general_inversion(), and matrix_triangular_inversion().