Re: the competition's expm vs ours

[A. Scottedward Hodel]

On Nov 25, 2008, at 10:56 AM, Jordi Gutiérrez Hermoso wrote:

2008/11/22 Marco Caliari <address@hidden>:

In Octave expm there are first some "reductions" (trace reduction

and balancing) and then Pade' approximation (8,8) with scaling and

squaring.  On the other hand, Matlab does not make any reductions

and uses Pade' approximation (6,6) with scaling and squaring

Thank you for the explanation. Now, am I correct in inferring that the
extra steps that Octave does for this function (whose implementation I
think I finally found after Doxygenising the sources, yay!) produce a
noticeable performance hit as compared to Matlab's? Is this
performance hit acceptable?

- Jordi G. H.

I implemented Octave's expm function over 10 or so years ago, based on "Nineteen Dubious Ways to Compute the Matrix Exponential" (1978) by Moler and Van Loan. This paper was recently revisited although I don't have the reference handy.

Trace reduction, balancing, and scaling and squaring are preconditioners that are useful (and sometimes essential) to obtain good numerical accuracy.  The use of an 8th order diagonal Padé approximation vs 6th (or 3rd) is somewhat arbitrary.  (Padé approximations require about half of the flops of a comparable accuracy Taylor Series expansion.)  The first two preconditioners (and their back-transforms) require O(n^2) flops, if I remember right.  The Padé approximations and squaring (the inverse of scaling) require O(n^3) flops.  

Scaling and squaring is essential for any matrix with norm greater than 1 due to the behavior of a truncated Taylor series; see Moler and  van Loan's paper for more details.    Squaring adds log_2(||A||) matrix multiplies --- O(n^3) flops --- to the process.  Balancing and trace reduction often (but not always) help to reduce the norm of a matrix at relatively low numerical cost.

Once you've read Moler and  van Loan's paper, you'll know as much about expm as I do.

A. Scottedward Hodel address@hidden

http://homepage.mac.com/hodelas/tar

molvan78

Nineteen Dubious Ways to Compute the Exponential of a Matrix (article)

Author

C. Moler and C. {Van Loan}

Journal

SIAM Review

Year

1978

Month

October

Number

4

Pages

801–836

Volume

20