Matrixvermenigvuldiging in Java

1. Overzicht

In deze tutorial bekijken we hoe we twee matrices in Java kunnen vermenigvuldigen.

Aangezien het matrixconcept niet standaard in de taal bestaat, zullen we het zelf implementeren en zullen we ook met een paar bibliotheken werken om te zien hoe zij met matricesvermenigvuldiging omgaan.

Uiteindelijk zullen we een kleine benchmarking uitvoeren van de verschillende oplossingen die we hebben onderzocht om de snelste te bepalen.

2. Het voorbeeld

Laten we beginnen met het opzetten van een voorbeeld waarnaar we in deze tutorial kunnen verwijzen.

Eerst stellen we ons een matrix van 3 × 2 voor:

Laten we ons nu een tweede matrix voorstellen, deze keer twee rijen bij vier kolommen:

Vervolgens de vermenigvuldiging van de eerste matrix met de tweede matrix, wat resulteert in een 3 × 4 matrix:

Als een herinnering, dit resultaat wordt verkregen door elke cel van de resulterende matrix met deze formule te berekenen:

Waar r is het aantal rijen matrix EEN, c is het aantal matrixkolommen B en n is het aantal matrixkolommen EEN, die moet overeenkomen met het aantal rijen matrix B.

3. Matrixvermenigvuldiging

3.1. Eigen implementatie

Laten we beginnen met onze eigen implementatie van matrices.

We houden het simpel en rechtvaardig gebruik tweedimensionaal dubbele arrays:

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

Dat zijn de twee matrices van ons voorbeeld. Laten we degene creëren die wordt verwacht als het resultaat van hun vermenigvuldiging:

dubbel [] [] verwacht = {nieuw dubbel [] {26d, 12d, 43d, 12d}, nieuw dubbel [] {17d, 10d, 30d, 17d}, nieuw dubbel [] {36d, 16d, 59d, 14d}} ;

Nu alles is ingesteld, gaan we het vermenigvuldigingsalgoritme implementeren. We maken eerst een lege resultaatmatrix en herhalen de cellen om de verwachte waarde in elk van de cellen op te slaan:

double [] [] multiplyMatrices (double [] [] firstMatrix, double [] [] secondMatrix) {double [] [] resultaat = nieuwe dubbele [firstMatrix.length] [secondMatrix [0] .length]; for (int row = 0; row <result.length; row ++) {for (int col = 0; col <result [row] .length; col ++) {resultaat [rij] [col] = multiplyMatricesCell (firstMatrix, secondMatrix, row , col); }} resultaat retourneren; }

Laten we tot slot de berekening van een enkele cel implementeren. Om dat te bereiken, we zullen de formule gebruiken die eerder in de presentatie van het voorbeeld is getoond:

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

Laten we tot slot controleren of het resultaat van het algoritme overeenkomt met ons verwachte resultaat:

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

3.2. EJML

De eerste bibliotheek die we zullen bekijken, is EJML, wat staat voor Efficient Java Matrix Library. Op het moment dat deze tutorial wordt geschreven, is het een van de meest recent bijgewerkte Java-matrixbibliotheken. Het doel is om zo efficiënt mogelijk te zijn met betrekking tot berekeningen en geheugengebruik.

We zullen de afhankelijkheid moeten toevoegen aan de bibliotheek in ons pom.xml:

 org.ejml ejml-all 0.38 

We zullen vrijwel hetzelfde patroon gebruiken als hiervoor: twee matrices maken volgens ons voorbeeld en controleren of het resultaat van hun vermenigvuldiging het resultaat is dat we eerder hebben berekend.

Laten we dus onze matrices maken met EJML. Om dit te bereiken, we zullen de SimpleMatrix les aangeboden door de bibliotheek.

Het kan een tweedimensionale dimensie hebben dubbele array als invoer voor zijn constructor:

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

En laten we nu onze verwachte matrix voor de vermenigvuldiging definiëren:

SimpleMatrix verwacht = nieuwe SimpleMatrix (nieuwe dubbele [] [] {nieuwe dubbele [] {26d, 12d, 43d, 12d}, nieuwe dubbele [] {17d, 10d, 30d, 17d}, nieuwe dubbele [] {36d, 16d, 59d, 14d}});

Nu we allemaal klaar zijn, gaan we kijken hoe we de twee matrices met elkaar kunnen vermenigvuldigen. De SimpleMatrix klasse biedt een mult () methode een ander nemen SimpleMatrix als parameter en retourneert de vermenigvuldiging van de twee matrices:

SimpleMatrix actueel = firstMatrix.mult (secondMatrix);

Laten we eens kijken of het verkregen resultaat overeenkomt met het verwachte resultaat.

