Computing number of flops
2 views (last 30 days)
Show older comments
Let A in R^{nxn}.
(a) Compute the number of flops needed to compute A^k using matrix-matrix multiplications.
(b) Assuming that A = VDV ^{-1} where V^{-1} is given and D is a diagonal matrix, propose a different procedure to compute A^k that requires less flops. Compute the number of flops.
a) So we have k square matrices. Computing element aij of A^k requires taking the dot product of row i in the first matrix A and column j in the subsequent matrix A. Computing the dot product requires n multiplications and n−1 additions. Since there are n^2 elements, the dot product must be computed n^2 times.
Thus the total number of operations is n^2(n+(n−1))=2n^3−n^2=O(n3). But since we are doing the procedur k-times, then the number of flops = k(2n^3 - n^2). Is it correct?
b) what about it? What is the answer?
0 Comments
Answers (0)
See Also
Categories
Find more on Matrix Indexing in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!