How many counting operations are for matrix exponential?

Question

Let A be a m x m matrix and

$$\sum_{k=0}^n \frac{A^k}{k!}$$

I have this following flops count:

For $A^k$, $(n-1)(2m^3-m^2)$ flops
$n$ multiplications for $k!$
$n$ divisions for $\frac{A^k}{k!}$
$n-1$ additions for the summation

So the total is $(3n - 1) + (n-1)(2m^3-m^2)$ flops. Is it correct?

You might want to use the Horner scheme $I+A(I+A/2(I+A/3(...(I+A/n)...)))$, it should not change the count too much. But note that the divisions and matrix additions are element-wise, also in your step 3 and 4. — Lutz Lehmann, Jun 06 '19 at 20:21
@LutzL what are the implications if the divisions and matrix additions are element-wise? — Joshua Leung, Jun 06 '19 at 20:27

score 1 · Answer 1 · answered Jun 06 '19 at 20:25

1

Let's slow down a bit and count summand by summand: \begin{array}{lll} \mbox{summand} & \mbox{multiplications required, using prev. results} & \mbox{some prev. results}\\ \hline {1 \over 2!} A^2 & 1 + m^3 + m^2 & \\ \\ {1 \over 3!} A^3 & 1 + m^3 + m^2 \; \mbox{(as $A^3 = A^2 A$, i.e., $m^3$ multiplications)} & {1 \over 2!}, \; A^2 \\ \\ {1 \over 4!} A^4 & 1 + m^3 + m^2 \; \mbox{(as $A^4 = A^3 A$, i.e., $m^3$ multiplications)} & {1 \over 3!}, \; A^3 \\ \\ \end{array} Am I missing something?

answered Jun 06 '19 at 20:25

avs

6,276

So $\frac{1}{k!}A^k = \frac{1}{k}A \times (\frac{1}{(k-1)!}A^{k-1})$?? – Joshua Leung Jun 06 '19 at 20:42
Yes. The matrix commutes with itself and with all scalars, right? So, we can save a lot of computations by re-using previously computed results. – avs Jun 06 '19 at 20:53
does this affect the flop count though? – Joshua Leung Jun 06 '19 at 21:02
It means, once you have $A^{k-1}$, you can get $A^k$ by performing just one matrix multiplication ($m^3$ flops). – avs Jun 06 '19 at 23:32

How many counting operations are for matrix exponential?

1 Answers1