利用Hadoop实现超大矩阵相乘之我见（一）
前记
最近，公司一位挺优秀的总务离职，欢送宴上，她对我说“你是一位挺优秀的程序员”，刚说完，立马道歉说“对不起，我说你是程序员是不是侮辱你了？”我挺诧异，程序员现在是很低端，很被人瞧不起的工作吗？或许现在连卖盗版光盘的，修电脑的都称自己为搞IT的，普通人可能已经分不清搞IT的到底是做什么的了。其实我想说，程序员也分很多种的，有些只能写if-then-else,有些只能依葫芦画瓢，但真正的程序员我想肯定是某个领域的专家，或许他是一位数学家，或许他是一位物理学家，再或许他是计算机某个细分领域的专家，他是理论与现实的结合，是凌驾于纯理论的存在！而笔者我正立志成为这样的能让人感到骄傲的程序员。
切入正题吧，谈到云计算，不得不提大数据，处理大数据，肯定逃不离分布式计算。互联网行业，无论是商品推荐还是好友推荐，还是PageRank,所要处理的Items规模、用户规模都是极其庞大的，小则数以百万、千万记，大则数以亿记。在此数据基础上，诞生了很多优秀的推荐算法，推荐算法中大部分会运用到矩阵运算。如此大规模的数据，一台计算机已经没有能力处理，说简单点，一台服务器的内存可能连加载半个矩阵数据都不够，更别谈处理了。“当一头牛拉不动车时，很少有人去找一头更大更强壮的牛，而是找来更多的牛一起拉。”，这就是分布式计算，而Hadoop就是在分布式集群上处理大记录集的强大利器。
笔者最近对推荐算法挺感兴趣的，也研究了一些！部分算法数学公式研究的透彻了，便有自己想实现的冲动，可公式里的矩阵运算可不是那么简单!所以就想从研究超大规模矩阵相乘开始，一方面为以后做大规模矩阵运算、实现推荐算法做技术储备；另一方面也想真正体验一把用Hadoop实现分布式运算的乐趣；最重要的是能够写一些包含独特思想，有研究成分，有技术含量的代码。
摘要
本文首先讨论了目前现有的大矩阵运算方法，并指出其不足；接着提出自己的矩阵运算方法来解决目前现有方法所存在的问题，同时通过实验来观测本文方法所存在的问题，并针对这些问题，对本文方法进行再优化。
现有方法
行列相乘运算简介
传统的矩阵运算是A矩阵中的每一行分别与B矩阵中的每一列相乘。假设矩阵A的规模为（m*r）,矩阵B的规模为（r*n）,则矩阵C的规模为（m*n）。矩阵C中元素Ci,j是A中第i行与B中第j列元素依次对应相乘并汇总的结果。公式表示如下：
每一个Ci,j的计算都是独立的，所以可以交由不同的计算节点完成。
缺点
1、矩阵规模有一定限制，如果A矩阵或B矩阵有一个超大，则某个运算节点就很有可能由于内存限制，加载不了A矩阵的第i行或B矩阵的第j列。
2、对于稀疏矩阵计算没优势。若A，B中有稀疏矩阵存在，需判断A中i行与B中第j列对应的位置上是否有0元素，换句话说，还是需要加载第i行，第j列的全部内容，若某个位置没有输入，在运算过程中需要将相应位置用0填充，这样会造成上一点所存在的问题：内存放不下。
矩阵分块运算简介
当矩阵大到一定程度时，一台服务器由于内存限制已经无法处理，不过由于矩阵具体天然的可分块的特性，许多基于分块的矩阵运算算法诞生了，《数学之美》这本书上介绍的大矩阵相乘方法就是基于分块的，现简单介绍如下：
1、当A矩阵纵向很大，横向不大时，我们将A矩阵分块，将A矩阵中的分块分别与B矩阵相乘，通过Hadoop，这些计算可以并行进行，如图1所示：
图1
图中A1*B=C1,A2*B=C2,…,每部分计算分别可在不同的计算节点完成，最后将结果组合在一起。
2、当A矩阵为一个真正的超大矩阵（横向纵向都很大），与之相乘的B矩阵也必是一个超大矩阵（至少纵向很大），此时A，B矩阵都需要按行按列进行分块，并将不同的分块计算交由不同的计算节点完成，如图2所示。
图2
图中，矩阵A中的每一块都需要和矩阵B中对应位置的块依次相乘，这些块与块之间的相乘运算可以由不同的计算节点完成，最后将不同块与块的运算结果，经过严密精确的控制，对相关结果进行合并（主要是相加），得到最终的运算结果C。
缺点
1、对于不同的矩阵规模，如何分块是难点，同时块的大小受限于内存大小。
2、块与块之间的运算以及组织较繁琐。
3、不太利于稀疏矩阵的运算（0值占用较多的存储空间，以及会做很多无效运算）
基于最小粒度相乘的算法
为了文档的命名结构，笔者自己根据算法原理，起了这个名字。
简介
“行列相乘运算”和“分块运算”都受限于计算节点的内存限制。那么有没有一种运算，跟计算节点的内存大小无关呢？答案是：肯定有！总所周知，矩阵相乘的最小粒度计算是两个矩阵中的两个数相乘，比如，且计算结果是的一个组成部分。
假设有两个超大矩阵A和B，A的规模是（m*r）,B的规模是（r*n），将矩阵相乘中的最小粒度乘法运算进行统计，我们不难发现：A中每个元素Ai,k需要与B中第k行的元素Bk,j(j=1,2,…,n)依次相乘，计算结果分别为Ci,j的一个组成部分；而B中每个元素Bk,j需要与A中第j列的元素Ai,k(i=1,2,…,m)依次相乘，计算结果分别为Ci,j的一个组成部分。具体如图3所示。
图3
由于Ai,k*Bk,j是独立的，因此可以由不同的计算节点进行运算，最后根据key （i,j）将运算结果进行汇总相加，得到结果Ci,j。同时，每个计算节点每次计算时都是只加载两个数进行相乘，并不需要加载矩阵的某个块或者某行某列，因此没有内存的限制问题，理论上只要hadoop的HDFS文件系统够大，就可以计算任意大规模的矩阵相乘。
一个今天胜过两个明天
