Nocoo.Weblog

同济大学 计算机软件与理论 0720080247 李征
1. 矩阵乘法最优算法
1.1 矩阵与计算机科学
数学的重要性显而易见。数学是各种科学的基础，计算机也不例外。对于计算机学科起着关键性作用的数学分支主要是离散数学，因为计算机处理的数据还是二进制的离散量，对于连续量的处理还处在模拟的阶段。
此外，计算机科学中大量分支涉比如系统结构和计算机网络等等，都需要一定的逻辑学和图论作为其研究的支撑。作为离散数学的核心，矩阵的重要性不言而喻。众多的复杂计算机模型都可以用简单的矩阵来表示，而矩阵的运算也经常代表着重要的计算机物理含义。本文研究的搜索引擎排名评价体系就是其中之一。
1.2 矩阵乘法的理论下界
设A是一个m行n列矩阵
[singlepic=14397,,center]
B是另一个n行q列矩阵
[singlepic=14400,,center]
矩阵A和B的乘积是一个m行q列矩阵
[singlepic=14401,,center]
其中
[singlepic=14402,,center]
从定义出发计算矩阵的乘积，需要n次乘法运算和n-1次加减运算，得到的是计算矩阵乘法的计算复杂度的上界。当m、n和q被认为是同阶的数的时候，算法复杂度是O(n^3)。
两个矩阵相乘的任何可能的算法，运算次数至少不低于矩阵与向量相乘（当q=1时退化的情况）。此时，需要mn次乘法运算和m(m-1)次加减运算，当m和n同阶时，算法复杂度是O(n^2)。
由此可以得出结论，正确的矩阵相乘算法，其复杂度介于O(n^3)与O(n^2)。
1.3 几个典型的矩阵乘法算法
1.3.1 Winograd矩阵乘法算法
S. Winograd于1967年提出了一个矩阵乘法算法，其核心思想是修改向量内积计算方法，对重复计算部分进行预处理，然后将计算结果多次使用，从而达到简化计算的目的。
Winograd矩阵乘法算法实质是增加约50%的加减法代价以换取减少约50%乘法运算，但是其算法复杂度仍然是O(n^3)，并没有降低算法复杂性的阶。
1.3.2 Strassen矩阵乘法算法
Strassen算法是另外一个矩阵乘法算法，这个算法突破了O(n^3)的计算复杂度阶，由V. Strassen在1969年提出。
Strassen算法主要用于方阵的计算。Strassen观察了简单2阶方阵乘法的计算特点，使用7次乘法计算就能算出结果，而不是平常的8次，从而降低了整个算法计算复杂度阶。
Strassen算法的计算复杂度是O(n^(log2 7) )=O(n^2.31 )。
1.4 一个最优矩阵乘法算法
1989年，我的研究生导师蒋昌俊教授提出了一个新的矩阵乘法算法，称为凝聚算法。凝聚算法把矩阵相乘的计算复杂度降到了理论下界O(n^2)。
凝聚算法从非负整数矩阵出发，即当A和B的元素都是非负整数时，可以通过设置足够大的x和y，分别通过求x的m-1次多项式和y的q-1次多项式的值，把矩阵A的各列的元素和矩阵B的各行的元素凝聚在一起，分别得到n维向量[a1,a2,…,an]和[b1,b2,…,bn]，其中ak和bk分别是矩阵A的第k列元素和矩阵B的第k行元素的“凝聚”结果。通过向量的内积运算，又可以将上述两个向量的各个分量进一步凝聚成一个整数c。最后，以y为除数作q-1次整数求余运算，就把整数c散列成q个整数c1,c2,…,cq，再把ck对x作m-1次整除求余运算，又将ck散列成m个数，就得到了积矩阵C的第k列元素c1k,c2k,…,cmk。算法的关键之处在于设置x和y为足够大的整数，以便使整除求余的散列能够正确地反映前面通过多项式求值和向量内积运算的凝聚效果。
第一步：对x和y的取值是算法的关键，如果x和y的取值不合理，将得不到正确的反散列。
[singlepic=14403,,center]
第二步：对从1到n的k，用Horner方法计算：
[singlepic=14404,,center]
第三步：c=a1b1+a2b2+⋯+anbn
第四步：作除法，依次求商d1,d2,…,d(q-2)，rq和余数r1,r2,…,r(q-1)，使得：
[singlepic=14405,,center]
第五步：
对从1到q的j作除法，依次求商kj1,kj2,…,k(j(m-2))，rjm和余数rj1,rj2,…,r(j(m-1))，使得
[singlepic=14406,,center]
for i=1 to m do
for j=1 to q do
cij=r(j(m-i1+))
repeat
repeat
整个计算过程中各种操作的数量是

比较：mn+nq-2
乘法：mn+mq+nq
除法：mq-1
加减：mn+mq+nq-n

