Clear Filters
Clear Filters

Question to MATLAB profiler and speed of code (spline calculation during optimization)

3 views (last 30 days)
Hello dear MATLAB community,
I have a question concerning this piece of code
This will calculate a piecewise cubic spline for my parametrized function. It is calles so often because it´s inside an optimization routine (fmincon). My first question is: Is there a way to speed up this code? And the second question: Why is the runtime of line 11 and 13 and 12 and 14 so different? Both lines are doing the same operation but the the calculation time differs around 30%?
Thanks for your help,
David
  3 Comments
David
David on 31 Oct 2014
Edited: David on 31 Oct 2014
I´m using fmincon with the following settings:
iter = 100000;
opts = optimset('fmincon');
opts.Display = 'iter';
opts.Algorithm = 'interior-point';
opts.MaxSQPIter = iter;
opts.MaxIter = iter;
opts.MaxFunEvals = 150000;
[y(:,1),fval(1,1)] = fmincon(@myfun, x0,A,b,[],[],lb,[],[], opts);
I already tried to use other algorithms then interior-point but none of them were as good as the interior-point algorithm.
Sean de Wolski
Sean de Wolski on 31 Oct 2014
Interior point is usually the best. I question of the spline calculations are highly unstable (a trait of splines) that could be causing the optimizer to have trouble.

Sign in to comment.

Answers (5)

Stephen23
Stephen23 on 30 Oct 2014
Edited: Stephen23 on 25 Nov 2014
Two questions... two answers.
1) Probably. But this depends mostly on the two functions griddedInterpolant and F1 / F3, about which you have not provided us with any information. For example it might be possible to call these functions only once each, if griddedInterpolant can accept a matrix for its second input. It might also be faster to interpolate the data directly, without creating the intermediate functions F1 / F3.
2) MATLAB is an interpreted language with some sophisticated memory and data management. I am certainly no expert on this topic (someone from MATLAB could help you), but this apparently includes optimization of functions when they are first called, allocating memory and checking if the data changes during the code. These first steps add a little time when code is first run, or a function is first called. Those times look fine.
  7 Comments
Sean de Wolski
Sean de Wolski on 30 Oct 2014
Edited: Sean de Wolski on 30 Oct 2014
How many times do you have to run this? I mean at 0.000019s it'll have to run 52000x to take a second.
David
David on 30 Oct 2014
As this is a call during an optimization routine it is sometimes called more than 100.000 times. So even small optimizations of less than 1ms can have a big influence to the total computation time.

Sign in to comment.


Marco
Marco on 30 Oct 2014
Edited: Marco on 30 Oct 2014
EDIT: Please ignore this answer, I realized that my answer wasn´t a good answer, because lines 11 and 13 actually do not differ in respect to row and column access.
The answer was: About the difference in calculation speed in lines 11 and 13, I would expect that this has to do with the way how MATLAB stores the data in the memory of the hardware. It is said for MATLAB, that data stored in columns can consecutively be accessed faster by the hardware than the harware could consecutively access data being stored in rows. This is how The Mathworks implemented MATLAB. For other software this could be the opposite round. It depends on the specific low level implementation of the software. Here is a link to some MATLAB information about this: programming-patterns-maximizing-code-performance-by-optimizing-memory-access

Sean de Wolski
Sean de Wolski on 30 Oct 2014
Edited: Sean de Wolski on 30 Oct 2014
You can do this with one call to griddedInterpolant or interp1 (which builds a griddedInterpolant under the hood). Build it once and evaluate it on [x2 x2]. Since splines are calculated in one dimension anyway.
The call to interp1 would look like this:
% Simulated data
xges = cumsum(rand(10,2));
xi = 1:10; % index
xq = 1:0.1:10; % query
% x2 is first column, y2 is second
x2y2 = interp1(xi.',xges,xq.'); % interp
  5 Comments
Sean de Wolski
Sean de Wolski on 30 Oct 2014
Run each a few more times. Is there anything stochastic about the system/objective function/etc.?
David
David on 30 Oct 2014
The result of the optimization is always the same. The duration of both stays always nearly the same (+- 0.2s). The original code is always faster than your proposed solution (always around 1s).

Sign in to comment.


Philip Borghesani
Philip Borghesani on 30 Oct 2014
Your attempted pre-allocation by calling zeros for xj and yj is not doing anything useful and may be costing a small amount of time try just a simple assignment and removing the calls to zeros:
xj=F1(x2);
yj=F3(x2);
There is never a benefit to preallocating something if a following assignment is going to write into the entire variable.
  1 Comment
David
David on 31 Oct 2014
Edited: David on 31 Oct 2014
Thank you Philip for your answer.
I also thought of this possibility to save this computing time, but actually it doesn´t change anything. What I could figure out is that the pre-allocation needs time but only when profiling it. Measuring the whole optimization process with tic/toc leads to this times:
Elapsed time is 11.189407 seconds. %With pre-allocation
Elapsed time is 11.185134 seconds. %Without pre-allocation
This is actually the same time for both calculations.
But indeed your right the pre-allocation doesn´t give any benefit.
Small EDIT on this point:
After rerunning the optimization a lot of times you could see a small speed up without the pre-allocation (around 0.05s)

Sign in to comment.


Sean de Wolski
Sean de Wolski on 31 Oct 2014
Interior point is usually the best algorithm (hence why we made it the default!).
I question if the spline calculations are highly unstable (a trait of splines) and that this could be causing the optimizer to have trouble. This being the reason for the huge number of function evaluations.
Also, it wouldn't surprise me at all if the actual display iter setting is causing much of the time as printing to the command line is slower than computation. Try turning that off and rerunning.
  2 Comments
David
David on 31 Oct 2014
If i take a closer look into all calculations that the optimizer has done, then it seems like the spline calculation is pretty stable. The picture shows all calculated lines during the optimization and the red line is the optimum.
I also tried to turn off the display settings but there was no speed up. I achieve (sometimes) a significant speedup when setting the parameter
opts.TolFun = 0.05;
to a higher value then the default one. But this is very risky because of course sometimes the results gets very bad. I try to set up a logic in front of this parameter to set it dynamically.
David
David on 31 Oct 2014
Actually I think there is no possibility to speed up the calculation of a cubic spline in MATLAB. The function griddedInterpolant is way the fastest function to calculate the spline (as far as I have found).
Nevertheless I could speed up my code around 30%! I made another calculating condition for fmincon which leads to the same results but without looping 100.000 times.
Thanks to all who helped me!

Sign in to comment.

Categories

Find more on Interpolation in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!