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”.