怎样修改矩阵乘法的strassen算法,它也可以用于大小不必为2的幂的...
发布网友
发布时间：2024-10-08 23:56
共2个回答
热心网友
时间：2024-10-25 16:09
首先最简单的：把矩阵补全成为2的幂次规模即可。由于矩阵乘法性质，就算扩大矩阵（补0），也会保留原有的结果，而其他部分为0，也就是说算完之后再从结果矩阵将需要部分扣下来即可。
其次稍微动脑子的：规定一个最小乘法规模m*m，当子问题小于该规模的时候，用普通矩阵乘法，于是问题转化为，把当前矩阵规模扩大为 p*p，满足 n*2^r = p, 且n < m，我们的目标就成了找到一组比较小的 n , r
但是，毕竟要追求卓越，实际问题中补成2次幂的代价往往很大，比如总共1.5T的空间,矩阵们 总共占了1T，最差情况我们要补成2T，显然不合理，因此扩充矩阵的条件只考虑判断奇偶性即可，在每一次递归计算的时候如果发现矩阵规模是奇数，我们把它+1补成偶数即可。
热心网友
时间：2024-10-25 16:09
热心网友
时间：2024-10-25 16:01
首先最简单的：把矩阵补全成为2的幂次规模即可。由于矩阵乘法性质，就算扩大矩阵（补0），也会保留原有的结果，而其他部分为0，也就是说算完之后再从结果矩阵将需要部分扣下来即可。
其次稍微动脑子的：规定一个最小乘法规模m*m，当子问题小于该规模的时候，用普通矩阵乘法，于是问题转化为，把当前矩阵规模扩大为 p*p，满足 n*2^r = p, 且n < m，我们的目标就成了找到一组比较小的 n , r
但是，毕竟要追求卓越，实际问题中补成2次幂的代价往往很大，比如总共1.5T的空间,矩阵们 总共占了1T，最差情况我们要补成2T，显然不合理，因此扩充矩阵的条件只考虑判断奇偶性即可，在每一次递归计算的时候如果发现矩阵规模是奇数，我们把它+1补成偶数即可。
热心网友
时间：2024-10-25 16:08