Net zo SimpleMatrix heeft geen voorrang op de is gelijk aan () methode, kunnen we er niet op vertrouwen om de verificatie uit te voeren. Maar, het biedt een alternatief: de isIdentiek () methode die niet alleen een andere matrixparameter nodig heeft, maar ook een dubbele fouttolerantie één om kleine verschillen te negeren vanwege dubbele precisie:

assertThat (feitelijk) .matches (m -> m.isIdentical (verwacht, 0d));

Dat concludeert de vermenigvuldiging van matrices met de EJML-bibliotheek. Laten we eens kijken wat de anderen aanbieden.

3.3. ND4J

Laten we nu de ND4J-bibliotheek proberen. ND4J is een rekenbibliotheek en maakt deel uit van het deeplearning4j-project. ND4J biedt onder andere functies voor matrixberekening.

Allereerst moeten we de bibliotheekafhankelijkheid krijgen:

 org.nd4j nd4j-native 1.0.0-beta4 

Merk op dat we de bètaversie hier gebruiken omdat er enkele bugs lijken te zijn met de GA-release.

Kortheidshalve zullen we de twee dimensies niet herschrijven dubbele arrays en concentreer u gewoon op hoe ze met elke bibliotheek worden gebruikt. Met ND4J moeten we dus een INDArray. Om dat te doen, we noemen de Nd4j.create () fabrieksmethode en geef het een dubbele array die onze matrix vertegenwoordigt:

INDArray-matrix = Nd4j.create (/ * een dubbele array in twee dimensies * /);

Net als in de vorige sectie, zullen we drie matrices maken: de twee die we gaan vermenigvuldigen en de ene is het verwachte resultaat.

Daarna willen we de vermenigvuldiging tussen de eerste twee matrices daadwerkelijk doen met behulp van de INDArray.mmul () methode:

INDArray actueel = firstMatrix.mmul (secondMatrix);

Vervolgens controleren we nogmaals of het daadwerkelijke resultaat overeenkomt met het verwachte resultaat. Dit keer kunnen we rekenen op een gelijkheidscontrole:

assertThat (feitelijk) .isEqualTo (verwacht);

Dit laat zien hoe de ND4J-bibliotheek kan worden gebruikt om matrixberekeningen uit te voeren.

3.4. Apache Commons

Laten we het nu hebben over de Apache Commons Math3-module, die ons voorziet van wiskundige berekeningen, inclusief matrices-manipulaties.

Nogmaals, we zullen de afhankelijkheid moeten specificeren in onze pom.xml:

 org.apache.commons commons-math3 3.6.1 

Eenmaal opgezet, kunnen we gebruiken de RealMatrix interface en zijn Array2DRowRealMatrix implementatie om onze gebruikelijke matrices te creëren. De constructor van de implementatieklasse neemt een tweedimensionaal dubbele array als zijn parameter:

RealMatrix-matrix = nieuwe Array2DRowRealMatrix (/ * een dubbele array in twee dimensies * /);

Wat betreft de vermenigvuldiging van matrices, de RealMatrix interface biedt een vermenigvuldigen() methode een ander nemen RealMatrix parameter:

RealMatrix actueel = firstMatrix.multiply (secondMatrix);

We kunnen eindelijk verifiëren dat het resultaat gelijk is aan wat we verwachten:

assertThat (feitelijk) .isEqualTo (verwacht);

Laten we naar de volgende bibliotheek kijken!

3.5. LA4J

Deze heet LA4J, wat staat voor Linear Algebra for Java.

Laten we ook de afhankelijkheid voor deze toevoegen:

 org.la4j la4j 0.6.0 

Nu werkt LA4J ongeveer zoals de andere bibliotheken. Het biedt een Matrix interface met een Basic2DMatrix implementatie dat vergt een tweedimensionaal dubbele array als invoer:

Matrix matrix = nieuwe Basic2DMatrix (/ * een tweedimensionale dubbele array * /);

Net als in de Apache Commons Math3-module, de vermenigvuldigingsmethode is vermenigvuldigen() en neemt een andere Matrix als parameter:

Matrix actueel = firstMatrix.multiply (secondMatrix);

We kunnen nogmaals controleren of het resultaat overeenkomt met onze verwachtingen:

assertThat (feitelijk) .isEqualTo (verwacht);

Laten we nu eens kijken naar onze laatste bibliotheek: Colt.

3.6. Colt

Colt is een bibliotheek ontwikkeld door CERN. Het biedt functies die wetenschappelijk en technisch computergebruik met hoge prestaties mogelijk maken.

Net als bij de vorige bibliotheken, moeten we de juiste afhankelijkheid krijgen:

 hengstveulen 1.2.0 

