Умножение двух матриц в Java

Question

В настоящее время я разрабатываю класс для представления матриц, он представляет собой любую общую матрицу mxn. Я разработал сложение и скалярное умножение, но я изо всех сил пытаюсь развить умножение двух матриц. Данные матрицы хранятся в двумерном массиве двойников.

Метод выглядит немного как это:

public Matrix multiply(Matrix A) { 
      ////code 
    } 

Она возвращает матрицу продукта. Это умножение справа. Итак, если бы я назвал A.multiply (B), то он вернул бы матрицу AB, а B - вправо.

Мне еще не нужно беспокоиться о проверке того, определено ли умножение на заданных матрицах, я могу предположить, что мне дадут матрицы правильных размеров.

Кто-нибудь знает простой алгоритм, возможно даже в псевдокоде, чтобы выполнить процесс умножения?

Заранее спасибо.

Answer 1

Математически произведение матриц А (LXM) и В (MXN) определяется как матрица С (LXN), состоящий из элементов:

 m 
c_i_j = ∑ a_i_k * b_k_j 
     k=1 

Так что, если вы не слишком много для скорости осуществление вы можете быть счастливы с прямым прямым O (N^3):

for (int i=0; i<l; ++i) 
    for (int j=0; j<n; ++j) 
     for (int k=0; k<m; ++k) 
     c[i][j] += a[i][k] * b[k][j] 

Если вместо того, чтобы вы на скорость вы можете проверить другие варианты, таких как алгоритм Штрассены (см: алгоритм Strassen).

Тем не менее следует предупредить - особенно если вы умножаете малые матрицы на современные процессорные архитектуры, скорость в значительной степени зависит от данных матрицы и порядка умножения, чтобы наилучшим образом использовать в строках кеша.

Я очень сомневаюсь, что у вас будет какой-либо шанс повлиять на этот фактор с помощью vm, поэтому я не уверен, что это нужно принять во внимание.

Answer 2

Java. Матричное умножение.

Вот «код для выполнения процесса умножения». Протестировано с матрицами разного размера.

public class Matrix { 

/** 
* Matrix multiplication method. 
* @param m1 Multiplicand 
* @param m2 Multiplier 
* @return Product 
*/ 
    public static double[][] multiplyByMatrix(double[][] m1, double[][] m2) { 
     int m1ColLength = m1[0].length; // m1 columns length 
     int m2RowLength = m2.length; // m2 rows length 
     if(m1ColLength != m2RowLength) return null; // matrix multiplication is not possible 
     int mRRowLength = m1.length; // m result rows length 
     int mRColLength = m2[0].length; // m result columns length 
     double[][] mResult = new double[mRRowLength][mRColLength]; 
     for(int i = 0; i < mRRowLength; i++) {   // rows from m1 
      for(int j = 0; j < mRColLength; j++) {  // columns from m2 
       for(int k = 0; k < m1ColLength; k++) { // columns from m1 
        mResult[i][j] += m1[i][k] * m2[k][j]; 
       } 
      } 
     } 
     return mResult; 
    } 

    public static String toString(double[][] m) { 
     String result = ""; 
     for(int i = 0; i < m.length; i++) { 
      for(int j = 0; j < m[i].length; j++) { 
       result += String.format("%11.2f", m[i][j]); 
      } 
      result += "\n"; 
     } 
     return result; 
    } 

    public static void main(String[] args) { 
     // #1 
     double[][] multiplicand = new double[][] { 
       {3, -1, 2}, 
       {2, 0, 1}, 
       {1, 2, 1} 
     }; 
     double[][] multiplier = new double[][] { 
       {2, -1, 1}, 
       {0, -2, 3}, 
       {3, 0, 1} 
     }; 
     System.out.println("#1\n" + toString(multiplyByMatrix(multiplicand, multiplier))); 
     // #2 
     multiplicand = new double[][] { 
       {1, 2, 0}, 
       {-1, 3, 1}, 
       {2, -2, 1} 
     }; 
     multiplier = new double[][] { 
       {2}, 
       {-1}, 
       {1} 
     }; 
     System.out.println("#2\n" + toString(multiplyByMatrix(multiplicand, multiplier))); 
     // #3 
     multiplicand = new double[][] { 
       {1, 2, -1}, 
       {0, 1, 0} 
     }; 
     multiplier = new double[][] { 
       {1, 1, 0, 0}, 
       {0, 2, 1, 1}, 
       {1, 1, 2, 2} 
     }; 
     System.out.println("#3\n" + toString(multiplyByMatrix(multiplicand, multiplier))); 
    } 
} 

Выход:

#1 
     12.00  -1.00  2.00 
     7.00  -2.00  3.00 
     5.00  -5.00  8.00 

#2 
     0.00 
     -4.00 
     7.00 

#3 
     0.00  4.00  0.00  0.00 
     0.00  2.00  1.00  1.00