如何在C中实现矩阵乘法（X1，X2 ......）？ [英] How can I implement matrix multiplication (X1, X2......)in C?

问题描述

划分和征服矩阵乘法算法：

 MMult（A，B，n）
 
如果n = 1输出A× B 
 
 Else Compute A11，B11 ,. 。 。 ，A22，B22％计算m = n / 2 
 
 X1←MMult（A11，B11，n / 2）
 
 X2←MMult（A12，B21，n / 2）
 
 X3←MMult（A11，B12，n / 2）
 
 X4←MMult（A12，B22，n / 2）
 
 X5←MMult（A21，B11，n / 2）
 
 X6←MMult（A22，B21，n / 2）
 
 X7←MMult（A21，B12，n / 2）
 
 X8←MMult（A22，B22，n / 2）
 
 C11←X1 + X2 
 
 C12←X3 + X4 
 
 C21←X5 + X6 
 
 C22←X7 + X8 
 
输出C 
 
结束如果

我的尝试：



我不明白我可以在这里使用什么数据结构，或者如何实现上述算法... plz帮我提供一些c代码。

#Thanks ... expert

解决方案

但我怎么能计算A11，B11 ,. 。 。 ，A22，B22％计算m = n / 2 in c？

简单方法：

你分配你的本地 A ?? 和 B ?? 并复制 A的相应部分和 B 这些矩阵然后递归调用 MMult 。这将使用大量额外的内存。



更难（更有思考！）方式：

使用递归调用 MMult 的不同函数（例如， InternalMMult ）

此函数将将原始 A 和 B 作为参数，但也将包含有关的行和列范围的信息<每次递归调用时code> A 和 B 。此函数将根据 A 和 B 的指定感兴趣区域进行计算。



可能可以通过普通中间件（ X ）和结果（ C ）具有类似方式的范围的矩阵。这需要一些认真的分析！ （你是为了挑战吗？！）



注意：

正如我在上面关于原始问题的评论中所述：

但是，您显示的算法仅适用于等级等于2的平方矩阵。

它是否真的比处理 NxK mult KxM 给出的一般情况的三重嵌套循环更有效a NxM ？

您可以使用数组来保存每个矩阵的值，然后根据规则相乘。

Divide and conquer algorithm for matrix multiplication:

MMult(A, B, n)

If  n= 1  Output  A×B

Else  Compute A11,B11, . . . , A22,B22 % by computing  m=n/2

X1←MMult(A11, B11, n/2)

X2←MMult(A12, B21, n/2)

X3←MMult(A11, B12, n/2)

X4←MMult(A12, B22, n/2)

X5←MMult(A21, B11, n/2)

X6←MMult(A22, B21, n/2)

X7←MMult(A21, B12, n/2)

X8←MMult(A22, B22, n/2)

C11←X1+X2

C12←X3+X4

C21←X5+X6

C22←X7+X8

Output C

End If

What I have tried:

I don't understand what data structure can i use here or, how the above algorithm can be implemented...plz help me giving some pieces of c code.
#Thanks...experts

解决方案

But how could I Compute A11,B11, . . . , A22,B22 % by computing m=n/2 in c?

The easy way:
You allocate your local A?? and B?? and copy the appropriate pieces of the A and B matrices into these and then call MMult recursively. This will use lots of additional memory.

The harder (more thinking!) way:
Use a different function for the recursive calls to MMult (e.g., InternalMMult)
This function will take as parameters the original A and B but will also include the information about the row and column ranges of interest for A and B at each recursive call. This function will do its calculations based on the specified regions of interest of the A and B.

It may be possible to pass common intermediate (X) and result (C) matrices with ranges in a similar manner. This would take some serious analysis! (Are you "up" for a challenge?!)

Note:
As I noted in my comment above on the original question:
However, the algorithm you show will work correctly only for square matrices with rank equal to a power of 2.
Is it really more efficient than the triple-nested loop that handles the general case of an NxK mult KxM giving a NxM?

You can use arrays to hold the values of each matrix, and then just multiply according to the rules.

这篇关于如何在C中实现矩阵乘法（X1，X2 ......）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！