Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was working on something on Matlab couple of months back and found a tweak to speed up Gauss elimination on Matlab by dividing the original matrix into 4 block matrices and then solving them in a block-wise fashion.

I am however wondering about couple of things.

  1. What is the reason for the optimal "split parameter" to be $\approx \frac{2}{3}$? Is there a heuristic or quick argument for this?

  2. Why is the number of additions independent of how we block partition the matrix?

share|improve this question

1 Answer 1

up vote 7 down vote accepted

Volker Strassen amazed the algorithmic world in 1969 by producing an $O(n^{\log_2 7})$ algorithm for matrix multiplication, based on a similar idea but applied recursively. The algorithm can also be adapted to matrix inversion and so to the solving of linear equations.

Since then, researchers have produced even better algorithms. The best known so far is by Coppersmith and Winograd (1987), who achieve $O(n^{2.376})$. Recent work suggests that matrix multiplication is actually possible in $O_\epsilon(n^{2+\epsilon})$ for any $\epsilon > 0$. Usually this is stated as $\omega = 2$, where $\omega$ is the infimum of all exponents $k$ such that matrix multiplication is possible in time $O(n^k)$.

Matrix multiplication is actually equivalent to matrix inversion, in the sense that they both have the same $\omega$. The proof can be found in the well-known CLRS.

All these algorithms - even Strassen's - are impractical (the constants hidden inside the big O are huge), and so never actually used. However, "blocking" is a wide-spread technique, since accessing memory "locally" is more efficient (due to the way caches work).

share|improve this answer
    
+1 for a very educational answer! –  M.B. Jan 24 '11 at 4:22
    
Yes. Here is an article (lehigh.edu/~gi02/m242/08linstras.pdf) which Moron posted as an answer to another question. This has the proof why Matrix Multiplication cost is same as Matrix Inversion. –  user17762 Jan 24 '11 at 4:54
    
There's some controversy whether Strassen is practical -- rjlipton.wordpress.com/2010/10/23/galactic-algorithms/… –  Yaroslav Bulatov Jan 24 '11 at 5:33
    
Here are Strassen's and Coppersmith/Winograd's articles. –  J. M. Apr 11 '11 at 2:08

Your Answer

 
discard

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