Now that we have seen that the divide-and-conquer approach can reduce the number of one-digit multiplications in multiplying two integers, we should not be surprised that a similar feat can be accomplished for multiplying matrices.

**Multiplication of Large Integers and ****Strassenâ€™s Matrix Multiplication**

In this section, we examine two surprising algorithms for seemingly straightfor-ward tasks: multiplying two integers and multiplying two square matrices. Both achieve a better asymptotic efficiency by ingenious application of the divide-and-conquer technique.

**Strassenâ€™s
Matrix Multiplication**

Now that
we have seen that the divide-and-conquer approach can reduce the number of
one-digit multiplications in multiplying two integers, we should not be
surprised that a similar feat can be accomplished for multiplying matrices.
Such an algorithm was published by V. Strassen in 1969 [Str69]. The principal
insight of the algorithm lies in the discovery that we can find the product ** C** of two 2 Ã— 2 matrices

Thus, to
multiply two 2 Ã— 2
matrices, Strassenâ€™s algorithm makes seven multipli-cations and 18
additions/subtractions, whereas the brute-force algorithm requires eight
multiplications and four additions. These numbers should not lead us to
multiplying 2 Ã— 2
matrices by Strassenâ€™s algorithm. Its importance stems from its *asymptotic *superiority as matrix order* **n** *goes to infinity.

Let ** A** and

It is not
difficult to verify that one can treat these submatrices as numbers to get the
correct product. For example, *C*_{00} can be
computed either as *A*_{00} âˆ— *B*_{00} +

*A*_{01}** **âˆ—

If the
seven products of ** n/**2 Ã—

Let us
evaluate the asymptotic efficiency of this algorithm. If ** M(n)** is the number of multiplications
made by Strassenâ€™s algorithm in multiplying two

which is
smaller than *n*^{3} required
by the brute-force algorithm.

Since
this savings in the number of multiplications was achieved at the expense of
making extra additions, we must check the number of additions ** A(n)** made by Strassenâ€™s algorithm. To
multiply two matrices of order

simply
multiplied. These observations yield the following recurrence relation:

** A(n) **=

Though
one can obtain a closed-form solution to this recurrence (see Problem 8 in this
sectionâ€™s exercises), here we simply establish the solutionâ€™s order of growth.
According to the Master Theorem, ** A(n)** âˆˆ

Since the
time of Strassenâ€™s discovery, several other algorithms for multiplying two ** n** Ã—

**Exercises
5.4**

**
**What are the smallest and largest numbers of digits
the product of two decimal ** n**-digit
integers can have?

**
**Compute 2101 âˆ— 1130 by
applying the divide-and-conquer algorithm outlined in the text.

**
****a. **Prove the equality** ***a*^{log}^{b}** **^{c}** **=** ***c*^{log}^{b}** ****^{a}**, which was used in Section 5.4.

**
**Why is *n*^{log2} ^{3}
better than 3^{log2} **^{n}** as a
closed-form formula for

**
****a. **Why did
we not include multiplications by 10^{n}** **in the multiplication count** **** M(n)
**of the
large-integer multiplication algorithm?

**
**In addition to assuming that ** n** is a power of 2, we made, for
the sake of simplicity, another, more subtle, assumption in setting up the
recurrences for

**
**How many one-digit additions are made by the
pen-and-pencil algorithm in multiplying two ** n**-digit
integers? You may disregard potential carries.

Verify
the formulas underlying Strassenâ€™s algorithm for multiplying 2 Ã— 2 matrices.

**7. **Apply Strassenâ€™s algorithm to
compute

exiting the recursion when ** n** = 2

**
**Solve the recurrence for the number of additions
required by Strassenâ€™s algo-rithm. Assume that ** n** is a
power of 2.

**
**V. Pan [Pan78] has discovered a divide-and-conquer
matrix multiplication algorithm that is based on multiplying two 70 Ã— 70 matrices using 143,640
multiplications. Find the asymptotic efficiency of Panâ€™s algorithm (you may
ignore additions) and compare it with that of Strassenâ€™s algorithm.

**
**Practical implementations of Strassenâ€™s algorithm
usually switch to the brute-force method after matrix sizes become smaller than
some crossover point. Run an experiment to determine such a crossover point on
your computer system.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Divide and Conquer : Strassenâ€™s Matrix Multiplication |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.