Matrixmultiplikation in Java

1. Übersicht

In diesem Tutorial sehen wir uns an, wie wir zwei Matrizen in Java multiplizieren können.

Da das Matrixkonzept nicht nativ in der Sprache vorhanden ist, werden wir es selbst implementieren und mit einigen Bibliotheken zusammenarbeiten, um zu sehen, wie sie mit der Multiplikation von Matrizen umgehen.

Am Ende werden wir ein kleines Benchmarking der verschiedenen Lösungen durchführen, die wir untersucht haben, um die schnellste zu ermitteln.

2. Das Beispiel

Beginnen wir mit der Erstellung eines Beispiels, auf das wir in diesem Tutorial verweisen können.

Zunächst stellen wir uns eine 3 × 2-Matrix vor:

Stellen wir uns nun eine zweite Matrix vor, diesmal zwei Zeilen mal vier Spalten:

Dann die Multiplikation der ersten Matrix mit der zweiten Matrix, was zu einer 3 × 4-Matrix führt:

Zur Erinnerung: Dieses Ergebnis wird erhalten, indem jede Zelle der resultierenden Matrix mit der folgenden Formel berechnet wird :

Dabei ist r die Anzahl der Zeilen der Matrix A , c die Anzahl der Spalten der Matrix B und n die Anzahl der Spalten der Matrix A , die mit der Anzahl der Zeilen der Matrix B übereinstimmen müssen .

3. Matrixmultiplikation

3.1. Eigene Implementierung

Beginnen wir mit unserer eigenen Implementierung von Matrizen.

Wir werden es einfach halten und nur zweidimensionale verwenden Doppel Arrays :

double[][] firstMatrix = { new double[]{1d, 5d}, new double[]{2d, 3d}, new double[]{1d, 7d} }; double[][] secondMatrix = { new double[]{1d, 2d, 3d, 7d}, new double[]{5d, 2d, 8d, 1d} };

Das sind die beiden Matrizen unseres Beispiels. Lassen Sie uns diejenige erstellen, die als Ergebnis ihrer Multiplikation erwartet wird:

double[][] expected = { new double[]{26d, 12d, 43d, 12d}, new double[]{17d, 10d, 30d, 17d}, new double[]{36d, 16d, 59d, 14d} };

Nachdem alles eingerichtet ist, implementieren wir den Multiplikationsalgorithmus. Wir erstellen zuerst ein leeres Ergebnisarray und durchlaufen seine Zellen, um den erwarteten Wert in jedem von ihnen zu speichern:

double[][] multiplyMatrices(double[][] firstMatrix, double[][] secondMatrix) { double[][] result = new double[firstMatrix.length][secondMatrix[0].length]; for (int row = 0; row < result.length; row++) { for (int col = 0; col < result[row].length; col++) { result[row][col] = multiplyMatricesCell(firstMatrix, secondMatrix, row, col); } } return result; }

Lassen Sie uns abschließend die Berechnung einer einzelnen Zelle implementieren. Um dies zu erreichen, verwenden wir die Formel, die weiter oben in der Darstellung des Beispiels gezeigt wurde :

double multiplyMatricesCell(double[][] firstMatrix, double[][] secondMatrix, int row, int col) { double cell = 0; for (int i = 0; i < secondMatrix.length; i++) { cell += firstMatrix[row][i] * secondMatrix[i][col]; } return cell; }

Überprüfen wir abschließend, ob das Ergebnis des Algorithmus mit unserem erwarteten Ergebnis übereinstimmt:

double[][] actual = multiplyMatrices(firstMatrix, secondMatrix); assertThat(actual).isEqualTo(expected);

3.2. EJML

Die erste Bibliothek, die wir uns ansehen werden, ist EJML, was für Efficient Java Matrix Library steht. Zum Zeitpunkt des Schreibens dieses Tutorials ist es eine der zuletzt aktualisierten Java-Matrixbibliotheken . Ziel ist es, hinsichtlich Berechnung und Speichernutzung so effizient wie möglich zu sein.

Wir müssen die Abhängigkeit zur Bibliothek in unserer pom.xml hinzufügen :

 org.ejml ejml-all 0.38 

Wir werden so ziemlich das gleiche Muster wie zuvor verwenden: Erstellen Sie zwei Matrizen gemäß unserem Beispiel und überprüfen Sie, ob das Ergebnis ihrer Multiplikation das zuvor berechnete ist.

Erstellen wir also unsere Matrizen mit EJML. Um dies zu erreichen, verwenden wir die von der Bibliothek angebotene SimpleMatrix- Klasse .

