Improving the computation speed of loops

I am trying to implement the GSADF-Test by Phillip's et al. in MATLAB, the accompanying code was submitted by one of the co-authors.

Essentially the code runs very slow, about an hour now for the first set of observations.

As I said, I did not write this myself and have no clue how to fix the computation speed.

Thus, fixes, alternatives methods or any help to get the here depicted Test across is most sincerely welcome!

(This Script calls the attached Function ADF_FL.m)

%**************************************************************************
%   "Testing for Multiple Bubbles" by Phillips, Shi and Yu (2011)
    
%   In this program, we calculate critical values for the generalized sup 
%   ADF statistic.
% *************************************************************************
 

clear all
close all
clc

format short

qe=[0.90;0.95;0.99];

tic;

m=2000;
T=1680;            % change your sample size here
r0=0.01+1.8/sqrt(T);
swindow0=floor(r0*T);       % change your minimum window size here

 
dim=T-swindow0+1;

%% %%%% DATA GENERATING PROCESS %%%%%%
SI=1;
randn('seed',SI);   
e=randn(T,m); 
a=T^(-1);
y=cumsum(e+a);


%% THE GENERALIZED SUP ADF TEST %%%%%%

gsadf=ones(m,1);  
for j=1:m; 
    sadfs=zeros(dim,1); 
    for r2=swindow0:1:T;
        dim0=r2-swindow0+1;
        rwadft=zeros(dim0,1);
        for r1=1:1:dim0; 
            rwadft(r1)= ADF_FL(y(r1:r2,j),0,1);  % two tail 5% significant level
        end;  
        sadfs(r2-swindow0+1)=max(rwadft);
    end;
    gsadf(j)=max(sadfs);
end;

toc;


quantile_gsadf=quantile(gsadf,qe);

filename = 'CV_GSADF1680.xlsx';
xlswrite(filename,gsadf,1,'A1:A2000');

disp([qe quantile_gsadf]);

Answer 1

[Bjorn Gustavsson]

When you want to search for ways to optimize your code always run it with the profiler to identify where the time is spent.

profile on
ADF_FL_test
profile report

If it takes too long time to run try with reduced sizes of your variables just to see how the time varies with the problem-size.

I reduced the sizes (m and T one order of magnitude smaller) and found that the time-wasters are lines 41 and 44 in ADF_FL.m. And the bulk of the time seems to be spent by the built-in mpower.

You'll have to do more of the profiling and development-work. Perhaps the ADF_FL function doesn't work as you expect for your inputs which might change some vector-vector-multiplication from inner-product to outer product and the function produces some result anyway?

HTH

[Felix Riechmann]

Thank you for your answer!

I suppose the ADF_FL function is not really the problem, rather the three nested For-Loops under Section "THE GENERALIZED SUP ADF TEST", because the function itself is called in other applications and works fine.

From my very basic MATLAB-Knowledge, I recall nesting three For-Loops is rather "unclean" (if you can call it that).

The Loop is a Monte-Carlo simulation with "m" iterations, which should be 2000 dictated as the status-quo by the academic literature.

What I did so far was replacing the first loop with a while loop with a pre-set counting variable and abort the section after a solid 15 minutes, finding that seven iterations and values have been generated.

I'll try my best to optimise the loop myself, but any further advice in this endeavour is as always deeply appreciated!

[Bjorn Gustavsson]

Sure, you can suppose that the ADF_FL are not really the problem - even though I went through the trouble of profiling your programme for you. Since you suppose that I have now for a second time done the profiling (for the reduced sizing) which gives these results:

and there you see that the bulk of the time is spent in the ADF_FL function, and when we look closer into the profiling results of where the time is spent in that function you'll see this (still for the reduced size-problem):

Then we can notice the small time spent in the main script (self-time) and the large fraction of time spent in the ADF_FL-function. You can decide where to spend the time on optimizing your code as you see fit. My humble advice would still be to at least consider the idea that time might be more efficiently shaved off the total from where the bulk of the time is calculated. For example you have a repeated use of (x2'*x2)^-1 on lines 41 and 44 (for my size-reduced problem) that takes up the bulk of the time in ADF_FL. It is possible that it would be time-saveing to save that calculation in a temporary array the first time it is calculated. That is one place to start looking for code optimization.

When it comes to the "bad practice of nested loops" that was a thing 15-20 years ago, no longer that big of a deal if the variables are not grown incrementally in the loop but properly pre-allocated.

If it is so that the product x2'*x2 will always be a 2-by-2 matrix then there are a couple of improvements you can make to cut down the running-time. I will not even try to get into whether it is possible to rewrite the algorithm, but just note that

inv2tx2 = (x2'*x2)^(-1);

Is approximately 3 times slower than

inv2tx2 = inv(x2'*x2);

which again is approximately a factor of 2 slower than the explicit

x2tx2 = x2'*x2;
inv2tx2 = [x2tx2(2,2) -x2tx2(1,2);
           -x2tx2(2,1) x2tx2(1,1)]./(x2tx2(1,1)*x2tx2(2,2)-x2tx2(1,2)*x2tx2(1,2));

So in that case you can speed up ADF_FL first by a factor of ~2 by saving the inverse first time it is calculated, then by another factor of ~6 by using the explicit expression for the inverse of a 2-by-2 matrix.

That makes for approximately a one order of magnitude speedup.

[Bjorn Gustavsson]

Did you get any further?