FYI: tril/triu optimized

[Jaroslav Hajek]

hi all,

in cooperation with David Bateman, I contributed an optimized compiled
implementation of tril and triu:
http://hg.savannah.gnu.org/hgweb/octave/rev/b134960cea23

benchmark

n = 2000;
A = rand (n);
k = 1;
tril (eye (2)); # to avoid startup penalty
for iter = 1:4
 tic; tril (A, k); toc
endfor

I got these timings:

original version:

Elapsed time is 0.0026319 seconds.
Elapsed time is 0.00277996 seconds.
Elapsed time is 0.00257206 seconds.
Elapsed time is 0.00258803 seconds.
Elapsed time is 0.0137451 seconds.
Elapsed time is 0.0138719 seconds.
Elapsed time is 0.0140979 seconds.
Elapsed time is 0.0158539 seconds.
Elapsed time is 0.0766211 seconds.
Elapsed time is 0.0778449 seconds.
Elapsed time is 0.077647 seconds.
Elapsed time is 0.0763021 seconds.


the new patch

Elapsed time is 5.88894e-05 seconds.
Elapsed time is 5.4121e-05 seconds.
Elapsed time is 2.31266e-05 seconds.
Elapsed time is 2.19345e-05 seconds.
Elapsed time is 0.000933886 seconds.
Elapsed time is 0.00111985 seconds.
Elapsed time is 0.000917912 seconds.
Elapsed time is 0.000798941 seconds.
Elapsed time is 0.018568 seconds.
Elapsed time is 0.020371 seconds.
Elapsed time is 0.020745 seconds.
Elapsed time is 0.0183351 seconds.


speed-up is more than 100x for n = 100, up to 20x for n = 500 , about
4x for n = 2000...
further, tril/triu now accept a "pack" option, so that they pack the
extracted elements in a column...

octave:1> a = rand(5)
a =

   0.393561   0.913037   0.518761   0.859863   0.778841
   0.438795   0.925017   0.813088   0.823300   0.154816
   0.304567   0.232932   0.574848   0.437198   0.095469
   0.260991   0.733759   0.916659   0.408505   0.949647
   0.072507   0.706963   0.811008   0.908441   0.087412

octave:2> triu(a)
ans =

   0.39356   0.91304   0.51876   0.85986   0.77884
   0.00000   0.92502   0.81309   0.82330   0.15482
   0.00000   0.00000   0.57485   0.43720   0.09547
   0.00000   0.00000   0.00000   0.40850   0.94965
   0.00000   0.00000   0.00000   0.00000   0.08741

octave:3> triu(a,"pack")
ans =

   0.393561
   0.913037
   0.925017
   0.518761
   0.813088
   0.574848
   0.859863
   0.823300
   0.437198
   0.408505
   0.778841
   0.154816
   0.095469
   0.949647
   0.087412

enjoy

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