Winograd矩阵乘法算法用于任意阶矩阵时的一种新处理方法

A New Scheme to Divide Odd-sized Matrices for the Winograd's Algorithm

摘要t矩阵乘法StraSsen算法及其变形winograd算法用分而治之的方法把矩阵乘法时间复杂性由传统的D(n。)改进到0(佗kg。n.但是对于奇数阶矩阵,在划分子矩阵时,要作特殊处理才能继续使用此算法.本文提出了一种非等阶“十”字架划分方法,可以最少化填零,最大化性能,使得奇数阶矩阵乘法的时间复杂性更加接近偶数阶矩阵乘法的效果.计算实例显示该方法是有效的.

Winograd's algorithm achieves its lower complexity by using a divide-and-conquer approach, but the division step must handle odd-sized matrices. We report on a dynamic cross scheme to handle odd-sized matrices, it minimizes padding and maximizes the performance of the algorithm. Performance comparisons of our scheme with that of competing schemes show that our scheme often outperforms the alternative ones.