Hi, I'm benchmarking the Mahalanobis distance to see how the accuracy and execution time changes with an increasing sample size. As far as I understand the algorithm the execution time should grow linearly as the sample size increases. The weird thing is that the time grows linearly up to (and including) 199 samples, but then suddenly has a drop at 200 samples. I've attached a graph to illustrate this. I'm using it to do outlier detection. The time drops at 200 samples, but the accuracy increases without a sudden drop.

On Tue, 15 Apr 2014, GOO Creations wrote: > I'm benchmarking the Mahalanobis distance to see how the accuracy and > execution time changes with an increasing sample size. As far as I > understand the algorithm the execution time should grow linearly as the > sample size increases. The weird thing is that the time grows linearly up > to (and including) 199 samples, but then suddenly has a drop at 200 > samples. I've attached a graph to illustrate this. What implementation of lapack/blas are you using? The most demanding task in computing Mahalanobis distance is the inversion of the covariance matrix of the selected series, which is performed via the lapack Cholesky functions dpotrf and dpotri. Depending on the implementation, these functions may switch algorithm based on the size of the input data (e.g. invoking parallelization when a certain threshold size is exceeded).

On Tue, 15 Apr 2014, Riccardo (Jack) Lucchetti wrote: > On Tue, 15 Apr 2014, Allin Cottrell wrote: > >> On Tue, 15 Apr 2014, GOO Creations wrote: >> >>> I'm benchmarking the Mahalanobis distance to see how the accuracy and >>> execution time changes with an increasing sample size. As far as I >>> understand the algorithm the execution time should grow linearly as the >>> sample size increases. The weird thing is that the time grows linearly up >>> to (and including) 199 samples, but then suddenly has a drop at 200 >>> samples. I've attached a graph to illustrate this. >> What implementation of lapack/blas are you using? >> >> The most demanding task in computing Mahalanobis distance is the inversion >> of the covariance matrix of the selected series, which is performed via >> the lapack Cholesky functions dpotrf and dpotri. Depending on the >> implementation, these functions may switch algorithm based on the size of >> the input data (e.g. invoking parallelization when a certain threshold >> size is exceeded). > That's what I had thought too, initially. However, the size of the covariance > matrix doesn't depend on the number of observations, which is the variable > our friend is tracking (unless I misunderstood his message). Duh! You're right. Then I can't explain this either. Allin _______________________________________________ Gretl-users mailing list Gretl-users(a)lists.wfu.edu http://lists.wfu.edu/mailman/listinfo/gretl-users

On Tue, 15 Apr 2014, GOO Creations wrote: > I've used 8 different datasets with 30-40 million samples each. Every > single window over every single dataset gave the exact same time jump > between 199 and 200 observations. Sorry, _now_ I'm officially confused. Could you please clarify what you mean by "samples" and "observations"? ------------------------------------------------------- Riccardo (Jack) Lucchetti Dipartimento di Scienze Economiche e Sociali (DiSES) Università Politecnica delle Marche (formerly known as Università di Ancona) r.lucchetti(a)univpm.it http://www2.econ.univpm.it/servizi/hpp/lucchetti ------------------------------------------------------- _______________________________________________ Gretl-users mailing list Gretl-users(a)lists.wfu.edu http://lists.wfu.edu/mailman/listinfo/gretl-users

Hello, These are my results: On Fedora 19.0 x64 4 core [helio@localhost temp]$ ./test 197 number of observations: 707623 198 number of observations: 675847 199 number of observations: 679392 200 number of observations: 557697 201 number of observations: 536804 202 number of observations: 578269 203 number of observations: 544649 [helio@localhost temp]$ ./test 197 number of observations: 777980 198 number of observations: 764587 199 number of observations: 770005 200 number of observations: 623716 201 number of observations: 627000 202 number of observations: 630206 203 number of observations: 634468 [helio@localhost temp]$ ./test 197 number of observations: 695839 198 number of observations: 678020 199 number of observations: 681358 200 number of observations: 534876 201 number of observations: 537547 202 number of observations: 539711 203 number of observations: 543831 [helio@localhost temp]$ ./test 197 number of observations: 709759 198 number of observations: 684160 199 number of observations: 685812 200 number of observations: 534485 201 number of observations: 537334 202 number of observations: 573589 203 number of observations: 543497 On OpenSUSE 13.1 x64 2 core helio@linux-techno:~> ./test 197 number of observations: 1060657 198 number of observations: 1097359 199 number of observations: 1104009 200 number of observations: 867470 201 number of observations: 872487 202 number of observations: 874292 203 number of observations: 881876 helio@linux-techno:~> ./test 197 number of observations: 730982 198 number of observations: 732811 199 number of observations: 736721 200 number of observations: 579397 201 number of observations: 584108 202 number of observations: 584735 203 number of observations: 588359 helio@linux-techno:~> ./test 197 number of observations: 731426 198 number of observations: 738590 199 number of observations: 741741 200 number of observations: 583523 201 number of observations: 584833 202 number of observations: 588973 203 number of observations: 592129 helio@linux-techno:~> ./test 197 number of observations: 730169 198 number of observations: 732672 199 number of observations: 737452 200 number of observations: 579829 201 number of observations: 583927 202 number of observations: 584652 203 number of observations: 589383 As you can see the time-jump also happens here. Note the high 1st run times on OpenSUSE. On Tue, Apr 15, 2014 at 4:49 PM, GOO Creations <goocreations(a)gmail.com <mailto:goocreations@gmail.com>> wrote: ... I've attached a small example program (with a makefile) that does the test. I'm using gettimeofday, which will probably only work under Linux. It might take a couple of seconds to execute. I would apprciate it if someone could run it (sorry Allin, this is probably the wrong mailing list again for posting C code), and verify that I'm not the only one with this time-jump. These are my outputs: /197 number of observations: 784814// //198 number of observations: 760379// //199 number of observations: 759822// //200 number of observations: 598327// //201 number of observations: 602174// //202 number of observations: 604390// //203 number of observations: 607213// / Chris _______________________________________________ Gretl-users mailing list Gretl-users(a)lists.wfu.edu http://lists.wfu.edu/mailman/listinfo/gretl-users

On Wed, 16 Apr 2014, GOO Creations wrote: > Thanks Helio. So it's not just me. > > Since the mathematics behind Mahalanobis indicate a linear dependency between > the observation count and the execution time, I'm simply going to ignore this > time-jump. I've found the cause of the time-jump. It has nothing to do with the actual Mahalanobis calculations and is purely to do with the apparatus for printing the results, which up till now has been interleaved with the computation (but is now separated in CVS). The point is that we do certain calculations designed to ensure a reasonably "pretty" printout, but once the sample size exceeds a certain size we switch to a less rigorous but cheaper variant of that code. Since your test program passes a NULL pointer for the printing there's actually no call to run any of the prettification code, and in CVS we no longer do so. Allin Cottrell _______________________________________________ Gretl-users mailing list Gretl-users(a)lists.wfu.edu http://lists.wfu.edu/mailman/listinfo/gretl-users