Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Do you really want to delete this prezi?
Neither you, nor the coeditors you shared it with will be able to recover it again.
Make your likes visible on Facebook?
You can change this under Settings & Account at any time.
Divide and Conquer: Multiplication of Large Integers and Strassen's Matrix Multiplication
Transcript of Divide and Conquer: Multiplication of Large Integers and Strassen's Matrix Multiplication
Large Integers To demonstrate the basic idea of the algorithm, let us start with a case of two-digit integers, say, 23 and 14. These numbers can be represented as follows: and Now let us multiply them: We can compute the middle term with just one digit multiplication by taking advantage of the products 2 * 1 and 3 * 4 that need to computed anyway: For any pair of two-digit numbers and their product c can be computed by the formula where is the product of their first digits, is the product of their second digits, is the product of the sum of the a's digits and the sum of b's digit minus the sum of and First Divide-and-Conquer Algorithm A small example: A B where A = 2135 and B = 4014 So, In general, if and (where A and B are n-digit, are n/2-digit numbers), Recurrence for the number of one-digit multiplications M(n):
M(n) = 4M(n/2), M(1) = 1 Solution: M(n) = Efficiency: one-digit multiplications Second Divide-and-Conquer Algorithm The idea is to decrease the number of multiplications from 4 to 3: I.e., which requires only 3 multiplications at the expense of (4-1) extra add/sub. Recurrence for the number of multiplications M(n):
M(n) = 3M(n/2), M(1) = 1 Solution: Strassen's Matrix
Multiplication The principal insight of the algorithm lies in the discovery that we can find the product C of two 2 X 2 matrices A and B with just seven multiplications as opposed to the eight required by the brute-force algorithm. This is accomplished by using the following formulas: where Let A and B be two n x n matrices where n is a power of 2. (If n is not a power of 2, matrices can be padded with rows and columns of zeros.) We can divide A, B, and their product C into four n/2 x n/2 submatrices each as follows: It is not difficult to verify that one can treat these submatrices as numbers to get the correct product. Analysis of Strassen’s Algorithm If n is not a power of 2, matrices can be padded with zeros. Number of multiplications: M(n) = 7M(n/2), M(1) = 1 Solution: vs. of brute-force alg. Algorithms with better asymptotic efficiency are known but they are even more complex. Multiplication of large integers video