如何使用MapRedue实现矩阵乘法

2014-11-19

本文介绍两种常用的矩阵乘法的实现。

关于矩阵乘法


设矩阵A大小为m*p,矩阵B大小为p*nC=A*B,C的大小为m*n。矩阵中每个元素的行号和列号均从1开始,矩阵C可以通过下面的公式计算得到。

[latex]
C_{i,j}=\sum_{k=1}^{p}A_{i,k}*B_{k,j}
[/latex]

实现方案1


在文件中每一行存储矩阵中的一个元素,每一行格式如下:

所属矩阵#行号#列号#值

例如,若矩阵A是:

2 3
4 1
1 0

矩阵B是:

2
7

A在数据文件中对应的文件内容是:

A#1#1#2
A#1#2#3
A#2#1#4
A#2#2#1
A#3#1#1
A#3#2#0

B在数据文件中对应的文件内容是:

B#1#1#2
B#2#1#7

上面是Map Task的输入,对于每一行输入Map Task的输出中key和value的格式是:

行号#(1...n)  -> 所属矩阵#列号#对应的值

对于Map Task,每一行输入,有n个输出。

n为1,故对矩阵A,Map的输出是:

1#1 -> A#1#2
1#1 -> A#2#3
2#1 -> A#1#4
2#1 -> A#2#1
3#1 -> A#1#1
3#1 -> A#2#0

矩阵B的文件格式和A相同,对于每一行输入Map Task的输出中key和value的格式是:

(1...m)#列号  -> 所属矩阵#行号#对应的值

m为3。故对矩阵B,对于每一行输入,Map Task的输出中key和value的格式是:

1#1 -> B#1#2
1#1 -> B#2#7
2#1 -> B#1#2
2#1 -> B#2#7
3#1 -> B#1#2
3#1 -> B#2#7

在Reduce过程中输入的相同的键的值将放在一起,例如对于键1#1,Reduce的输入中,values为:

A#1#2,A#2#3,B#1#2,B#2#7

构造两个向量(也就是数组)a和b,a[1]=2,a[2]=3,b[1]=2,b[2]=7,将a和b点乘,得到2*2+3*7=25,故C[1,1] = 25。
Reduce的输出中key和value的格式是:

行号#列号 -> 结果

比如:

1#1 25

实现方案2


矩阵C在[i,j]处元素的值,其实就是矩阵A第i行、矩阵B第j列的点乘结果,所以可以让Map的输入的每个数据就是矩阵的一行或者一列。

对于矩阵A,数据文件中每行存储矩阵的一行,每行格式如下:

A#行号#这一行的数据

对于矩阵B,数据文件中每行存储矩阵的一列,每行格式如下:

B#列号#这一列的数据

于是可以得到数据文件:

A#1#2,3
A#2#4,1
A#3#1,0
B#1#2,7

以上的Map Task的输入。
对于矩阵A,每一行数据转换为:

行号#(1...n)  -> 所属矩阵#这一行的值

对于矩阵B,每一列数据转换为:

(1...m)#列号  -> 所属矩阵#这一列的值

所以Map Task的输出是:

1#1  A#2,3
2#1  A#4,1
3#1  A#1,0
1#1  B#2,7
2#1  B#2,7
3#1  B#2,7

Map Task的输出将作为Reduce Task的输入。在Reduce过程中输入的相同的键的值将放在一起,例如对于键1#1,Reduce的输入中,values为:

"A#2,3", "B#2,7"

将向量2,3与向量2,7点乘结果为25,所有C[1,1]=25。

其他


矩阵乘法还有其他的MapReduce实现思路,例如分块计算,这里暂且不做介绍了。

参考


Hadoop大数据处理 刘军 著 第9章

( 完 )