Given two rectangular matrices $A_{n \times m}$ and $B_{m \times r}$ where $n \neq m, \ m \neq r$ and $ r, \ m < n$. Mathematically, is it possible to convert $A$ and $B$ to $A^{\prime}_{n \times n}$ and $B^{\prime}_{n \times n}$ such that $A^{\prime}_{n \times n}$ and $B^{\prime}_{n \times n}$ hold the same information as $A$ and $B$ but with zero-padding?

I am asking this because I would like to implement the Coppersmith-Winograd Algorithm which offers $\mathcal{O}(n^{2.38})$ instead of the ordinary $\mathcal{O}(n^{3})$ matrix multiplication complexity. The algorithm only works on $n \times n$ matrices.

If so, what are the precautions I need to be taking care of?


1 Answer 1


Simply adding out $\ A\ $ with extra zero columns, and $\ B\ $ with extra zero rows won't change the product. That is, if you put $$ A'=\pmatrix{A&0_{n\times(n-m)}}\ $$ and $$ B'=\pmatrix{B\\0_{(n-r)\times n}}\ , $$ then $\ A'\ $ and $\ B'\ $ are $\ n\times n\ $ square matrices with $\ A'B'=AB\ $.

According to the Wikipedia article you linked to, the Coppersmith-Winograd Algorithm is only faster than the Strassen algorithm for matrices that are so enormous that they can't be handled by any computers available today, so you're probably going to better off using the latter algorithm.

  • $\begingroup$ Thank you so much! Congrats on the 7k points! $\endgroup$ Apr 3, 2020 at 16:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .