API per applicazioni

VI parte: Linear Algebra for Javadi

la4j, sigla che sta per Linear Algebra for Java, è una libreria Java che può risultare molto utile per coloro che debbano svolgere calcoli, come matematici e statistici, vista l'ampia gamma di funzioni su matrici e vettori che mette a disposizione.

Introduzione a la4j

la4j è una libreria Java 100% open source che fornisce strumenti base per l'algebra lineare come matrici e vettori corredati dei loro algoritmi. la4j è stato inizialmente progettata per essere strumento leggero e semplice per gli sviluppatori Java  e per matematici e statistici appassionati di programmazione. È stato avviato come progetto studentesco e trasformato in uno dei pacchetti Java più popolari per le matrici e vettori .

Caratteristiche principali

La libreria può essere scaricata dal suo sito ufficiale [1]. Le caratteristiche principali di la4j sono:

  • grandi prestazioni contornate da un buon design;
  • nessuna dipendenza da JAR e libreria dalle dimensioni contenute;
  • Object Oriented / API funzionale;
  • supporto di matrici "sparse" (CRS , CCS) e "dense" (array 1D / 2D);
  • algoritmi per i sistemi lineari (gaussiana, jacobiano, zeidel, radice quadrata, sweep e altro);
  • matrici di decomposizione (autovalori/autovettori, SVD, QR, LU, di Cholesky e altri);
  • supporto MatrixMarket / CSV IO per matrici e vettori.

Qualche definizione matematica

Vediamo qualche definizione relativa alla matematica. In analisi numerica abbiamo matrici dense e matrici sparse. La matrice densa è una matrice con "pochi" elementi pari a 0; la matrice sparsa è quella i cui valori sono quasi tutti uguali a 0.

Tipicamente, la struttura dati di una matrice è un array bidimensionale: ogni elemento dell'array rappresenta il generico elemento ai,j, a cui si può avere accesso tramite i due indici i e j. Per una matrice m x n deve essere disponibile almeno il minimo quantitativo di memoria necessario a immagazzinare gli (m x n) valori della matrice [2].

Matrice sparsa

Molti, se non tutti i valori di una matrice sparsa sono pari a 0. Il principio di base che si segue per memorizzare una matrice sparsa è  il seguente: invece di salvare tutti i valori, si salvano soltanto quelli diversi da zero. Sulla base della quantità e della distribuzione dei valori diversi da 0, è possibile utilizzare svariate strutture dati, che si allontanano dall'approccio usuale. Ciò consente di ottenere condiderevoli risparmi in termini di memoria.

Un esempio di formato per memorizzare matrici sparse è il (vecchio) Yale Sparse Matrix Format, che memorizza una matrice sparsa m x n, M, in una riga usando tre array monodimensionali. Poniamo che NNZ sia il numero di valori diversi da zero di M. Il primo array è A, di lunghezza NNZ, e memorizza tutti i valori diversi da zero di M, ordinati da sinistra a destra e dall'alto verso il basso. Il secondo array è IA, che è lungo m+1 (ossia un valore per riga, più uno). IA(i) contiene l'indice del primo elemento di A diverso da zero della riga i-esima. La lunghezza della riga i è determinata da IA(i+1) - IA(i), per questo motivo IA deve essere di lunghezza m+1. Il terzo array, JA, contiene l'indice della colonna di ciascun elemento di A, quindi JA è lunga NNZ [3].

Ad esempio, la matrice

[ 1 2 0 0 ]
[ 0 3 9 0 ]
[ 0 1 4 0 ]

è una matrice 3 x 4  con 6 elementi diversi da 0, per cui

A  = [ 1 2 3 9 1 4 ]
IA = [ 1 3 5 7 ]
JA = [ 1 2 2 3 2 3 ]

Uso pratico della libreria

Riportiamo di seguito una serie di esempi che illustrano le funzionalità e le caratteristiche della libreria. I commenti nel codice dovrebbero fornire una spiegazione piuttosto immediata, in modo tale che il programmatore possa impiegare le funzioni più comuni di la4j.

Matrice "densa" da array di double

