Java实现矩阵乘法以及优化的方法实例

缺乏、安全感 2022-10-27 13:58 52阅读 0赞

传统的矩阵乘法实现  
  首先，两个矩阵能够相乘，必须满足一个前提：前一个矩阵的行数等于后一个矩阵的列数。

第一个矩阵的第m行和第二个矩阵的第n列的乘积和即为乘积矩阵第m行第n列的值，可用如下图像表示这个过程。

矩阵乘法过程展示

C\[1\]\[1\] = A\[1\]\[0\] \* B\[0\]\[1\] + A\[1\]\[1\] \* B\[1\]\[1\] + A\[1\]\[2\] \* B\[2\]\[1\] + A\[1\]\[3\] \* B\[3\]\[1\] + A\[1\]\[4\] \* B\[4\]\[1\]

而用Java实现该过程的传统方法就是按照该规则实现一个三重循环，把各项乘积累加：

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
public int\[\]\[\] multiply(int\[\]\[\] mat1, int\[\]\[\] mat2)\{  
int m = mat1.length, n = mat2\[0\].length;  
int\[\]\[\] mat = new int\[m\]\[n\];  
for(int i = 0; i < m; i++)\{  
for(int j = 0; j < n; j++)\{  
for(int k = 0; k < mat1\[0\].length; k++)\{  
mat\[i\]\[j\] += mat1\[i\]\[k\] \* mat2\[k\]\[j\];  
\}  
\}  
\}  
return mat;  
\}  
  可以看出该方法的时间复杂度为O(n3)，当矩阵维数比较大的时候程序就很容易超时。

优化方法（Strassen算法）  
  Strassen算法是由Volker Strassen在1966年提出的第一个时间复杂度低于O(n³)的矩阵乘法算法，其主要思想是通过分治来实现矩阵乘法的快速运算，计算过程如图所示：

将一次矩阵乘法拆分成多个乘法与加法的结合

为什么这个方法会更快呢，我们知道，按照传统的矩阵乘法：

C11 = A11 \* B11 + A12 \* B21  
C12 = A11 \* B12 + A12 \* B22  
C21 = A21 \* B11 + A22 \* B21  
C22 = A21 \* B12 + A22 \* B22

我们需要8次矩阵乘法和4次矩阵加法，正是这8次乘法最耗时；而Strassen方法只需要7次矩阵乘法，尽管代价是矩阵加法次数变为18次，但是基于数量级考虑，18次加法仍然快于1次乘法。

发表评论取消回复

表情：

评论列表（有 0 条评论，52人围观）

还没有评论，来说两句吧...

相关阅读

相关矩阵乘法

C语言实现 IDE：Dev c++ include <stdio.h> define order 2 //阶数 define power 2 //幂

分手后的思念是犯贱/ 2023年07月11日 11:11/ 0 赞/ 1 阅读

相关 C语言实现矩阵的乘法

矩阵乘法作为算法题我觉得对我来说是比较难想的，而且作为没学线性代数的我来说，这简直就是场灾难，在我研究了书上及网上的有关资料后，我觉得自己应该差不多可以理解矩阵乘法的要领了，希

布满荆棘的人生/ 2023年06月30日 14:56/ 0 赞/ 43 阅读

相关 python矩阵乘法_Python矩阵乘法

![8f8364480b072857bd26840f3c0f62a0.png][] python矩阵乘法 Here you will get program for pyt

约定不等于承诺〃/ 2022年12月07日 13:28/ 0 赞/ 316 阅读

相关矩阵乘法

矩阵乘法新建两个矩阵A和B，两个矩阵的数据为‪‬‪‬‪‬‪‬‪‬‮‬‫‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬

ゝ一纸荒年。/ 2022年11月10日 10:53/ 0 赞/ 265 阅读

相关 Java实现矩阵乘法以及优化的方法实例

传统的矩阵乘法实现首先，两个矩阵能够相乘，必须满足一个前提：前一个矩阵的行数等于后一个矩阵的列数。第一个矩阵的第m行和第二个矩阵的第n列的乘积和即为乘积矩阵第

缺乏、安全感/ 2022年10月27日 13:58/ 0 赞/ 53 阅读

相关矩阵乘法

Description 矩阵乘法是线性代数中最基本的运算之一。给定三个矩阵 ![201206272323475818777_A41D5DD39303B72B0

忘是亡心i/ 2022年09月30日 06:09/ 0 赞/ 293 阅读

相关矩阵乘法的java实现

文章目录 1、算法思想 2、代码实现 1、算法思想 > 最近老是碰到迭代问题，小数太多手算又算不过来，写个矩阵乘法辅助一下吧。有两个矩阵A和B，计

ゝ一世哀愁。/ 2022年09月15日 12:28/ 0 赞/ 181 阅读

相关实现矩阵的乘法初级程序

\include <stdio.h> int main() \{ int arr1\[10\]\[10\] = \{ 0 \}, arr2\[10

秒速五厘米/ 2022年07月29日 09:06/ 0 赞/ 155 阅读

相关矩阵乘法

文章目录矩阵乘法(行操作) 矩阵乘法(列操作) 矩阵乘法(行操作) 如果有： E = \[ 1 0 0 − 2 1 0

Myth丶恋晨/ 2022年05月09日 14:48/ 0 赞/ 336 阅读

相关 MapReduce实现矩阵乘法

简单回顾一下矩阵乘法： ![C=AB][C_AB] 矩阵乘法要求左矩阵的列数与右矩阵的行数相等，m×n的矩阵A，与n×p的矩阵B相乘，结果为m×p的矩阵C。详细内容可以查看

川长思鸟来/ 2021年09月25日 15:56/ 0 赞/ 435 阅读