2
$\begingroup$

I'm interested in learning about some of the algorithms available for multiplying non-square matrices, yet despite exhaustive Googling efforts I have been unable to find any discussions of such algorithms except for a couple of extremely general pieces of pseudocode that I found on Wikipedia and MIT OCW.

If anyone could pass on some links to papers that discuss these algorithms in greater detail, I would greatly appreciate it! Thanks!

|cite|improve this question
$\endgroup$
  • $\begingroup$ Hint: what are the dimensions for two matrices $A$ and $B$ such that $AB$ is defined? $\endgroup$ – Ryan Mar 22 '15 at 6:19
  • $\begingroup$ That's a pretty broad question. Can you be more specific? What's wrong with what you've found? Have you looked in textbooks? Are you looking for a straightforward algorithm, or one that uses blocking and other techniques to take into account the memory hierarchy and the size of cache lines? $\endgroup$ – D.W.♦ Mar 22 '15 at 6:44
  • $\begingroup$ @D.W. I'm basically looking for anything other than the basic iterative algorithm. The problem is that so far I've only found vague mentions of the existence of such algorithms and the "concept" behind how they use binary splitting to decompose rectangular matrices into smaller rectangular matrices for multiplication. I read that there's a generalization of Strassen's algorithm to rectangular matrices, but I can't find of precise description of its implementation anywhere. I saw mentions of such algorithms in the textbook by Vazirani/Dasgupta/Papadimitriou and various online resources. $\endgroup$ – Danny Mar 22 '15 at 6:58
3
$\begingroup$

There is an algorithm due to Coppersmith (later improved by him) that can multiply an $N \times N^\alpha$ matrix by an $N^\alpha \times N$ matrix in time $\tilde{O}(N^2)$ for some $\alpha > 0$. The state of the art in this regard is a paper by Le Gall achieving a better $\alpha$, though his algorithm is much more complicated than Coppersmith's. Both algorithms are probably impractical. Ryan Williams (Appendix C) explains how to implement Coppersmith's algorithm, which a priori is non-uniform, in the context of a circuit lower bound; later it was shown that Coppersmith's algorithm can be replaced by other ingredients.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ What is the meaning of $\tilde{O}(N)$? The Coppersmith papers and others seem to be about product of matrices with very specific rectangular proportions. Is that a way of providing a basic complexity brick to be used in decomposition of actual matrices, whether square or rectangular, when having to compute a product? $\endgroup$ – babou Mar 22 '15 at 17:10
  • 1
    $\begingroup$ Sorry, I forgot a square in the complexity. The tilde hides logarithmic factors. Le Gall's paper has non-trivial algorithms for all sizes of rectangular matrices. $\endgroup$ – Yuval Filmus Mar 22 '15 at 17:38
  • $\begingroup$ Thanks. I was wondering about the square, but since I did not understand the tilde .... How bad would it be to padd the matrices into equal size square matrices, then compute the product, then recorver whatever is useful in the resulting matrix? I realize it sounds silly, but how silly is it? $\endgroup$ – babou Mar 22 '15 at 18:12
  • $\begingroup$ It wouldn't be silly, but you can get better results by the more careful interpolation described in Le Gall's paper. It should be mentioned in his introduction. $\endgroup$ – Yuval Filmus Mar 22 '15 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.