reduce execution time in matlab

I have a matlab programm with a loop, it takes with a machine of 16GO RAM, 7 hours to be executed. The aim is to compute a cross-correlation coefficient on a moving window (for each 1000 observations we compute using a DCCA function a detrended cross correlation); The program is as follows:

X and Y are two vectors with same length (5000 observation), for a given n=10 (20,40,....)

ft=zeros(1000,1);
gt=zeros(1000,1);
FT=zeros(1000,1) ;
Gt=zeros(1000,1) ;
CovXY=zeros(length(X)-999,1) ;
VarX=zeros(length(X)-999,1) ;
VarY=zeros(length(X)-999,1) ;
rho=zeros(1,length(X)-999) ;
x=zeros(1000,1) ;
y=zeros(1000,1);
for j=1:length(X)-999
  x=X(j :j+999);
  y=Y(j :j+999) ;
  [parameters, ll, Ft, VCV, scores] = garchpq(x,1,1) ;
  clear parameters ll VCV scores 
  [parameters, ll, Gt, VCV, scores] = garchpq(y,1,1) ;
  clear parameters ll VCV scores   
  for k=1 :1000
    ft(k)=x(k)/sqrt(Ft(k));
    gt(k)=y(k)/sqrt(Gt(k)) ;
  end
  [CovXY(j, :),VarX(j, :),VarY(j, :)]=DCCA(ft,gt,n);
  rho(j)=CovXY(j)/(VarX(j)*VarY(j)) ;
end
end

I'm asking someone to help me, in order to reduce execution time, i tried preallocation. I don't know what can i do else. For one segment the program takes some second.

[dpb]

1. What is garchpq?
2. What is DCCA?

Couple of things as exist may make minor improvement are

1. Don't need explicit clear
2. ft=x./sqrt(Ft); % no need for loop for ft, gt

Maybe you don't need to use sqrt at all if normalization factor isn't necessary?

When know what the other functions are, there's also possibilities there perhaps for improvments as well as blockproc or filter maybe.

[tilfani oussama]

garchpq is a function that computes a conditional volatility (garch(1,1) model) DCCA is function that computes detrended cross correlation. The logic behind using garchpq to get ft and gt, when dividing by their sqrt in order to filter x and y series.

[dpb]

Well, we can't optimize what we can't see...

What does the result of profiler show are the bottleneck(s)?

[tilfani oussama]

For GARCH you find it matlab. For DCCA here a description https://stats.stackexchange.com/questions/149799/code-for-detrended-cross-correlation-in-r What about blockproc??

[tilfani oussama]

For a given n=5,10,15,.....

[CovXY,VarX,VarY]=DCCA(Data1,Data2,n)

X=cumsum(Data1); %%integrate and set profile series
Y=cumsum(Data2);
X=transpose(X);
Y=transpose(Y);
N=length(X);
for i=1:N-n,
  ind1=i;
  ind2=i+n;
  index=(ind1:ind2);    
  C0=polyfit(index, X(index),1);
  C1=polyfit(index,Y(index),1);
  fit0=polyval(C0,index);
  fit1=polyval(C1,index);
  CovXY(i) = mean((X(index)-fit0).*(Y(index)-fit1));
  CovX(i)= mean((X(index)-fit0).^2);
  CovY(i)= mean((Y(index)-fit1).^2);
end
CovXY=mean(CovXY);
VarX=mean(CovX).^0.5;
VarY=mean(CovY).^0.5;

[OCDER]

Just wondering, is "Cov_" the same as the covariance, cov? And "Var_" the same as the variance, var?

https://www.mathworks.com/help/matlab/ref/cov.html https://www.mathworks.com/help/matlab/ref/var.html

There's also something for cross-covariance, xcov, and cross-correlation, xcorr.

https://www.mathworks.com/help/signal/ref/xcov.html https://www.mathworks.com/help/signal/ref/xcorr.html

Are these different from what you compute with DCCA?

[tilfani oussama]

Yes they differ. Those described in links are pearson correlation, which differ from DCCA.

[the cyclist]

I also recommend that you profile your code to see which lines are taking the most time.

[the cyclist]

I don't think it will speed things up, but if you only need Ft and Gt, then you can call garchpq with this syntax:

[~, ~, Ft] = garchpq(x,1,1);
[~, ~, Gt] = garchpq(y,1,1);

[tilfani oussama]

May be. I will try. Thanks

[dpb]

Searching https://www.mathworks.com/help/search.html?qdoc=garchpq&submitsearch= returns

Did you mean: garch0 (2 results)
No results for garchpq.

so I still don't know garchpq. There's a garch but it doesn't seem to have same footprint.

[the cyclist]

Google search for "garchpq matlab" did not turn up anything for me.

[tilfani oussama]

Yes garch0 (p q) are parameters

[Greg]

You've ignored both suggestions to run the profiler. It is specifically designed to help you do exactly what you are trying to do - identify slow lines of code to try to speed them up.

We can guess what is slowing you down. The profile will know what is doing it.

[dpb]

"Yes garch0 (p q) are parameters"

Well, that's not what' written in the code posted. Nor does the return match the profile...

Answer 1

[Bruno Luong]

Please try to replace the DCCA with this function

function [CovXY,VarX,VarY]=DCCA_vec(Data1,Data2,n)