Es kann ein zweidimensionales Doppelarray als Eingabe für seinen Konstruktor verwenden:

SimpleMatrix firstMatrix = new SimpleMatrix( new double[][] { new double[] {1d, 5d}, new double[] {2d, 3d}, new double[] {1d ,7d} } ); SimpleMatrix secondMatrix = new SimpleMatrix( new double[][] { new double[] {1d, 2d, 3d, 7d}, new double[] {5d, 2d, 8d, 1d} } );

Und jetzt definieren wir unsere erwartete Matrix für die Multiplikation:

SimpleMatrix expected = new SimpleMatrix( new double[][] { new double[] {26d, 12d, 43d, 12d}, new double[] {17d, 10d, 30d, 17d}, new double[] {36d, 16d, 59d, 14d} } );

Nachdem wir alle eingerichtet sind, wollen wir sehen, wie die beiden Matrizen miteinander multipliziert werden. Die SimpleMatrix- Klasse bietet eine mult () -Methode, die eine andere SimpleMatrix als Parameter verwendet und die Multiplikation der beiden Matrizen zurückgibt :

SimpleMatrix actual = firstMatrix.mult(secondMatrix);

Lassen Sie uns überprüfen, ob das erhaltene Ergebnis mit dem erwarteten übereinstimmt.

Da SimpleMatrix die equals () -Methode nicht überschreibt , können wir uns bei der Überprüfung nicht darauf verlassen. Es bietet jedoch eine Alternative: die isIdentical () -Methode, die nicht nur einen anderen Matrixparameter, sondern auch eine doppelte Fehlertoleranz verwendet, um kleine Unterschiede aufgrund doppelter Genauigkeit zu ignorieren:

assertThat(actual).matches(m -> m.isIdentical(expected, 0d));

Damit ist die Multiplikation der Matrizen mit der EJML-Bibliothek abgeschlossen. Mal sehen, was die anderen anbieten.

3.3. ND4J

Probieren wir jetzt die ND4J-Bibliothek aus. ND4J ist eine Berechnungsbibliothek und Teil des Projekts deeplearning4j. ND4J bietet unter anderem Funktionen zur Matrixberechnung.

Zunächst müssen wir die Bibliotheksabhängigkeit ermitteln:

 org.nd4j nd4j-native 1.0.0-beta4 

Beachten Sie, dass wir hier die Beta-Version verwenden, da es einige Fehler mit der GA-Version zu geben scheint.

For the sake of brevity, we won't rewrite the two dimensions double arrays and just focus on how they are used with each library. Thus, with ND4J, we must create an INDArray. In order to do that, we'll call the Nd4j.create() factory method and pass it a double array representing our matrix:

INDArray matrix = Nd4j.create(/* a two dimensions double array */);

As in the previous section, we'll create three matrices: the two we're going to multiply together and the one being the expected result.

After that, we want to actually do the multiplication between the first two matrices using the INDArray.mmul() method:

INDArray actual = firstMatrix.mmul(secondMatrix);

Then, we check again that the actual result matches the expected one. This time we can rely on an equality check:

assertThat(actual).isEqualTo(expected);

This demonstrates how the ND4J library can be used to do matrix calculations.

3.4. Apache Commons

Let's now talk about the Apache Commons Math3 module, which provides us with mathematic computations including matrices manipulations.

Again, we'll have to specify the dependency in our pom.xml:

 org.apache.commons commons-math3 3.6.1 

Once set up, we can use the RealMatrix interface and its Array2DRowRealMatrix implementation to create our usual matrices. The constructor of the implementation class takes a two-dimensional double array as its parameter:

RealMatrix matrix = new Array2DRowRealMatrix(/* a two dimensions double array */);

As for matrices multiplication, the RealMatrix interface offers a multiply() method taking another RealMatrix parameter:

RealMatrix actual = firstMatrix.multiply(secondMatrix);

We can finally verify that the result is equal to what we're expecting:

assertThat(actual).isEqualTo(expected);

Let's see the next library!

3.5. LA4J

This one's named LA4J, which stands for Linear Algebra for Java.

Let's add the dependency for this one as well:

 org.la4j la4j 0.6.0 

Now, LA4J works pretty much like the other libraries. It offers a Matrix interface with a Basic2DMatrix implementation that takes a two-dimensional double array as input:

Matrix matrix = new Basic2DMatrix(/* a two dimensions double array */);

