Let $A_{nxn}$ be a given square matrix. Compute the number of multiplications and additions required to evaluate $A^{28}$ using

Let $A_{nxn}$ be a given square matrix. Compute the number of multiplications and additions required to evaluate $A^{28}$ using:
a) the naive method, $A^{28} = A * A * A *...* A$ (28 times)
b) $A^2, A^4 = A^2 . A^2,$ etc.

Solution

Number of multiplications required to calculate one element of product matrix $= n$
Number of additions required to calculate one element of product matrix $= n-1$

Let multiplications be x & additions be y.
Total number of operations to calculate one element of product matrix $= nx + (n-1)y$
Size of matrix $A_{n*n} = n * n = n^2$
Thus, total number of operations required to calculate all elements of the product matrix $= n^2 [nx + (n-1)y]$

Answer a:

Using Naive method, there will be 27 matrix multiplications to get $A^{28}$ .
Thus, total operations required for $A^{28}$ via naive method $= 27n^2[nx + (n-1)y]$

Answer b:

If we divide & conquer & store the intermediate results, it can be done via below steps:

$A^2 = A * A$
$A^4 = A^2 * A^2$
$A^8 = A^4 * A^4$
$A^{16} = A^8 * A^8$
$A^{12} = A^8 * A^4$
$A^{28} = A^{16} * A^{12}$

Total number of matrix multiplications required via this method to get $A^{28} = 6$
Thus, total operations required for $A^{28}$ via divide & conquer $= 6n^2[nx + (n-1)y]$

Subscribe to Ehan Ghalib!

Leave a Reply Cancel Reply