文章目录
  1. 1. n×n矩阵计算
    1. 1.1. n×n矩阵
    2. 1.2. 基本js实现
    3. 1.3. 验证
  2. 2. 分治策略的矩阵算法
    1. 2.1. 直接的递归分治算法
    2. 2.2. 矩阵乘法的Strassen算法

n×n矩阵计算的javascript实现。

n×n矩阵计算


n×n矩阵

A = (a[i][j])B = (b[i][j])为n × n的方阵,则对i, j = 1, 2, ..., n,定义乘积C = A · B中的元素c[i][j]为:

image

基本js实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function squareMatrixMultiply(A, B) {
var n = A.length;
var C = [];
for (var i = 0; i < n; i++) {
C[i] = [];
for (var j = 0; j < n; j++) {
C[i][j] = 0;
for (var k = 0; k < n; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}

验证

1
2
3
4
5
6
7
8
9
var AMatrix = [[1, 3], [7, 5]];
var BMatrix = [[6, 8], [4, 2]];
squareMatrixMultiply(AMatrix, BMatrix);
// 输出[[18, 14], [62, 66]]
var AMatrix = [[1, 3, 2, 1], [7, 5, 1, 7], [1, 2, 3, 9], [2, 3, 1, 2]];
var BMatrix = [[6, 8, 2, 2], [4, 2, 2, 8], [2, 3, 1, 2], [7, 5, 1, 7]];
squareMatrixMultiply(AMatrix, BMatrix);
// 输出[[29, 25, 11, 37], [113, 104, 32, 105], [83, 66, 18, 87], [40, 35, 13, 44]]

分治策略的矩阵算法


直接的递归分治算法

  • 思路

image

  • js实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
function squareMatrixMultiplyRecursive(A, B) {
// 传入原矩阵、复制起点(x, y)、复制长度n
function getMatrix(M, x, y, n) {
// console.log(M, x, y, n)
var N = [];
for (var i = 0; i < n; i++) {
N[i] = [];
for (var j = 0; j < n; j++) {
// 复制值
N[i][j] = M[i + y][j + x];
}
}
return N;
}
// 方阵的相加, 若传入type为'minus',则进行减运算
function addMatrix(A, B, type) {
var n = A.length;
var N = [];
for (var i = 0; i < n; i++) {
N[i] = [];
for (var j = 0; j < n; j++) {
// 复制值
N[i][j] = type === 'minus' ? (A[i][j] - B[i][j]) : (A[i][j] + B[i][j]);
}
}
return N;
}
// 整理矩阵,将多维数组整理成二维数组
function convertMatrix(M) {
// 取出所有值
var arr = M.toString().split(',');
var array = [];
// 选出有效值
for (var k = 0; k < arr.length; k++) {
if (arr[k]) { array.push(Number(arr[k])); }
}
// 计算数组长度以及平方根
var n = array.length;
var m = Math.sqrt(n);
// console.log('M', M, n, m)
// 重新整理为二维数组
var N = [], L = [];
N[0] = array.slice(0, n / 4);
N[1] = array.slice(n / 4, n / 2);
N[2] = array.slice(n / 2, n * 3 / 4);
N[3] = array.slice(n * 3 / 4, n);
for (var i = 0; i < m; i++) {
L[i] = [];
}
for (var l = 0; l < 4; l++) {
for (var i = 0; i < m / 2; i++) {
for (var j = 0; j < m / 2; j++) {
L[i + Math.floor(l / 2) * m / 2].push(N[l][j + i * m / 2]);
}
}
}
return L;
}
var n = A.length; // 获取长度
// 创建n×n矩阵C
var C = [];
for (var i = 0; i < n; i++) { C[i] = []; }
if (n === 1) {
// 若只有一个数,则返回乘积
C[0][0] = A[0][0] * B[0][0];
} else {
var m = parseInt(n / 2);
// 分割A为n/2矩阵[[A11, A12], [A21, A22]]
var A11 = getMatrix(A, 0, 0, m);
var A12 = getMatrix(A, m, 0, n - m);
var A21 = getMatrix(A, 0, m, n - m);
var A22 = getMatrix(A, m, m, m);
// 分割B为n/2矩阵[[B11, B12], [B21, B22]]
var B11 = getMatrix(B, 0, 0, m);
var B12 = getMatrix(B, m, 0, n - m);
var B21 = getMatrix(B, 0, m, n - m);
var B22 = getMatrix(B, m, m, m);
// 递归求出A11, A12, A21, A22以及B11, B12, B21, B22的值
// 求出矩阵C,并返回
C[0][0] = addMatrix(squareMatrixMultiplyRecursive(A11, B11), squareMatrixMultiplyRecursive(A12, B21));
C[0][1] = addMatrix(squareMatrixMultiplyRecursive(A11, B12), squareMatrixMultiplyRecursive(A12, B22));
C[1][0] = addMatrix(squareMatrixMultiplyRecursive(A21, B11), squareMatrixMultiplyRecursive(A22, B21));
C[1][1] = addMatrix(squareMatrixMultiplyRecursive(A21, B12), squareMatrixMultiplyRecursive(A22, B22));
C = convertMatrix(C);
}
return C;
}
  • 验证
1
2
3
4
5
6
7
8
9
var AMatrix = [[1, 3], [7, 5]];
var BMatrix = [[6, 8], [4, 2]];
squareMatrixMultiplyRecursive(AMatrix, BMatrix);
// 输出[[18, 14], [62, 66]]
var AMatrix = [[1, 3, 2, 1], [7, 5, 1, 7], [1, 2, 3, 9], [2, 3, 1, 2]];
var BMatrix = [[6, 8, 2, 2], [4, 2, 2, 8], [2, 3, 1, 2], [7, 5, 1, 7]];
squareMatrixMultiplyRecursive(AMatrix, BMatrix);
// 输出[[29, 25, 11, 37], [113, 104, 32, 105], [83, 66, 18, 87], [40, 35, 13, 44]]

矩阵乘法的Strassen算法

该算法比较长,大家可参考《算法导论》一书或者Strassen 演算法──分治矩陣乘法

  • 思路

2×2矩阵计算:
image

传统的矩阵乘法运算方式,C[i][j] = A[i][1]·B[1][j] + A[i][2]·B[2][j],总共使用8个分块乘法和4个分块加法。
Strassen演算使用7个分块乘法和18个分块加法:
image

  • js实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
function squareMatrixMultiplyStrassen(A, B) {
// 传入原矩阵、复制起点(x, y)、复制长度n
function getMatrix(M, x, y, n) {
var N = [];
for (var i = 0; i < n; i++) {
N[i] = [];
for (var j = 0; j < n; j++) {
// 复制值
N[i][j] = M[i + y][j + x];
}
}
// console.log(M,x,y,n,N)
return N;
}
// 方阵的相加, 若传入type为'minus',则进行减运算
function addMatrix(A, B, type) {
var n = A.length;
var N = [];
for (var i = 0; i < n; i++) {
N[i] = [];
for (var j = 0; j < n; j++) {
// 复制值
N[i][j] = type === 'minus' ? (A[i][j] - B[i][j]) : (A[i][j] + B[i][j]);
}
}
return N;
}
// 整理矩阵,将多维数组整理成二维数组
function convertMatrix(M) {
// 取出所有值
var arr = M.toString().split(',');
var array = [];
// 选出有效值
for (var k = 0; k < arr.length; k++) {
if (arr[k]) { array.push(Number(arr[k])); }
}
// 计算数组长度以及平方根
var n = array.length;
var m = Math.sqrt(n);
// console.log('M', M, n, m)
// 重新整理为二维数组
var N = [], L = [];
N[0] = array.slice(0, n / 4);
N[1] = array.slice(n / 4, n / 2);
N[2] = array.slice(n / 2, n * 3 / 4);
N[3] = array.slice(n * 3 / 4, n);
for (var i = 0; i < m; i++) {
L[i] = [];
}
for (var l = 0; l < 4; l++) {
for (var i = 0; i < m / 2; i++) {
for (var j = 0; j < m / 2; j++) {
L[i + Math.floor(l / 2) * m / 2].push(N[l][j + i * m / 2]);
}
}
}
return L;
}
var n = A.length; // 获取长度
// 创建n×n矩阵C
var C = [];
for (var i = 0; i < n; i++) { C[i] = []; }
if (n === 1) {
// 若只有一个数,则返回乘积
C[0][0] = A[0][0] * B[0][0];
} else {
var m = parseInt(n / 2);
// 分割A为n/2矩阵[[A11, A12], [A21, A22]]
var A11 = getMatrix(A, 0, 0, m);
var A12 = getMatrix(A, m, 0, n - m);
var A21 = getMatrix(A, 0, m, n - m);
var A22 = getMatrix(A, m, m, m);
// 分割B为n/2矩阵[[B11, B12], [B21, B22]]
var B11 = getMatrix(B, 0, 0, m);
var B12 = getMatrix(B, m, 0, n - m);
var B21 = getMatrix(B, 0, m, n - m);
var B22 = getMatrix(B, m, m, m);
// 计算7个P矩阵
var P1 = squareMatrixMultiplyStrassen(addMatrix(A11, A22), addMatrix(B11, B22));
var P2 = squareMatrixMultiplyStrassen(addMatrix(A21, A22), B11);
var P3 = squareMatrixMultiplyStrassen(A11, addMatrix(B12, B22, 'minus'));
var P4 = squareMatrixMultiplyStrassen(A22, addMatrix(B21, B11, 'minus'));
var P5 = squareMatrixMultiplyStrassen(addMatrix(A11, A12), B22);
var P6 = squareMatrixMultiplyStrassen(addMatrix(A21, A11, 'minus'), addMatrix(B11, B12));
var P7 = squareMatrixMultiplyStrassen(addMatrix(A12, A22, 'minus'), addMatrix(B21, B22));
// 求出矩阵C,并返回
C[0][0] = convertMatrix(addMatrix(addMatrix(P1, P4), addMatrix(P5, P7, 'minus'), 'minus'));
C[0][1] = convertMatrix(addMatrix(P3, P5));
C[1][0] = convertMatrix(addMatrix(P2, P4));
C[1][1] = convertMatrix(addMatrix(addMatrix(P1, P3), addMatrix(P2, P6, 'minus'), 'minus'));
C = convertMatrix(C);
}
return C;
}
  • 验证
1
2
3
4
5
6
7
8
9
var AMatrix = [[1, 3], [7, 5]];
var BMatrix = [[6, 8], [4, 2]];
squareMatrixMultiplyStrassen(AMatrix, BMatrix);
// 输出[[18, 14], [62, 66]]
var AMatrix = [[1, 3, 2, 1], [7, 5, 1, 7], [1, 2, 3, 9], [2, 3, 1, 2]];
var BMatrix = [[6, 8, 2, 2], [4, 2, 2, 8], [2, 3, 1, 2], [7, 5, 1, 7]];
squareMatrixMultiplyStrassen(AMatrix, BMatrix);
// 输出[[29, 25, 11, 37], [113, 104, 32, 105], [83, 66, 18, 87], [40, 35, 13, 44]]

写着玩的,认真你就输了哈哈。

查看Github有更多内容噢:https://github.com/godbasin
更欢迎来被删的前端游乐场边撸猫边学前端噢

码生艰难,写文不易,给我家猪囤点猫粮了喵~

作者:被删

出处:https://godbasin.github.io

本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

文章目录
  1. 1. n×n矩阵计算
    1. 1.1. n×n矩阵
    2. 1.2. 基本js实现
    3. 1.3. 验证
  2. 2. 分治策略的矩阵算法
    1. 2.1. 直接的递归分治算法
    2. 2.2. 矩阵乘法的Strassen算法