As in the Apache Commons Math3 module, the multiplication method is multiply() and takes another Matrix as its parameter:

Matrix actual = firstMatrix.multiply(secondMatrix);

Once again, we can check that the result matches our expectations:

assertThat(actual).isEqualTo(expected);

Let's now have a look at our last library: Colt.

3.6. Colt

Colt is a library developed by CERN. It provides features enabling high performance scientific and technical computing.

As with the previous libraries, we must get the right dependency:

 colt colt 1.2.0 

In order to create matrices with Colt, we must make use of the DoubleFactory2D class. It comes with three factory instances: dense, sparse and rowCompressed. Each is optimized to create the matching kind of matrix.

For our purpose, we'll use the dense instance. This time, the method to call is make() and it takes a two-dimensional double array again, producing a DoubleMatrix2D object:

DoubleMatrix2D matrix = doubleFactory2D.make(/* a two dimensions double array */);

Once our matrices are instantiated, we'll want to multiply them. This time, there's no method on the matrix object to do that. We've got to create an instance of the Algebra class which has a mult() method taking two matrices for parameters:

Algebra algebra = new Algebra(); DoubleMatrix2D actual = algebra.mult(firstMatrix, secondMatrix);

Then, we can compare the actual result to the expected one:

assertThat(actual).isEqualTo(expected);

4. Benchmarking

Now that we're done with exploring the different possibilities of matrix multiplication, let's check which are the most performant.

4.1. Small Matrices

Let's begin with small matrices. Here, a 3×2 and a 2×4 matrices.

In order to implement the performance test, we'll use the JMH benchmarking library. Let's configure a benchmarking class with the following options:

public static void main(String[] args) throws Exception { Options opt = new OptionsBuilder() .include(MatrixMultiplicationBenchmarking.class.getSimpleName()) .mode(Mode.AverageTime) .forks(2) .warmupIterations(5) .measurementIterations(10) .timeUnit(TimeUnit.MICROSECONDS) .build(); new Runner(opt).run(); }

This way, JMH will make two full runs for each method annotated with @Benchmark, each with five warmup iterations (not taken into the average computation) and ten measurement ones. As for the measurements, it'll gather the average time of execution of the different libraries, in microseconds.

We then have to create a state object containing our arrays:

@State(Scope.Benchmark) public class MatrixProvider { private double[][] firstMatrix; private double[][] secondMatrix; public MatrixProvider() { firstMatrix = new double[][] { new double[] {1d, 5d}, new double[] {2d, 3d}, new double[] {1d ,7d} }; secondMatrix = new double[][] { new double[] {1d, 2d, 3d, 7d}, new double[] {5d, 2d, 8d, 1d} }; } }

That way, we make sure arrays initialization is not part of the benchmarking. After that, we still have to create methods that do the matrices multiplication, using the MatrixProvider object as the data source. We won't repeat the code here as we saw each library earlier.

Finally, we'll run the benchmarking process using our main method. This gives us the following result:

Benchmark Mode Cnt Score Error Units MatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication avgt 20 1,008 ± 0,032 us/op MatrixMultiplicationBenchmarking.coltMatrixMultiplication avgt 20 0,219 ± 0,014 us/op MatrixMultiplicationBenchmarking.ejmlMatrixMultiplication avgt 20 0,226 ± 0,013 us/op MatrixMultiplicationBenchmarking.homemadeMatrixMultiplication avgt 20 0,389 ± 0,045 us/op MatrixMultiplicationBenchmarking.la4jMatrixMultiplication avgt 20 0,427 ± 0,016 us/op MatrixMultiplicationBenchmarking.nd4jMatrixMultiplication avgt 20 12,670 ± 2,582 us/op

As we can see, EJML and Colt are performing really well with about a fifth of a microsecond per operation, where ND4j is less performant with a bit more than ten microseconds per operation. The other libraries have performances situated in between.

Also, it's worth noting that when increasing the number of warmup iterations from 5 to 10, performance is increasing for all the libraries.

4.2. Large Matrices

Now, what happens if we take larger matrices, like 3000×3000? To check what happens, let's first create another state class providing generated matrices of that size:

@State(Scope.Benchmark) public class BigMatrixProvider { private double[][] firstMatrix; private double[][] secondMatrix; public BigMatrixProvider() {} @Setup public void setup(BenchmarkParams parameters) { firstMatrix = createMatrix(); secondMatrix = createMatrix(); } private double[][] createMatrix() { Random random = new Random(); double[][] result = new double[3000][3000]; for (int row = 0; row < result.length; row++) { for (int col = 0; col < result[row].length; col++) { result[row][col] = random.nextDouble(); } } return result; } }

