Computing number of flops

3 次查看（过去 30 天）

Pascale Bou Chahine 2020-9-23

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/598714-computing-number-of-flops

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?