Finding the Closest Pair of Points Problem: Given n ordered pairs x1, y



Download 59 Kb.
Page10/10
Date16.05.2021
Size59 Kb.
1   2   3   4   5   6   7   8   9   10
q1 = (a11 + a22) * (b11 + b22)

q2 = (a21 + a22) * b11

q3 = a11*( b12 – b22)

q4 = a22 * (b21 – b11)

q5 = (a11 + a12) * b22

q6 = (a21 – a11) * (b11 + b12)

q7 = (a12 – a22) * (b21 + b22)
It turns out that
c11 = q1 + q4 – q5 + q7

c12 = q3 + q5

c21 = q2 + q4

c22 = q1 + q3 – q2 + q6
Note: I haven't actually looked at Strassen's paper. This is just from the text. In going through other books, I saw a different set of products than these. (I also saw these in other books too though.) The different set of products I saw required 24 additions instead of 18, so this is a slight improvement (though not asymptotic) over the other algorithm I saw in a different book.
Let's verify a couple of these:
q1 + q4 – q5 + q7 = (a11 + a22) * (b11 + b22) + a22 * (b21 – b11)

(a11 + a12) * b22 + (a12 – a22) * (b21 + b22)


= a11b11 + a11b22 + a22b11 + a22b22 + a22b21 – a22b11 – a11b22 – a12b22

+ a12b21 + a12b22 – a22b21 – a22b22
= a11b11 + a12b21 , since everything else cancels out.
q3 + q5 = a11*( b12 – b22) + (a11 + a12) * b22

= a11b12 – a11b22 + a11b22 + a12b22

= a11b12 + a12b22
I have no idea how Strassen came up with these combinations. He probably realized that he wanted to determine each element in the product using less than 8 multiplications. From there, he probably just played around with it. In the algorithms text by Cormen, Leiserson and Rivest, they show how one could derive these products.
If we let T(n) be the running time of Strassen's algorithm, then it satisfies the following recurrence relation:
T(n) = 7T(n/2) + O(n2)


It's important to note that the hidden constant in the O(n2) term is larger than the corresponding constant for the standard divide and conquer algorithm for this problem. However, for large matrices this algorithm yields an improvement over the standard one with respect to time.


Share with your friends:
1   2   3   4   5   6   7   8   9   10




The database is protected by copyright ©essaydocs.org 2020
send message

    Main page