As we can see, we'll create 3000×3000 two-dimensions double arrays filled with random real numbers.

Let's now create the benchmarking class:

public class BigMatrixMultiplicationBenchmarking { public static void main(String[] args) throws Exception { Map parameters = parseParameters(args); ChainedOptionsBuilder builder = new OptionsBuilder() .include(BigMatrixMultiplicationBenchmarking.class.getSimpleName()) .mode(Mode.AverageTime) .forks(2) .warmupIterations(10) .measurementIterations(10) .timeUnit(TimeUnit.SECONDS); new Runner(builder.build()).run(); } @Benchmark public Object homemadeMatrixMultiplication(BigMatrixProvider matrixProvider) { return HomemadeMatrix .multiplyMatrices(matrixProvider.getFirstMatrix(), matrixProvider.getSecondMatrix()); } @Benchmark public Object ejmlMatrixMultiplication(BigMatrixProvider matrixProvider) { SimpleMatrix firstMatrix = new SimpleMatrix(matrixProvider.getFirstMatrix()); SimpleMatrix secondMatrix = new SimpleMatrix(matrixProvider.getSecondMatrix()); return firstMatrix.mult(secondMatrix); } @Benchmark public Object apacheCommonsMatrixMultiplication(BigMatrixProvider matrixProvider) { RealMatrix firstMatrix = new Array2DRowRealMatrix(matrixProvider.getFirstMatrix()); RealMatrix secondMatrix = new Array2DRowRealMatrix(matrixProvider.getSecondMatrix()); return firstMatrix.multiply(secondMatrix); } @Benchmark public Object la4jMatrixMultiplication(BigMatrixProvider matrixProvider) { Matrix firstMatrix = new Basic2DMatrix(matrixProvider.getFirstMatrix()); Matrix secondMatrix = new Basic2DMatrix(matrixProvider.getSecondMatrix()); return firstMatrix.multiply(secondMatrix); } @Benchmark public Object nd4jMatrixMultiplication(BigMatrixProvider matrixProvider) { INDArray firstMatrix = Nd4j.create(matrixProvider.getFirstMatrix()); INDArray secondMatrix = Nd4j.create(matrixProvider.getSecondMatrix()); return firstMatrix.mmul(secondMatrix); } @Benchmark public Object coltMatrixMultiplication(BigMatrixProvider matrixProvider) { DoubleFactory2D doubleFactory2D = DoubleFactory2D.dense; DoubleMatrix2D firstMatrix = doubleFactory2D.make(matrixProvider.getFirstMatrix()); DoubleMatrix2D secondMatrix = doubleFactory2D.make(matrixProvider.getSecondMatrix()); Algebra algebra = new Algebra(); return algebra.mult(firstMatrix, secondMatrix); } }

When we run this benchmarking, we obtain completely different results:

Benchmark Mode Cnt Score Error Units BigMatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication avgt 20 511.140 ± 13.535 s/op BigMatrixMultiplicationBenchmarking.coltMatrixMultiplication avgt 20 197.914 ± 2.453 s/op BigMatrixMultiplicationBenchmarking.ejmlMatrixMultiplication avgt 20 25.830 ± 0.059 s/op BigMatrixMultiplicationBenchmarking.homemadeMatrixMultiplication avgt 20 497.493 ± 2.121 s/op BigMatrixMultiplicationBenchmarking.la4jMatrixMultiplication avgt 20 35.523 ± 0.102 s/op BigMatrixMultiplicationBenchmarking.nd4jMatrixMultiplication avgt 20 0.548 ± 0.006 s/op

As we can see, the homemade implementations and the Apache library are now way worse than before, taking nearly 10 minutes to perform the multiplication of the two matrices.

Colt is taking a bit more than 3 minutes, which is better but still very long. EJML and LA4J are performing pretty well as they run in nearly 30 seconds. But, it's ND4J which wins this benchmarking performing in under a second on a CPU backend.

4.3. Analysis

That shows us that the benchmarking results really depend on the matrices' characteristics and therefore it's tricky to point out a single winner.

5. Conclusion

In this article, we've learned how to multiply matrices in Java, either by ourselves or with external libraries. After exploring all solutions, we did a benchmark of all of them and saw that, except for ND4J, they all performed pretty well on small matrices. On the other hand, on larger matrices, ND4J is taking the lead.

As usual, the full code for this article can be found over on GitHub.