the competition's expm vs ours

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

the competition's expm vs ours

Jordi Gutiérrez Hermoso
I just ran into a "benchmark" in a blog somewhere that suggests that
our expm is slower than Matlab's.

Can someone with Matlab access provide insight, please? Are they both
m-files or compiled or what? Are we using different algorithms?

I've always wanted to read up on the literature on how to implement
matrix expoonentials and those famous papers, so this looks like a
good excuse to do so.

- Jordi G. H.
Reply | Threaded
Open this post in threaded view
|

Re: the competition's expm vs ours

David Bateman-3
Jordi Gutiérrez Hermoso wrote:
> I just ran into a "benchmark" in a blog somewhere that suggests that
> our expm is slower than Matlab's.
>  
Jaroslav can probably do a better job at that than I can as he worked on
this part of the code... However, can you put us to the benchmark?

D.


--
David Bateman                                [hidden email]
Motorola Labs - Paris                        +33 1 69 35 48 04 (Ph)
Parc Les Algorithmes, Commune de St Aubin    +33 6 72 01 06 33 (Mob)
91193 Gif-Sur-Yvette FRANCE                  +33 1 69 35 77 01 (Fax)

The information contained in this communication has been classified as:

[x] General Business Information
[ ] Motorola Internal Use Only
[ ] Motorola Confidential Proprietary

Reply | Threaded
Open this post in threaded view
|

Re: the competition's expm vs ours

Jordi Gutiérrez Hermoso
2008/11/12 David Bateman <[hidden email]>:
> Jordi Gutiérrez Hermoso wrote:
>>
>> I just ran into a "benchmark" in a blog somewhere that suggests that
>> our expm is slower than Matlab's.
>>
>
> Jaroslav can probably do a better job at that than I can as he worked on
> this part of the code... However, can you put us to the benchmark?

It wasn't anything impressive. Just ran expm a couple of times on
rand(300), and we lost by a factor of 8 or so. I can't find it again.
:-/

I just want to confirm if we are indeed this slow. And also some
hints, because I can't find the actual implementation.

- Jordi G. H.

Reply | Threaded
Open this post in threaded view
|

Re: the competition's expm vs ours

Kai Habel-6
Jordi Gutiérrez Hermoso schrieb:

> 2008/11/12 David Bateman <[hidden email]>:
>  
>> Jordi Gutiérrez Hermoso wrote:
>>    
>>> I just ran into a "benchmark" in a blog somewhere that suggests that
>>> our expm is slower than Matlab's.
>>>
>>>      
>> Jaroslav can probably do a better job at that than I can as he worked on
>> this part of the code... However, can you put us to the benchmark?
>>    
>
> It wasn't anything impressive. Just ran expm a couple of times on
> rand(300), and we lost by a factor of 8 or so. I can't find it again.
> :-/
>
> I just want to confirm if we are indeed this slow. And also some
> hints, because I can't find the actual implementation.
>
> - Jordi G. H.
>  

Looking for 'expm matlab octave' Google gave back this thread [1].

I ran a quick benchmark on a 1.4GHz Pentium M using today's tip and
matlab 7.6.0

matlab 7.6.0
>> M = rand(300,300);
t=0.25; T=2;
tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
Elapsed time is 2.799052 seconds.
>> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
Elapsed time is 1.789023 seconds.
>> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
Elapsed time is 1.611524 seconds.
>> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
Elapsed time is 1.607993 seconds.
>> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
Elapsed time is 1.750429 seconds.


octave:15> clear all
octave:16> M = rand(300,300);
octave:17> t=0.25; T=2;
octave:18> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
Elapsed time is 4.506 seconds.
octave:19> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
Elapsed time is 4.303 seconds.
octave:20> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
Elapsed time is 4.374 seconds.
octave:21> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
Elapsed time is 4.457 seconds.

So, I see a factor of 2...3 for this particular code - without ATLAS if
its relevant here.

Kai

[1]
http://www.wilmott.com/messageview.cfm?catid=19&threadid=41499&STARTPAGE=2
Reply | Threaded
Open this post in threaded view
|

Re: the competition's expm vs ours