// Creo matrice bidimensionale
Matrix a = new Basic2DMatrix(new double[][]{
  { 1.0, 2.0, 3.0 },
  { 4.0, 5.0, 6.0 },
  { 7.0, 8.0, 9.0 }
});
// Matrice unidimensionale
Matrix b = new Basic1DMatrix(new double[][]{
  { 1.0, 2.0, 3.0 },
  { 4.0, 5.0, 6.0 },
  { 7.0, 8.0, 9.0 }
});

Importare matrice "densa" da file .csv

Matrix a = new Basic2DMatrix(Matrices.asSymbolSeparatedSource( new FileInputStream("matrix.csv")));

Importare matrice "densa" da file MatrixMarket (.mm)

Matrix a = new Basic1DMatrix(Matrices.asMatrixMarketSource( new FileInputStream("matrix.mm")));

Matrice "sparsa" da array di double

// Matrice ‘Compressed Row Storage' (CRS)
Matrix a = new CRSMatrix(new double[][]{
  { 1.0, 0.0, 3.0 },
  { 0.0, 5.0, 0.0 },
  { 7.0, 0.0, 9.0 }
});
// Matrice  ‘Compressed Column Storage' (CCS)
Matrix b = new CCSMatrix(new double[][]{
  { 0.0, 2.0, 0.0 },
  { 4.0, 5.0, 6.0 },
  { 0.0, 0.0, 9.0 }
});

Importare matrice "sparsa" da file .csv

Matrix a = new CRSMatrix(Matrices.asSymbolSeparatedSource(
    new FileInputStream("matrix.csv")));

Importare matrice "sparsa" da file MatrixMarket (.mm)

Matrix a = new CCSMatrix(Matrices.asMatrixMarketSource( 
    new FileInputStream("matrix.mm")));

Vettore "denso" o "sparso" da array di double

// Definisco un vettore
Vector a = new BasicVector(new double[]{ 1.0, 2.0, 3.0 });
// Un vettore compresso che utilizza 
// matrice bidimensionele come rappresentazione interna
Vector b = new CompressedVector(new double[] { 0.0, 2.0, 0.0 });

Importare vettore "denso" o "sparso" da file .csv

Vector a = new BasicVector(Vectors.asSymbolSeparatedSource( 
    new FileInputStream("vector.csv")));
Vector b = new CompressedVector(Vectors.asSymbolSeparatedSource( 
    new FileInputStream("vector.csv")));

Importare vettore "denso" da file MatrixMarket (.mm)

Vector a = new BasicVector(Vectors.asMatrixMarketSource(
    new FileInputStream("vector.mm")));

Importare vettore "sparso" da file MatrixMarket (.mm)

Vector a = new CompressedVector(Vectors.asMatrixMarketSource( 
    new FileInputStream("vector.mm")));

Convertire Matrice in Vettore

// Definisco una matrice ‘Compressed Row Storage' 
Matrix a = new CRSMatrix(new double[][]{
  { 1.0, 0.0, 3.0 },
  { 0.0, 5.0, 0.0 },
  { 7.0, 0.0, 9.0 }
});
// Prendo la prima riga della matrice come vettore sparso
Vector b = a.toRowVector();
// Prendo la prima colonna  della matrice come vettore sparso
Vector c = a.toColumnVector();

Convertire Vettore in Matrice

// Definisco un BasicVector
Vector a = new BasicVector(new double[]{ 1.0, 2.0, 3.0 });
// Prendo il vettore come prima riga della matrice densa
Matrix b = a.toRowMatrix();
// Prendo il vettore come prima colonna della matrice densa
Matrix c = a.toColumnMatrix();

Convertire Matrice "densa" in "sparsa"

// Matrice unidemensionale
Matrix a = new Basic1DMatrix(new double[][]{
  { 1.0, 2.0, 3.0 },
  { 4.0, 5.0, 6.0 },
  { 7.0, 8.0, 9.0 }
});
// Converto una Basic1DMatrix in CRSMatrix
Matrix b = a.copy(LinearAlgebra.CRS_FACTORY);

Convertire Matrice "sparsa" in "densa"

