MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## What is the computational complexity of matrix multiplication? [closed]

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.)

-
as someone pointed out in the other website, this cannot be done because the size of the output is linear in $p$. please ignore this silly question. – inquirer Jun 30 at 11:31
In view of the above commment, vote to close as no longer relevant. – quid Jun 30 at 12:03