Clever Geek Handbook

How many floating point operations are there for Strassen's algorithm for a kxk matrix?

I am trying to understand this analysis of Strassen's algorithm for kxk matrix multiplication. But I'm still not too sure how many operations were processed. Can someone help clarify this?

+2


source to share


2 answers


The number of operations performed is determined as follows. First, we split the matrix into four k / 2 steps, and then perform seven recursive multiplications of those matrices. We then make a constant number of additions of these products to get the desired result. This gives us a recurrence relationship defined as follows:

T (1) = 1

T (k) = 7T (k / 2) + ck 2



Note that lg 7> 2, since lg 7> lg 4 = 2. (Here lg is the binary logarithm). Thus, in the case of one of the Master Theorem, the asymptotic complexity of the algorithm is O (k lg 7 ) & asymptotic; O (to 2.807 ).

Hope this helps!

+2


source


Given that the page states that this is approximately O (N ^ 2.807 ...), I would assume that this would be a good approximation of the number of floating point operations. All loop / iteration operations will be performed on whole operations.



0


source






More articles:


All Articles