我有两个矩阵,其中第一个矩阵是根据第二个矩阵的数据创建的,用于转换第二个矩阵。我多次重复这个操作。由于这两个矩阵的依赖关系,我一直没能在这里找到加速运算的方法。我会尝试用小矩阵向您展示我在说什么。
[ 1 0 0 0 ] [ .11 .22 .33 .44 ]
[ 0 1 0 0 ] [ .65 .42 .01 .92 ]
[ 0 0 .51^2 .85^2 ] * [ .31 .15 .51 .85 ]
[ 0 0 .44^2 .23^2 ] [ .25 .78 .44 .23 ]
A B
假设我做了数百万次这个操作,并且计算值在 A 中的位置取决于我希望在 B 中发生旋转的位置。因此,在每次迭代中矩阵 A 和 B 是不同的,并且使用的值计算要放入 A 的新值是不同的。
有谁知道加速此类代码的方法吗?考虑到矩阵乘法本质上是 vector 矩阵乘法,我希望创建一个组合 A(展开到 A 是一个完整矩阵的点,或者足够充分以利用 MMM 算法),但是新值的数据依赖性使得看来我可能被卡住了。我得到这样的东西:
A * B = B'
A' * B' = B''
A'' * B'' = B'''
其中 A' 派生自 B',A'' 派生自 B'',依此类推。
编辑:
澄清一下,第二轮可以是:
[ 1 0 0 0 ] [ .11 .22 .33 .44 ]
[ 0 .65^2 .42^2 0 ] [ .65 .42 .01 .92 ]
[ 0 .26^2 .60^2 0 ] * [ .26 .60 .45 .39 ]
[ 0 0 0 1 ] [ .06 .04 .10 .17 ]
A' B'
最佳答案
当矩阵 A[rows][num]
乘以矩阵 B[num][cols]
时,结果矩阵 C[rows] 中的每个元素[cols]
是
C[r][c] = A[r][0]*B[0][c] + ... + A[r][num-1]*B[num-1][c]
= sum( A[r][k] * B[k][c], k = 0 .. num-1 )
这里,A
是一个单位矩阵,除了两行(r0
和 r1
),每行在两列中有两个值( c0
和 c1
)。因为行 r0
和 r1
否则为零,结果矩阵 C
中这些行上的每个元素都是两个乘积的和:
C[r0][i] = A[r0][c0] * B[c0][i] + A[r0][c1] * B[c1][i]
C[r1][i] = A[r1][c0] * B[c0][i] + A[r1][c1] * B[c1][i]
并且由于 A
是单位矩阵,结果中的所有其他行与 B
矩阵中的对应行相同。
如果我们使用
a00 = A[r0][c0] a01 = A[r0][c1]
a10 = A[r1][c0] a11 = A[r1][c1]
那么我们可以将更新循环描述为
For i = 0 .. cols-1
C[r0][i] = a00 * B[c0][i] + a01 * B[c1][i]
C[r1][i] = a10 * B[c0][i] + a11 * B[c1][i]
End for
如果我们在更新循环中使用两个临时变量(在 c0 == r0
或 c1 == r0
的情况下,这样我们就不会覆盖 [r0][i]
在我们计算 [r1][i]
处的元素之前),整个操作可以就地完成,仅使用 B
矩阵。
如果左矩阵A
中的非恒等元元素是矩阵B
中相应元素的平方,我们就地更新,就变得很简单了。在 C99 中:
#include <stdlib.h>
void update(const size_t n, double B[n][n], const size_t r, const size_t c)
{
const double a00 = B[r ][c ] * B[r ][c ];
const double a01 = B[r ][c+1] * B[r ][c+1];
const double a10 = B[r+1][c ] * B[r+1][c ];
const double a11 = B[r+1][c+1] * B[r+1][c+1];
size_t i;
for (i = 0; i < n; i++) {
const double b0i = B[c ][i];
const double b1i = B[c+1][i];
B[r ][i] = a00 * b0i + a01 * b1i;
B[r+1][i] = a10 * b0i + a11 * b1i;
}
}
上述操作的计算成本是4*n+4
次乘法和2*n
次加法(矩阵元素),即O(N) .
这种方法同样适用于Givens和 Jacobi旋转,除了不是使用给定矩阵计算四个元素,而是根据传递给函数的参数计算它们;需要传递两个单独的行和两列参数,而不是连续的行和列。
关于c - 有什么办法可以减少这两个相依矩阵之间的运算吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43562493/