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.

According to Wikipedia, Strassen's Algorithm runs in $O(N^{2.807})$ time. Has anyone seen a more rigorous analysis displaying constants, possibly in a specific language such as C or Java?

I realize this will vary from language to language, machine to machine etc, but does anyone know of an approximate input size where Strassen's algorithm starts to outperform regular matrix multiplication?

I think this may belong on the computer science stack exchange but since it is somewhat mathematical I thought I would post it here.

share|improve this question
1  
The 'rigorous' analysis won't depend on the specific implementation language. There are too many vagaries in computer languages, and anyway they end up not contributing much one way or the other to the analysis. Most references for such algorithm analysis will just look at the recurrence and try to extract constants and lower order terms from the Master Method. –  Mitch Feb 16 '11 at 3:18
add comment

2 Answers 2

up vote 11 down vote accepted

I suggest that you have a look at the easily readable original article here (probably you need a university subscription), and the MR review is here. Since Strassen's algorithm is quite famous, I would be surprised if it were difficult to find a detailed analysis in various dialects by googling a little.

The roughly is in fact precisely $\log_{2}{7} \approx 2.807$.

In order to multiply two $n \times n$ matrices in the usual way you need $n^{3}$ multiplications and $n^{2}(n-1)$ additions, so in total you need $n^2 (2n-1)$ arithmetical operations. Strassen's algorithm (in his own analysis) gets away with less than $4.7 n^{\log_{2} 7}$ arithmetical operations (provided $n \geq 16$ if I'm not completely mistaken), and this should be better for all such $n$.

I don't see any other "costly" thing than addition and multiplication in an implementation. The amount of memory needed should also be rather easy to figure out from Strassen's description, but it should be of order $4 n^2$.

share|improve this answer
    
how is the number of mutiplications n^3 and the number of additions n^2(n-1) . Can you explain please ? –  Geek Aug 3 '12 at 4:48
    
The formula for the $(i,j)$ entry of $AB$ is $(AB)_{ij} = \sum_{k=1}^n A_{ik}B_{kj}$. It involves $n$ multiplications and $(n-1)$ additions of scalars. Now you have $n^2$ entries $(i,j)$ with $1 \leq i, j \leq n$ of $(AB)_{ij}$, so in total you have $n^2 \cdot n = n^3$ multiplications and $n^{2}(n-1)$ additions of scalars to perform. –  t.b. Aug 3 '12 at 6:18
1  
@Geek: was that clear enough? Look at the case of two $4 \times 4$-matrices $A = (A_{ij})_{i,j=1}^4$ and $B = (B_{ij})_{k,j=1}^4$. Then the $(i,j)$-entry of the matrix $AB$ is $$A_{i1} B_{1j} + A_{i2}B_{2j} + A_{i3}B_{3j} + A_{i4}B_{4j}$$ so you have to perform $4 = n$ multiplications and $3 = (n-1)$ additions to compute it. You have to do such computations for each of the $4 \times 4 = n^2$ entries of $AB$. In total $64 = (4 \times 4) \times 4 = n^3$ multiplications and $48 = (4 \times 4) \times 3 = n^2 (n-1)$ additions. –  t.b. Aug 3 '12 at 12:48
    
@tb thanks . +1. –  Geek Aug 3 '12 at 16:50
    
I have asked another question here on Strassen Algorithm . –  Geek Aug 3 '12 at 17:05
add comment

From a google search [crossover strassen matrix multiplication], I've found that experiments have found the crossover point to be from n = 8 to n = 20.

However, at some point in analysis of algorithms you jump from manipulating mathematical concepts straight to just running things experimentally and recording values and times. At that point it is not really called analysis of algorithms, but instead plain old engineering where you manipulate things other than the basic algorithm (agressively optimizing compiling, caching strategies, the speed of memory components, hardware parallelization, the cooling system, etc). Then the variables to consider are too many and underspecified to make an analytic (on paper) calculation, and you just have to compare using runtime data.

share|improve this answer
add comment

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.