Jaroslav Hajek-2
In reply to this post by David Bateman-3
On Wed, Nov 12, 2008 at 11:09 AM, David Bateman
<[hidden email]> wrote:
> Jordi Gutiérrez Hermoso wrote:
>>
>> I just ran into a "benchmark" in a blog somewhere that suggests that
>> our expm is slower than Matlab's.
>>
>
> Jaroslav can probably do a better job at that than I can as he worked on
> this part of the code... However, can you put us to the benchmark?
>

Not really. I just included some improvement suggestions by Marco
Caliari. I guess he is the one who understands the algorithm inside
expm.



> D.
>
>
> --
> David Bateman                                [hidden email]
> Motorola Labs - Paris                        +33 1 69 35 48 04 (Ph) Parc Les
> Algorithmes, Commune de St Aubin    +33 6 72 01 06 33 (Mob) 91193
> Gif-Sur-Yvette FRANCE                  +33 1 69 35 77 01 (Fax)
> The information contained in this communication has been classified as:
> [x] General Business Information [ ] Motorola Internal Use Only [ ] Motorola
> Confidential Proprietary
>
>



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

Reply | Threaded
Open this post in threaded view
|

Re: the competition's expm vs ours

David Bateman-3
In reply to this post by Kai Habel-6
Kai Habel wrote:

> Jordi Gutiérrez Hermoso schrieb:
>  
>> 2008/11/12 David Bateman <[hidden email]>:
>>  
>>    
>>> Jordi Gutiérrez Hermoso wrote:
>>>    
>>>      
>>>> I just ran into a "benchmark" in a blog somewhere that suggests that
>>>> our expm is slower than Matlab's.
>>>>
>>>>      
>>>>        
>>> Jaroslav can probably do a better job at that than I can as he worked on
>>> this part of the code... However, can you put us to the benchmark?
>>>    
>>>      
>> It wasn't anything impressive. Just ran expm a couple of times on
>> rand(300), and we lost by a factor of 8 or so. I can't find it again.
>> :-/
>>
>> I just want to confirm if we are indeed this slow. And also some
>> hints, because I can't find the actual implementation.
>>
>> - Jordi G. H.
>>  
>>    
>
> Looking for 'expm matlab octave' Google gave back this thread [1].
>
> I ran a quick benchmark on a 1.4GHz Pentium M using today's tip and
> matlab 7.6.0
>
> matlab 7.6.0
>  
>>> M = rand(300,300);
>>>      
> t=0.25; T=2;
> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
> Elapsed time is 2.799052 seconds.
>  
>>> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
>>>      
> Elapsed time is 1.789023 seconds.
>  
>>> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
>>>      
> Elapsed time is 1.611524 seconds.
>  
>>> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
>>>      
> Elapsed time is 1.607993 seconds.
>  
>>> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
>>>      
> Elapsed time is 1.750429 seconds.
>
>
> octave:15> clear all
> octave:16> M = rand(300,300);
> octave:17> t=0.25; T=2;
> octave:18> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
> Elapsed time is 4.506 seconds.
> octave:19> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
> Elapsed time is 4.303 seconds.
> octave:20> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
> Elapsed time is 4.374 seconds.
> octave:21> tic; inv(M) * (expm(-t*M) - expm(-T*M)); toc;
> Elapsed time is 4.457 seconds.
>
> So, I see a factor of 2...3 for this particular code - without ATLAS if
> its relevant here.
>
>  
Yes the absence of ATLAS is important as we use xLANGE and xGEBAL in the
expm that are part of LAPACK. So we need to compare with ATLAS installed..

Regards
D.


> Kai
>
> [1]
> http://www.wilmott.com/messageview.cfm?catid=19&threadid=41499&STARTPAGE=2
>
>  


--
David Bateman                                [hidden email]
Motorola Labs - Paris                        +33 1 69 35 48 04 (Ph)
Parc Les Algorithmes, Commune de St Aubin    +33 6 72 01 06 33 (Mob)
91193 Gif-Sur-Yvette FRANCE                  +33 1 69 35 77 01 (Fax)

The information contained in this communication has been classified as:

[x] General Business Information
[ ] Motorola Internal Use Only
[ ] Motorola Confidential Proprietary