hanyeah

两个n×n的矩阵相乘，按照定义来写算法，算法的时间复杂度是O(n³)。

Strassen算法是一个分治算法，可以将矩阵相乘的时间复杂度降为O(n^lg7)。

按照定义计算的算法，代码如下：

var a = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]];
var b = [[1,5,9,13],[2,6,10,14],[3,7,11,15],[4,8,12,16]];
var d = [[1,3],[7,5]];
var e = [[6,8],[4,2]];

var c = squareMatrixMultiply(a, b);
console.log(c);
var f = squareMatrixMultiply(d, e);
console.log(f);
function squareMatrixMultiply(a, b){
	var c = [];
	var n = a.length;
	for(var i = 0; i < n; i++){
		c[i] = [];
		for(var j = 0; j < n; j++){
			var cij = 0;
			for(var k = 0; k < n; k++){
				cij += a[i][k] * b[k][j];
			}
			c[i][j] = cij;
		}
	}
	return c;
}

Strassen算法

var a = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]];
var b = [[1,5,9,13],[2,6,10,14],[3,7,11,15],[4,8,12,16]];
var d = [[1,3],[7,5]];
var e = [[6,8],[4,2]];
var g = squareMatrixMultiplyRecursive(a, 0, 0, b, 0, 0, 4);
console.log(g);
var h = squareMatrixMultiplyRecursive(d, 0, 0, e, 0, 0, 2);
console.log(h);

function squareMatrixMultiplyRecursive(a, ai0, aj0, b, bi0, bj0, n){
	var c = [];
	if(n == 1){
		c[0] = [];
		c[0][0] = a[ai0][aj0] * b[bi0][bj0];
	} 
	else {
		var hn = n / 2;

		merge(
			squareMatrixMultiplyRecursive(
				a, ai0, aj0,
				b, bi0, bj0,
				hn),
			squareMatrixMultiplyRecursive(
				a, ai0, aj0 + hn,
				b, bi0 + hn, bj0,
				hn),
			c, 0, 0, hn
		);//c11 = a11 * b11 + a12 * b21;
		merge(
			squareMatrixMultiplyRecursive(
				a, ai0, aj0,
				b, bi0, bj0 + hn,
				hn), 
			squareMatrixMultiplyRecursive(
				a, ai0, aj0 + hn,
				b, bi0 + hn, bj0 + hn,
				hn),
			c, 0, hn, hn
		);//c12 = a11 * b12 + a12 * b22;
		merge(
			squareMatrixMultiplyRecursive(
				a, ai0 + hn, aj0,
				b, bi0, bj0,
				hn),
			squareMatrixMultiplyRecursive(
				a, ai0 + hn, aj0 + hn,
				b, bi0 + hn, bj0,
				hn),
			c, hn, 0, hn
		);//c21 = a21 * b11 + a22 * b21;
		merge(
			squareMatrixMultiplyRecursive(
				a, ai0 + hn, aj0,
				b, bi0, bj0 + hn,
				hn),
			squareMatrixMultiplyRecursive(
				a, ai0 + hn, aj0 + hn,
				b, bi0 + hn, bj0 + hn,
				hn),
			c, hn, hn, hn
		);//c22 = a21 * b12 + a22 * b22;
	}
	return c;
}

function merge(a, b, c, i0, j0, n){
	for(var i = 0; i < n; i++){
		c[i0 + i] = c[i0 + i] || [];
		for(var j = 0; j < n; j++){
			c[i0+i][j0+j] = a[i][j] + b[i][j]; 
		}
	}
}

Strassen算法时间复杂度降低了，但是空间复杂度太高了。

目前，n×n矩阵相乘的渐进复杂性最优的算法是Coppersmith和Winograd提出的，运行时间为O(n^2.376)。

计算机算法：Strassen矩阵相乘算法