most recent 30 from http://mathoverflow.net 2013-05-19T17:47:30Z http://mathoverflow.net/feeds/question/100993 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/100993/what-is-the-computational-complexity-of-matrix-multiplication inquirer 2012-06-30T11:12:16Z 2012-06-30T11:12:16Z

<p>I am looking for information about the computational complexity of matrix multiplication of specific type of rectangular matrices. Wikipedia states that the complexity of multiplying $A \in \mathbb{R}^{m \times n}$ by $B \in \mathbb{R}^{n \times p}$ is $O(mnp)$ (schoolbook multiplication).</p> <p>I have a case where $m$ and $n$ are much smaller than $p$ (in fact, they are constant, while $p$ is arbitrary), and I was hoping to get better complexity than linear in $p$, on the expense of making the dependence on $m$ and $n$ worse than linear.</p> <p>I am not optimistic about being able to find an algorithm for this. It seems like algorithms for rectangular matrix multiplication usually focus on the case where $m=n$ and $p &lt;&lt; n$ (such as the paper here: <a href="http://www.sciencedirect.com/science/article/pii/S0885064X97904386" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S0885064X97904386</a>).</p> <p>Any ideas?</p> <p>Thanks.</p> <p>(I also posted the question to here <a href="http://cstheory.stackexchange.com/questions/11891/the-computational-complexity-of-matrix-multiplication" rel="nofollow">http://cstheory.stackexchange.com/questions/11891/the-computational-complexity-of-matrix-multiplication</a>, but when google led me to similar questions here, I thought I would try it over here as well.)</p>