Om matrices te maken met Colt, we moeten gebruik maken van de DoubleFactory2D-klasse. Het wordt geleverd met drie fabrieksinstanties: dicht, schaars en row Gecomprimeerd. Elk is geoptimaliseerd om het bijpassende soort matrix te creëren.

Voor ons doel gebruiken we de dicht voorbeeld. Deze keer, de methode om te bellen is maken() en er is een tweedimensionaal voor nodig dubbele reeks nogmaals, het produceren van een DoubleMatrix2D voorwerp:

DoubleMatrix2D matrix = doubleFactory2D.make (/ * een dubbele array in twee dimensies * /);

Zodra onze matrices zijn geïnstantieerd, willen we ze vermenigvuldigen. Deze keer is er geen methode op het matrixobject om dat te doen. We moeten een instantie van het Algebra klasse die een mult () methode twee matrices nemen voor parameters:

Algebra-algebra = nieuwe algebra (); DoubleMatrix2D actueel = algebra.mult (firstMatrix, secondMatrix);

Vervolgens kunnen we het werkelijke resultaat vergelijken met het verwachte:

assertThat (feitelijk) .isEqualTo (verwacht);

4. Benchmarking

Nu we klaar zijn met het onderzoeken van de verschillende mogelijkheden van matrixvermenigvuldiging, gaan we kijken welke het meest performant zijn.

4.1. Kleine matrices

Laten we beginnen met kleine matrices. Hier een 3 × 2 en een 2 × 4 matrices.

Om de prestatietest te implementeren, gebruiken we de JMH benchmarking-bibliotheek. Laten we een benchmarkklasse configureren met de volgende opties:

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

Op deze manier maakt JMH twee volledige runs voor elke methode die is geannoteerd met @Benchmark, elk met vijf opwarmings-iteraties (niet meegenomen in de gemiddelde berekening) en tien meet-iteraties. Wat betreft de metingen, het zal de gemiddelde uitvoeringstijd van de verschillende bibliotheken verzamelen, in microseconden.

We moeten dan een state-object maken dat onze arrays bevat:

@State (Scope.Benchmark) openbare klasse MatrixProvider {privé dubbel [] [] firstMatrix; privé dubbel [] [] secondMatrix; openbare MatrixProvider () {firstMatrix = nieuwe dubbele [] [] {nieuwe dubbele [] {1d, 5d}, nieuwe dubbele [] {2d, 3d}, nieuwe dubbele [] {1d, 7d}}; secondMatrix = nieuwe dubbele [] [] {nieuwe dubbele [] {1d, 2d, 3d, 7d}, nieuwe dubbele [] {5d, 2d, 8d, 1d}}; }}

Op die manier zorgen we ervoor dat de initialisatie van arrays geen deel uitmaakt van de benchmarking. Daarna moeten we nog steeds methoden maken die de matrices vermenigvuldigen, met behulp van de MatrixProvider object als de gegevensbron. We zullen de code hier niet herhalen, omdat we elke bibliotheek eerder hebben gezien.

Ten slotte voeren we het benchmarkingproces uit met behulp van onze hoofd methode. Dit geeft ons het volgende resultaat:

Benchmark Mode Cnt Score Error Units MatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication gem. 20 1,008 ± 0,032 us / op MatrixMultiplicationBenchmarking.coltMatrixMultiplication gem. 20 0,219 ± 0,014 us / op MatrixMultiplication. MatrixMultiplicationBenchmarking.la4jMatrixMultiplication gem. 20 0,427 ± 0,016 us / op MatrixMultiplicationBenchmarking.nd4jMatrixMultiplication gem. 20 12.670 ± 2582 us / op

Zoals we kunnen zien, EJML en Colt presteren erg goed met ongeveer een vijfde van een microseconde per operatie, waar ND4j is minder performant met iets meer dan tien microseconden per operatie. De andere bibliotheken hebben tussendoor optredens.

Het is ook vermeldenswaard dat wanneer het aantal opwarmings-iteraties wordt verhoogd van 5 naar 10, de prestaties voor alle bibliotheken toenemen.

4.2. Grote matrices

Wat gebeurt er als we grotere matrices nemen, zoals 3000 × 3000? Om te controleren wat er gebeurt, gaan we eerst een andere state-klasse maken die gegenereerde matrices van die grootte biedt:

@State (Scope.Benchmark) openbare klasse BigMatrixProvider {privé dubbel [] [] firstMatrix; privé dubbel [] [] secondMatrix; openbare BigMatrixProvider () {} @Setup openbare ongeldige instellingen (BenchmarkParams-parameters) {firstMatrix = createMatrix (); secondMatrix = createMatrix (); } private double [] [] createMatrix () {Random random = nieuwe Random (); dubbel [] [] resultaat = nieuw dubbel [3000] [3000]; for (int row = 0; row <result.length; row ++) {for (int col = 0; col <result [row] .length; col ++) {resultaat [rij] [col] = random.nextDouble (); }} resultaat retourneren; }}

Zoals we kunnen zien, maken we 3000 × 3000 tweedimensionale dubbele arrays gevuld met willekeurige reële getallen.

Laten we nu de benchmarking-klasse maken:

openbare klasse BigMatrixMultiplicationBenchmarking {openbare statische leegte hoofd (String [] args) gooit uitzondering {Mapparameters = parseParameters (args); ChainedOptionsBuilder builder = nieuwe OptionsBuilder () .include (BigMatrixMultiplicationBenchmarking.class.getSimpleName ()) .mode (Mode.AverageTime) .forks (2) .warmupIterations (10) .measurementIterations (10) .timeUnit (TimeONDSUnit.SECUnit (TimeONDS); nieuwe Runner (builder.build ()). run (); } @Benchmark openbaar object homemadeMatrixMultiplication (BigMatrixProvider matrixProvider) {return HomemadeMatrix .multiplyMatrices (matrixProvider.getFirstMatrix (), matrixProvider.getSecondMatrix ()); } @Benchmark openbaar object ejmlMatrixMultiplication (BigMatrixProvider matrixProvider) {SimpleMatrix firstMatrix = nieuwe SimpleMatrix (matrixProvider.getFirstMatrix ()); SimpleMatrix secondMatrix = nieuwe SimpleMatrix (matrixProvider.getSecondMatrix ()); retourneer firstMatrix.mult (secondMatrix); } @Benchmark openbaar object apacheCommonsMatrixMultiplication (BigMatrixProvider matrixProvider) {RealMatrix firstMatrix = nieuwe Array2DRowRealMatrix (matrixProvider.getFirstMatrix ()); RealMatrix secondMatrix = nieuwe Array2DRowRealMatrix (matrixProvider.getSecondMatrix ()); retourneer firstMatrix.multiply (secondMatrix); } @Benchmark openbaar object la4jMatrixMultiplication (BigMatrixProvider matrixProvider) {Matrix firstMatrix = nieuwe Basic2DMatrix (matrixProvider.getFirstMatrix ()); Matrix secondMatrix = nieuwe Basic2DMatrix (matrixProvider.getSecondMatrix ()); retourneer firstMatrix.multiply (secondMatrix); } @Benchmark openbaar object nd4jMatrixMultiplication (BigMatrixProvider matrixProvider) {INDArray firstMatrix = Nd4j.create (matrixProvider.getFirstMatrix ()); INDArray secondMatrix = Nd4j.create (matrixProvider.getSecondMatrix ()); retourneer firstMatrix.mmul (secondMatrix); } @Benchmark openbaar object coltMatrixMultiplication (BigMatrixProvider matrixProvider) {DoubleFactory2D doubleFactory2D = DoubleFactory2D.dense; DoubleMatrix2D firstMatrix = doubleFactory2D.make (matrixProvider.getFirstMatrix ()); DoubleMatrix2D secondMatrix = doubleFactory2D.make (matrixProvider.getSecondMatrix ()); Algebra-algebra = nieuwe algebra (); retourneer algebra.mult (firstMatrix, secondMatrix); }}

Wanneer we deze benchmarking uitvoeren, krijgen we totaal verschillende resultaten:

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 gem. 20 35,523 ± 0,102 s / op BigMatrixMultiplicationBenchmarking.nd4jMatrixMultiplication gem. 20 0,548 ± 0,006 s / op

Zoals we kunnen zien, zijn de zelfgemaakte implementaties en de Apache-bibliotheek nu veel slechter dan voorheen, het kost bijna 10 minuten om de vermenigvuldiging van de twee matrices uit te voeren.

Colt doet er iets meer dan 3 minuten over, wat beter is maar nog steeds erg lang. EJML en LA4J presteren redelijk goed, want ze lopen in bijna 30 seconden. Maar het is ND4J die deze benchmark binnen een seconde wint op een CPU-backend.

4.3. Analyse

Dat laat ons zien dat de benchmarkresultaten echt afhangen van de kenmerken van de matrices en dat het daarom lastig is om één winnaar aan te wijzen.

5. Conclusie

In dit artikel hebben we geleerd hoe we matrices in Java kunnen vermenigvuldigen, hetzij door onszelf, hetzij met externe bibliotheken. Nadat we alle oplossingen hadden verkend, hebben we ze allemaal getest en we zagen dat ze, behalve ND4J, allemaal redelijk goed presteerden op kleine matrices. Aan de andere kant neemt ND4J op grotere matrices het voortouw.

Zoals gewoonlijk is de volledige code voor dit artikel te vinden op GitHub.