Strassen Algorithm for Unusal Matrices

Question

The Strassen algorithm is developed for multiplying the matrices faster. It enables us to reduce O(n^3) time complexity to O(n^2.81).

However, this algorithm is applied for the matrices which are square and the dimension of the matrices must be a power of 2.

Assume that the matrices are called A and B.

Problem 1: A = 3x3 B = 3x3

Problem 2: A = 2x3 B = 3x1

How can we apply Strassen algorithm to multiplication of these matrices ? The only thing which comes to mind is enlarging the matrices to convert them into square non matrices by adding zeros, which is called padding operation. However, I am not sure whether this method is proper or not.

Is there another method ?

Is my notion correct ?

Answer 1

Strassen's algorithm, when applied directly, only multiplies two square matrices of dimension $2^n$. You can use it to multiply two $m \times m$ matrices by finding the smallest power of 2 such that $m \leq 2^n$, padding your matrices to $2^n \times 2^n$, and using Strassen's algorithm. This results in an $O(m^{\log_2 7})$ algorithm.

When multiplying rectangular matrices using Strassen's algorithm, padding still works but the exponent might change. However, there are other algorithms which are more suitable for multiplying rectangular matrices. In particular, it is known that there is a constant $\alpha > 0$ such that multiplying an $n \times n^\alpha$ matrix by an $n^\alpha \times n$ matrix uses only $\tilde{O}(n^2)$ operations. These algorithms are probably impractical.

Finally, if you multiply small matrices as in your example, you shouldn't be using any fancy matrix multiplication method. Just use the usual algorithm. Strassen's algorithm is only worth it for very large matrices (if at all).

Answer 2

Almost the same as Yuval's answer, except...

If I gave you two 1025 x 1025 matrices, you wouldn't extend them to 2048 x 2048. You'd extend them to 1026 x 1026, and use one layer of Strassen's algorithm with 513 x 513 matrices - if you decided that this is faster than direct calculation of a 1025 x 1025 product. One recursion level lower, you'd decide whether your seven 513 x 513 products are faster to calculate directly or as a 514 x 514 product using one layer of Strassen's algorithm and so on.

I very much doubt that Strassen's algorithm will be an improvement for 65 x 65 products. There are fewer floating-point operations, but probably a lot more overhead.

For non-square matrices: If you want to multiply a (100x100) by a (1000x100) matrix, that can be done trivially by calculating ten (100x100) x (100x100) products. Filling up to 1000x1000 would be madness.