Re: the competition's expm vs ours

[Jaroslav Hajek]

On Wed, Dec 3, 2008 at 1:10 AM, Jordi Gutiérrez Hermoso
<address@hidden> wrote:
> 2008/12/1 Marco Caliari <address@hidden>:
>> On my laptop, I got the following results for a 500x500 matrix:
>>
>> Octave 3.0.3 (with ATLAS): 4.3 seconds
>> Octave 3.0.3, removing the extra steps: 4.0 seconds
>> Matlab 7.6.0: 1.2 seconds
>> Octave 3.0.3, rewriting in a better way the Pade' approximation (and with
>> the extra steps): 3.7 seconds
>>
>> So, I don't think the extra steps produce the difference and they are
>> suggested also in "The scaling and squaring method for the matrix
>> exponential revisited" by N.J. Higham.
>
> Hrm... Are you using sources that incorporate Jaroslav's indexing
> improvements? I guess we could profile Octave to see where the actual
> slowdown is instead of guessing...
>
> - Jordi G. H.
>

Another slowdown in the m-file is caused by the fact that the expressions
E = DS*E/DS;
E = DP*E*DP';
are calculated using dense matrix arithmetic.

See also my recent post about optimized treatment of diagonal matrices
(not yet in Nabble).
I think after the diagonal & permutation matrix optimizations are
applied, I think we can contribute an m-file version of expm based on
the source Marco presented.
I see at least one futher significant optimization that can be done
(and applies to the C++ version as well).

cheers

-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz