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.
Macros | |
#define | MALLOC(s, t, f) malloc((unsigned)(s)) |
package matrix More... | |
#define | FREE(s, t, f) free((char *)(s)) |
Functions | |
void | matrix_smith (Pmatrix MAT, Pmatrix P, Pmatrix D, Pmatrix Q) |
void matrix_smith(matrice MAT, matrix P, matrix D, matrix Q): Calcul de la forme reduite de Smith D d'une matrice entiere MAT et des deux matrices de changement de base unimodulaires associees, P et Q. More... | |
int | matrices_to_1D_lattice (Pmatrix A, Pmatrix B, int n, int m, int i, Value *gcd_p, Value *c_p) |
Under the assumption A x = B, A[n,m] and B[n], compute the 1-D lattice for x_i of x[m] as. More... | |
int matrices_to_1D_lattice | ( | Pmatrix | A, |
Pmatrix | B, | ||
int | n, | ||
int | m, | ||
int | i, | ||
Value * | gcd_p, | ||
Value * | c_p | ||
) |
Under the assumption A x = B, A[n,m] and B[n], compute the 1-D lattice for x_i of x[m] as.
x_i = gcd_i lambda + c_i
derived from the parametric solution of the system :
x_i = sum_{k<j<=m} q_{i,j} lambda_j + sum_{1<=j,=k} q_{i,j} y_c_{j}
where k is the rank of matrix A (0<=k<=n, k<=m), lambda_j are the free variables and y_c is the solution of the equations. This leads to:
gcd_i = sum_{k<j<=m} q_{i,j} and c_i = sum_{1<=j,=k} q_{i,j} y_c_{j}
when the system has a least one solution.
To compute Q and y_c, We use D[n,m], the Smith form of A, with D = P A Q and P[n,n] and Q[m,m] unimodular
inv(P) D inv(Q) x = b
inv(P) D y = b => D y = P b => some components of y[m] are constants, y_c[m]
y_c = D'{-1} P b, where D'[min(n,m),min(n,m)] is the top left submatrix of D[n,m]
y = inv(Q) x => x = Q (y_c[1..k],y[k+1..m])
where (a,b) represents s the concatenation of vectors a and b, and k<=min(n,m) the .
c_i = sum_j Q_{i,j} y_c_{j}
gcd = gcd_{j s.t. yc_j = 0} Q_{i,j}
Return false if the system Ax=b has no solution
This implements a partial parametric resolution of A x = B. It might be better from an engineering viewpoint to solve the system fully and then to exploit the equation for x_i.
gcd_p | cd_p |
c_p | _p |
Definition at line 195 of file smith.c.
References B, D, DIVIDE, free(), MATRIX_ELEM, matrix_multiply(), matrix_new(), matrix_smith(), modulo, pgcd, Q, value_mult, VALUE_ONE, VALUE_ZERO, and value_zero_p.
Referenced by transformer_to_1D_lattice().
void matrix_smith(matrice MAT, matrix P, matrix D, matrix Q): Calcul de la forme reduite de Smith D d'une matrice entiere MAT et des deux matrices de changement de base unimodulaires associees, P et Q.
smith.c
D est la forme reduite de Smith, P et Q sont des matrices unimodulaires; telles que D == P x MAT x Q
(c.f. Programmation Lineaire. M.MINOUX. (83))
int MAT[n,m] : matrice int n : nombre de lignes de la matrice MAT int m : nombre de colonnes de la matrice MAT int P[n,n] : matrice int D[n,m] : matrice (quasi-diagonale) reduite de Smith int Q[m,m] : matrice
Les 3 matrices P(nxn), Q(mxm) et D(nxm) doivent etre allouees avant le calcul.
Note: les determinants des matrices MAT, P, Q et D ne sont pas utilises.
le plus petit element sur la diagonale
le rest de la division par ALL
precondition sur les parametres
le transformation n'est pas fini.
MAT | AT |
Definition at line 68 of file smith.c.
References ALL, assert, D, level, matrix_assign(), matrix_col_el(), MATRIX_DENOMINATOR, MATRIX_ELEM, matrix_identity(), matrix_line_el(), matrix_min(), MATRIX_NB_COLUMNS, MATRIX_NB_LINES, matrix_print(), matrix_subtraction_column(), matrix_subtraction_line(), matrix_swap_columns(), matrix_swap_rows(), printf(), Q, SUB_MATRIX_ELEM, value_div, value_one_p, VALUE_ZERO, and x.
Referenced by main(), matrices_to_1D_lattice(), and sc_resol_smith().