X=cumsum(Data1); %%integrate and set profile series
Y=cumsum(Data2);
X=transpose(X);
Y=transpose(Y);
N=length(X);

x = (0:n).';
V = [x ones(n+1,1)];
P = V*pinv(V);
Q = eye(n+1)-P;
Q = fliplr(Q);
R0=conv2(X,Q);
R0=R0(:,n+1:N);
R1=conv2(Y,Q);
R1=R1(:,n+1:N);
CovXY = sum(R0.*R1,1)/(n+1);
CovX = sum(R0.*R0,1)/(n+1);
CovY = sum(R1.*R1,1)/(n+1);
CovXY = mean(CovXY);
VarX = sqrt(mean(CovX));
VarY = sqrt(mean(CovY));  
end

The loop

for k=1 :1000
  ft(k)=x(k)/sqrt(Ft(k));
  gt(k)=y(k)/sqrt(Gt(k)) ;
end

can be replaced by

ft = x ./ sqrt(Ft);
gt = y ./ sqrt(Gt);

[tilfani oussama]

Many thanks. I will do it immediately

[Bruno Luong]

So?

If it's not enough you have to post the code garchpq, if it's short enough I might try to take a look.

[tilfani oussama]

The program is faster. I will put the code of garchpq, its long. But i will share with you. Many thinks

[Bruno Luong]

Perhaps you should open a new thread to speed up the garchpq alone?

[tilfani oussama]

Please find enclosed gacrhpq, if you can help me to speed up. For your proposition, times was reduced, but no enough. Bests

[dpb]

Right off the bat I see

if isempty(startingVals)
  startingVals = mean(data2)*.05;
  for i=1:K
    As = sum(p(i,:));
    startingVals  = [startingVals .1*ones(1,As)/As]; %#ok<AGROW>
  end
  for i=1:K
    Bs = sum(p(i,:));
    startingVals  = [startingVals .8*ones(1,Bs)/Bs]; %#ok<AGROW>
  end
  startingVals = startingVals';
end

I don't know how big K is nor how many times this routine gets called, but there are two loops there that are dynamically reallocating startingVals K times each instead of preallocating. And in a counted loop, too, where the number of iterations is knwown a priori...

But, where are the results from the profiler???? You can't make significant progress on the overall run time unless you know which part of the code is the significant culprit. You can cut a subset down by 70% but if it's only 1% overall, it won't make much difference for the effort.

[Bruno Luong]

@tilfani

Sorry, the garchpq() calls a big hammer of optimization, the fmincon() with an unknown objective function heavy_likelihood() (not include in the code).

I'm not surprised that takes most of the time, even look at the objective function. There is not much I can do to improve it, without warranty that you get an as good accurate output.

You should go back and report the time issue to your advisor/boss and trying to find another alternative for whatever problem you want to solve.

[OCDER]

Hm, saw this in the garchpq code. nested for loop AND growing matrix for K^2 potential matrix copies. Times that by 8000 iterations (two garchpq summons for X = 1:5000-999) for your application. The time could add up quickly. I wish we had a way to profile how much time each step actually takes....

temp = O';
for i=1:K
    for j = 1:K
        temp = [temp squeeze(A(i,j,1:p(i,j)))]; %#ok<AGROW>
    end
end

Optimization is a time-consuming process. Perhaps hire someone who is good at MATLAB to optimize this code? Otherwise, you'll have to go through every code and rework it, test it, rework, test, ....

If a built-in matlab process becomes the bottleneck, you'll have to use some advance tricks to speed things up like what Yair does:

https://undocumentedmatlab.com/blog/speeding-up-builtin-matlab-functions-part-1

Answer 2

[Bruno Luong]

@dpb

The comment %#ok<AGROW> tells the author (Kevin Sheppard) is well aware about growing, and he obviously doesn't care.

The code garhcpq.m looks well written, contrary to the function DCCA() which is ugly IMHO.

[tilfani oussama]

What do you suggest? Is possible to speed up this code?

[Bruno Luong]

You need first to do what every one ask you: run a short number iteration with the PROFILER then post the result.

But if you miss my post, No I don't think there is a chance to accelerate the garhcpq.m

Some people focus on the growing stuff with K=1 in your example so there is no pb there.

The consumed time is FMINCON running by GARCHPQ over and over.

[dpb]

I didn't "FOCUS" on it; it was just the first thing that jumps out...

That the author didn't care is one thing; and it undoubtedly won't make any measurable difference overall, granted, but it is sloppy and easily remedied in this case since they are counted loops, not uncertain size.

It's probably because it is "only" initialization that the author left it but why not fix what can easily just on general principles?

[Bruno Luong]

This loop is just for building the starting guess vector (composed by few segments) for FMINCON, and believe me this is next to nothing the work that would be carried out later.

The delta growing is not constant, granted can be computed without the loop growing. But there are few reasons why the author prefer coding that way:

• Because it's not important?
• The author prefer spending his time for something else?
• Because the code is more readable in this way?
• Because the code is more easily to be modified and maintainable in this way?

[dpb]

I'm not arguing it would make any noticeable improvement; just stuck out at first glance so pointed it out is all...

As for the other three points all it would have taken is writing one line using an already-defined variable and modifications would have been automagic that way just as are as is...took almost as long for the author to acknowledge the "ignore" message as it would have to have fixed at the time.

A big deal? In this case, no. In general, poor coding practice is still poor coding practice.