当m、n和q被认为同阶时，凝聚算法计算过程中有2n^2-2次比较运算，3n^2次乘法运算，n^2-1次除法运算和3n^2-n次加减运算，计算复杂度为O(n^2)。
2. 矩阵乘法最优算法在搜索引擎排名中的应用
2.1 一种互联网结构建模
万维网（World Wide Web，WWW）是指在因特网上以超文本为基础形成的信息网。万维网为用户提供了一个可以浏览的图形化界面，用户通过它可以查阅Internet上的信息资源。WWW是通过互联网获取信息的一种应用，我们所浏览的网站就是WWW的具体表现形式，但其本身并不就是互联网，万维网只是互联网的组成部分之一。互联网常用的服务包括：WWW、Email、FTP、Usenet、IM等。
在“谁发明了浏览器” 文中介绍了蒂姆-伯纳斯－李（Tim Berners-Lee）于1990年发明了首个网页浏览器－－World Wide Web。在1991年蒂姆-伯纳斯-李建立世界上第一个网站，它于1991年8月6日上网，它解释了万维网是什么，如何使用网页浏览器和如何建立一个网页服务器等等。综合各种资料，1991年8月6日被认为是是万维网诞生的日子。
WWW的基础是超文本和链接，链接也使得一个一个网站被相互链接起来，成为了全球规模的巨大网络。链接分为两种，一种称为内部链接，指从一个网站某个网页，链接到同一网站的另一个网页的链接；另一种称为外部链接，指从一个网站某个网页，链接到另一个网站的某个网页的链接。实际当中考虑的链接是外部链接，因为外部链接反映了整个互联网的拓扑关系。
搜索引擎是一种互联网应用，搜索引擎是自动从Internet搜集信息，经过一定整理以后，提供给用户进行查询的系统。英特网上的信息浩瀚万千，而且毫无秩序，所有的信息像汪洋上的一个个小岛，链接是这些小岛之间纵横交错的桥梁，而搜索引擎，则为你绘制一幅一目了然的信息地图，供你随时查阅。
对于搜索引擎来说，网站及其链接关系可以用图来描述。
[singlepic=14407,,center]
图1 八个网站相互链接的例子
通过邻接矩阵A可以描述整个网络的拓扑结构。邻接矩阵A定义为
[singlepic=14398,,center]
我们认为，一个网站本身是存在指向本身的链接的，因此aii=1。
图1中的示例的邻接矩阵为
[singlepic=14399,,center]
2.2 互联网站价值评价标准
用户通过搜索引擎找到他们所需要的网站和页面，而搜索引擎也被用户寄予厚望，希望能够在排在最前面的搜索结果中得到他们觉得最有价值的目标页面。
互联网络是一个开放的系统，如何去衡量信息的可靠性呢？当然，CNN或者人民日报谈论一个问题，和一个普通博客谈论一个问题，当然是不一样的。即，信息是有权值的。
为每一个网站人工去赋一个权值明显是不现实的。互联网站数目超过了1亿个，而且每个网站不停地在更新，一个固定的权值也是不合适的。
Google设计了PageRank算法。PageRank是一个动态的评价体系，能够动态地对网站和网页提供的信息的重要程度进行评估，并据此作为一项标准，排序用户搜索结果。
一般人们认为，可靠的信息来自于新闻网站、大公司和百科全书。这些网站被人工选出，赋予最高的PageRank权值。然后根据这些网站的外部链接，将自己的PageRank递减地传递下去，被这些网站链接的网站获得了第二级的PageRank，如此传递下去，就可以链接到每一个网站（除了那些没有意义的信息孤岛网站）。
如果我们得到了整个互联网的邻接矩阵A，那么我们可以通过计算A^k，得到经过k次链接后，哪些网站得到了传递过来的PageRank。
2.3 矩阵乘法最优算法在搜索引擎排名中的应用
互联网邻接矩阵是一个超级规模的矩阵，超过1亿维。在这里，我们探讨一下做一次相乘，凝聚算法能够带来的性能提升。
假设：互联网站数目n=1×10^8个，超级计算机（例如2008年6月9日IBM公司的“走鹃”）每秒进行运算1×10^15次。

Winograd算法(1967)：2n^3+3n^2-4n+1，2×10^9秒=63.4年
Strassen算法(1969)：6n^2.31-6n^2，18059秒=5小时
凝聚算法(1989)：9n^2-n-3，90秒

由此可见，如果能够将凝聚算法应用在搜索引擎领域，会带来巨大的性能提升。
3. 参考资料
[1]. 矩阵乘法的一个最佳算法. 蒋昌俊, 吴哲辉, 1989, 科学通报第4期, 251-254
[2]. “矩阵乘法的一个最佳算法”一文的进一步研究. 蒋昌俊, 吴哲辉, 1994, Vol. 11, No. 2, 149-153
查看本文PDF版本：凝聚算法在搜索引擎应用设想