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).
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.
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 << n$ (such as the paper here: http://www.sciencedirect.com/science/article/pii/S0885064X97904386).
Any ideas?
Thanks.
(I also posted the question to here http://cstheory.stackexchange.com/questions/11891/the-computational-complexity-of-matrix-multiplication, but when google led me to similar questions here, I thought I would try it over here as well.)
