468
Relations, Functions, and Matrices
Computing the various p i quantities requires 7 multiplications and 10 additions (counting subtractions as
additions). Computing the product C once the p i quantities exist takes 0 multiplications and an additional
8 additions. In total, computing C by this method requires 7 multiplications and 18 additions. Now take
two n × n matrices a and b and partition each of them into four (n∙2 × n∙2) matrices:
a = c
a 11 a 12
a 21 a 22
d
b = c
b 11 b 12
b 21 b 22
d
The product C = a # b is still given by Equation (1) using a ij and b ij instead of a ij and b ij , respectively.
Therefore Equation (2) still holds, and the product C requires 7 (n∙2 × n∙2) matrix multiplications. This
is an example of a divide and conquer algorithm, where the work has been reduced to several instances
of the same problem on a significantly reduced input size (although there is an additional overhead of 18
(n∙2 × n∙2) matrix additions).
Let M(n) represent the number of multiplications required for a product of two n × n matrices. Using
Strassen’s algorithm, we can write
M(1) = 1
(one multiplication in the product of two 1 × 1 matrices)
M(n) = 7M a
n
2
b
a. Solve this recurrence relation for M(n).
b. If A(n) represents the number of additions required for a product of two n × n matrices, justify the
following recurrence relation:
A(1) = 0
A(n) = 7Aa
n
2
b + 18a
n
2
b
2
c. Solve this recurrence relation to obtain an order-of-magnitude expression for A(n).
d. Find an approximate order-of-magnitude value for the total work (additions and multiplications) for
matrix multiplication using Strassen’s algorithm, and compare it with the Θ(n
3
) work (additions and
multiplications) for traditional matrix multiplication. (Although Strassen’s algorithm is theoretically an
improvement for all values of n, the constants that are ignored in an order-of-magnitude argument mean
that in actual implementation the traditional algorithm may run faster for values of n less than about
2
6
= 64).
55. The Gaussian elimination algorithm is labor-intensive. A worst-case analysis can be done simply by counting, where multiplications and additions are the units of work (divisions are counted as multiplications
and subtractions are counted as additions). Consider a system of n linear equations in n unknowns.
a. In the worst-case, the first non-zero element of each row of the augmented matrix as it is being transformed into upper triangular form is not 1 and that row must be multiplied by a non-zero scalar to create
a 1. Show that this requires a total of
(n + 1)(n + 2)
2
− 3
multiplications. (Hint: Consider Practice 7 in Chapter 2.)
b. Aside from the multiplications required in part (a), show that
2n
3
+ 3n
2
− 5n
6
multiplications and
2n
3
+ 3n
2
− 5n
6
additions are required to transform the augmented matrix into upper triangular form.
(Hint: Consider Exercise 11 in Section 2.2.)
Relations, Functions, and Matrices
Computing the various p i quantities requires 7 multiplications and 10 additions (counting subtractions as
additions). Computing the product C once the p i quantities exist takes 0 multiplications and an additional
8 additions. In total, computing C by this method requires 7 multiplications and 18 additions. Now take
two n × n matrices a and b and partition each of them into four (n∙2 × n∙2) matrices:
a = c
a 11 a 12
a 21 a 22
d
b = c
b 11 b 12
b 21 b 22
d
The product C = a # b is still given by Equation (1) using a ij and b ij instead of a ij and b ij , respectively.
Therefore Equation (2) still holds, and the product C requires 7 (n∙2 × n∙2) matrix multiplications. This
is an example of a divide and conquer algorithm, where the work has been reduced to several instances
of the same problem on a significantly reduced input size (although there is an additional overhead of 18
(n∙2 × n∙2) matrix additions).
Let M(n) represent the number of multiplications required for a product of two n × n matrices. Using
Strassen’s algorithm, we can write
M(1) = 1
(one multiplication in the product of two 1 × 1 matrices)
M(n) = 7M a
n
2
b
a. Solve this recurrence relation for M(n).
b. If A(n) represents the number of additions required for a product of two n × n matrices, justify the
following recurrence relation:
A(1) = 0
A(n) = 7Aa
n
2
b + 18a
n
2
b
2
c. Solve this recurrence relation to obtain an order-of-magnitude expression for A(n).
d. Find an approximate order-of-magnitude value for the total work (additions and multiplications) for
matrix multiplication using Strassen’s algorithm, and compare it with the Θ(n
3
) work (additions and
multiplications) for traditional matrix multiplication. (Although Strassen’s algorithm is theoretically an
improvement for all values of n, the constants that are ignored in an order-of-magnitude argument mean
that in actual implementation the traditional algorithm may run faster for values of n less than about
2
6
= 64).
55. The Gaussian elimination algorithm is labor-intensive. A worst-case analysis can be done simply by counting, where multiplications and additions are the units of work (divisions are counted as multiplications
and subtractions are counted as additions). Consider a system of n linear equations in n unknowns.
a. In the worst-case, the first non-zero element of each row of the augmented matrix as it is being transformed into upper triangular form is not 1 and that row must be multiplied by a non-zero scalar to create
a 1. Show that this requires a total of
(n + 1)(n + 2)
2
− 3
multiplications. (Hint: Consider Practice 7 in Chapter 2.)
b. Aside from the multiplications required in part (a), show that
2n
3
+ 3n
2
− 5n
6
multiplications and
2n
3
+ 3n
2
− 5n
6
additions are required to transform the augmented matrix into upper triangular form.
(Hint: Consider Exercise 11 in Section 2.2.)