Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I am looking for information about the computational complexity of matrix multiplication 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$, 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.

Any ideas?

Thanks.

Note: the reason I am hoping for it to be possible is because of the well known result of less than cubic dependence in $p$ if $m=n=p$ (when matrices are all squares).

share|improve this question
8  
A (sequential) algorithm's complexity cannot be smaller than the size of its output. For your problem can you represent the input and output using space that is sublinear in p? –  Colin McQuillan Jun 30 '12 at 11:17
    
are the elements mostly nonzero or often zero? ie sparse? that certainly leads to various optimizations. also it seems like the SVD [singular value decomposition] might be relevant based on the current response referring to approximations. –  vzn Jul 3 '12 at 4:44

1 Answer 1

Classical work of Coppersmith shows that for some $\alpha > 0$, one can multiply an $n \times n^\alpha$ matrix with an $n^\alpha \times n$ matrix in $\tilde{O}(n^2)$ arithmetic operations. This is a crucial ingredient of Ryan Williams's recent celebrated result.

François le Gall recently improved on Coppersmith's work, and his paper has just been accepted to FOCS 2012. In order to understand this work, you will need some knowledge of algebraic complexity theory. Virginia Williams's paper contains some relevant pointers. In particular, Coppersmith's work is completely described in Algebraic Complexity Theory, the book.

A different strand of work concentrates on multiplying matrices approximately. You can check this work by Magen and Zouzias. This is useful for handling really large matrices, say multiplying an $n \times N$ matrix and an $N \times n$ matrix, where $N \gg n$.

The basic approach is to sample the matrices (this corresponds to a randomized dimensionality reduction), and multiplying the much smaller sampled matrices. The trick is to find out when and in what sense this gives a good approximation. In contrast to the previous strand of work which is completely impractical, sampling algorithms are practical and even necessary for handling large amounts of data.

share|improve this answer
    
Just a note: it is known (as of November 2010) that rectangular matrix multiplication isn't necessary for solving ACC SAT. (Which is good, because rectangular matrix mult is "galactic" and complex.) –  Ryan Williams Nov 21 '12 at 19:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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