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.
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 tempo libero cerca di ampliare le sue conoscenze informatiche partecipando a progetti software presenti su SourceForge.net come “FlaQuizTV” e la documentazione italiana di “Argo UML”.