// Creo una matrice  ‘Compressed Column Storage' 
Matrix a = new CCSMatrix(new double[][]{
  { 0.0, 2.0, 0.0 },
  { 4.0, 5.0, 6.0 },
  { 0.0, 0.0, 9.0 }
});
// Converto CCSMatrix in Basic2DMatrix
Matrix b = a.copy(LinearAlgebra.BASIC2D_FACTORY);

Conversioni di vettori

// Definisco un semplice vettore
Vector a = new BasicVector(new double[]{ 1.0, 2.0, 3.0 });
// Converto il BasicVector in CompressedVector
Vector b = c.copy(LinearAlgebra.SPARSE_FACTORY);
// Converto il CompressedVector in BasicVector
Vector c = b.copy(LinearAlgebra.DENSE_FACTORY);

Trasformare una matrice usando funzioni predefinite

// Matrice 
Matrix a = new Basic2DMatrix(new double[][] {
   { 1.0, 2.0, 3.0 },
   { 4.0, 5.0, 6.0 },
   { 7.0, 8.0. 9.0 }
});
// Moltiplico ogni elemento della matrice per 10
Matrix b = a.transform(Matrices.asMulFunction(10.0));
// Incremento ogni elemento della matrice di 1
Matrix c = b.transform(Matrices.INC_FUNCTION);

Trasformare una matrice facendo override di funzioni già definite

//Definisco Matrice a
Matrix a = new CRSMatrix(new double[][] {
   { 1.0, 0.0, 0.0 },
   { 4.0, 5.0, 6.0 },
   { 0.0, 0.0. 9.0 }
});
// Voglio ottenere solo la diagonal della Matrice a
Matrix b = a.transform(new MatrixFunction() {
  @Override
  public double evaluate(int i, int j, double value) {
    return (i == j) ? value : 0.0;
  }
});

Prodotto tra Matrici

// Definisco matrice A
Matrix a = new CCSMatrix(new double[][] {
   { 1.0, 2.0, 3.0 },
   { 4.0, 0.0, 6.0 },
   { 7.0, 0.0. 9.0 }
});
// Definisco Matrice B
Matrix b = new Basic2DMatrix(new double[][] {
   { 1.0, 2.0, 3.0 },
   { 4.0, 5.0, 6.0 },
   { 7.0, 8.0. 9.0 }
});
// Prodotto
Matrix c = a.multiply(b);

Prodotto tra Matrice e Vettore

// Matrice A
Matrix a = new CRSMatrix(new double[][] {
   { 1.0, 2.0, 3.0 },
   { 4.0, 0.0, 6.0 },
   { 7.0, 0.0. 9.0 }
});
// Vettore sparso b
Vector b = new CompressedVector(new double[] { 1.0, 0.0, 3.0 });
// Prodotto
Vector c = a.multiply(b);

Prodotto tra Vettore e Matrice

// Vettore denso a
Vector a = new BasicVector(new double[] { 1.0, 0.0, 3.0 });
// Matrice b
Matrix b = new CCSMatrix(new double[][] {
   { 1.0, 2.0, 3.0 },
   { 4.0, 0.0, 6.0 },
   { 7.0, 0.0. 9.0 }
});
//Prodotto
Vector c = a.multiply(b);

Calcolo del prodotto  di due vettori

Vector a = new BasicVector(new double[]{ 1.0, 2.0, 3.0 });
Vector b = new BasicVector(new double[]{ 4.0, 5.0, 6.0 });
double d = a.innerProduct(b); // 1.0*4.0 + 2.0*5.0 + 3.0*6.0 = 32

Calcolo del prodotto di Hadamar di due vettori

Vector a = new BasicVector(new double[]{ 1.0, 2.0, 3.0 });
Vector b = new BasicVector(new double[]{ 4.0, 5.0, 6.0 });
Vector c = a.hadamardProduct(b); // Vector { 4.0, 10.0, 18.0 }

Calcola prodotto di due vettori , che produce come risultato una matrice.

Vector a = new BasicVector(new double[]{ 1.0, 2.0, 3.0 });
Vector b = new BasicVector(new double[]{ 4.0, 5.0, 6.0 });
/* 
Matrix {
  4.0,  5.0,  6.0
  8.0, 10.0, 12.0
 12.0, 15.0, 18.0
}
*/
Matrix c = a.outerProduct(b);

Matrice inversa

// Matrice A
Matrix a = new Basic2DMatrix(new double[][] {
   { 1.0, 2.0, 3.0 },
   { 4.0, 5.0, 6.0 },
   { 7.0, 8.0. 9.0 }
});
// usiamo il metodo Gauss-Jordan per l'inversione
MatrixInverter inverter = a.withInverter(LinearAlgebra.GAUSS_JORDAN);
// La matrice b sarà densa
Matrix b = inverter.invert(LinearAlgebra.DENSE_FACTORY);

Sistema di equazioni lineari (m = n)

// La matrice ‘a' è un CRS (Compressed Row Storage)
Matrix a = new CRSMatrix(new double[][] {
   { 1.0, 2.0, 3.0 },
   { 4.0, 5.0, 6.0 },
   { 7.0, 8.0. 9.0 }
});
//Il vettore ‘b' è un semplice vettore denso
Vector b = new BasicVector(new double[] {
   1.0, 2.0, 3.0
});
//Useremo il metodo di sostituzione Forward-Back
// che si basa sulla decomposizione LU e può essere utilizzato 
// con i sistemi quadratici
LinearSystemSolver solver 
    = a.withSolver(LinearAlgebra.FORWARD_BACK_SUBSTITUTION);
// Il vettore ‘x' sarà sparso
Vector x = solver.solve(b, LinearAlgebra.SPARSE_FACTORY);

Sistema di equazioni lineari (m > n)

// La matrice ‘a' è  densa e unidimensionale
Matrix a = new Basic1DMatrix(new double[][] {
   {  1.0,  2.0,  3.0 },
   {  4.0,  5.0,  6.0 },
   {  7.0,  8.0.  9.0 },
   { 10.0, 11.0. 12.0 },
   { 13.0, 14.0. 15.0 }
});
//Il vettore ‘b' è un semplice vettore denso
Vector b = new BasicVector(new double[] {
  1.0, 2.0, 3.0, 4.0, 5.0
});
// Useremo il metodo dei quadrati minimi,
// che si basa sulla decomposizione QR e può essere utilizzato 
// con i sistemi sovradeterminati
LinearSystemSolver solver = a.withSolver(LinearAlgebra.LEAST_SQUARES);
// Il vettore ‘x' sarà sparso
Vector x = solver.solve(b, LinearAlgebra.DENSE_FACTORY);

Scomposizione della Matrice (es LU)

// Creiamo una matrice densa unidimensione 
Matrix a = new Basic1DMatrix(new double[][] {
  { 1.0, 2.0, 3.0 },
  { 4.0, 5.0, 6.0 },
  { 7.0, 8.0. 9.0 }
});
// Usiamo la scomposizione LU
MatrixDecompositor decompositor = a.withDecompositor(LinearAlgebra.LU);
// Risultato: L = lup[0], U = lup[1], P = lup[2]
Matrix[] lup = decompositor.decompose(LinearAlgebra.DENSE_FACTORY);

Conclusioni

LA4J si dimostra un buon compagno di viaggio per matematici e statistici che lavorano con I calcoli matematici, soprattutto per la vasta gamma di funzioni su matrici e vettori che ha al suo interno. Le alternative a questa libreria possono essere JAMA o Apache Commons Math e partire da la4j può servire anche a fare delle valutazioni comparative in tal senso.

 

 

 

 

 

 

Riferimenti

[1] Il sito ufficiale di la4j

http://la4j.org

 

[2] Definizioni di matrice

http://it.wikipedia.org/wiki/Glossario_sulle_matrici

 

[3] Matrice sparsa

http://it.wikipedia.org/wiki/Matrice_sparsa

 

Condividi

Pubblicato nel numero
206 maggio 2015
Yuri Cervoni si è laureato alla facoltà di Ingegneria Informatica dell’Università “La Sapienza” di Roma nel maggio 2009 con la tesi: “Implementazione e realizzazione di un metodo per l’animazione dell’algoritmo di Dijkstra”. Dall’Aprile 2009, prima come stagista e poi come sviluppatore software, lavora nella Società degli Studi di Settore. Nel…
Articoli nella stessa serie
Ti potrebbe interessare anche