Bug 46: Winograd Done Bad
- Winograd's algorithm for matrix multiplication roughly halves the number of scalar multiplications.
- This code multiplies two input matrices (mk times kn) and adds the result to a third input matrix (mn).
- Row-major: mk has m rows and k columns, kn has k rows and n columns, mn has m rows and n columns.
- Winograd multiplies a pair of row elements with a pair of column elements using 1 scalar multiplication.
- The trick: (row1 * col1) + (row2 * col2) = (row1 + col2) * (row2 + col1) - (row1 * row2) - (col1 * col2)
- For each mk row, it prepares a sum of (row1 * row2) for disjoint pairs of consecutive scalars row1, row2.
- For each kn column, it prepares a sum of (col1 * col2) for disjoint pairs of consecutive scalars col1, col2.
- These prepared sums are reused many times, as each row of mk is multiplied with every column of kn.
Fix The Tiny Bug In This Go Code: