Search code examples
algorithmmatrixdivide-and-conquer

Divide and conquer on rectangular matrices

I apologize for the vagueness of this question, but I'm trying to ascertain a way to perform divide and conquer multiplication of rectangular matrices A and B such that A = n x m and B = m x p

I've done a bit of reading and Strassen's method seems promising, but I can't determine how I would use this algorithm on rectangular matrices. I've seen some people refer to "padding" with zeros to make both matrices square and then "unpadding" the result, but I'm not clear on what the unpadding stage would entail.

Thank you for your advice!

Solution

  • The result matrix is going to contain zeros on all items that were "added" to operand matrices. To get back to your rectangular result, you would just crop the result, i.e. take upper left corner of the result matrix based on dimensions of operands.

    However, padding by itself seems to be wise only in cases where n, m and p are very close. When these are disproportionate, you are going to lot of zero matrix multiplication.

    For example if n = 2m = p, Strassen's algorithm is going to divide multiplication into 7 multiplications of m-size matrices. However, 4 of these multiplications would involve zero matrices and are not necessary.

    I think there are two ways how to improve the performance:

    • Use padding and remember which part of matrix is padded. Then for each multiplication step check whether you are not multiplying by a zero matrix. If you do, the result would also be a zero matrix, no need to compute that. This would remove most of the cost involved with padding.
    • Do not use padding. NonSquare_Strassen: Divide the rectangular matrices into square regions and a remainders. Run vanilla Strassen on square regions. Run NonSquareStrassen again on the remainders. Afterwards, combine these results. This algorithm will be most likely faster than the first, but not entirely easy to implement. However, the logic will be quite similar to Strassen's algorithm for square matrices.

    For the sake of simplicity I would choose the first option.

    Note: Remember that you can use Strassen's approach also for rectangular matrices and that below certain matrix size, O(n^2) cost of additional matrix additions becomes more significant and it's better to finish small sizes using normal cubic multiplication. This means that the Strassen's approach is still quite easy to implement for non-square matrices. The above expects that you have the algorithm for square matrices already implemented.