关于矩阵乘法

设矩阵A大小为m*p，矩阵B大小为p*n，C=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

矩阵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章