# How to reduce computation time with 8 nested for loop

31 views (last 30 days)
SANJAY SINGH TOMAR on 25 Sep 2021 at 12:23
Commented: Walter Roberson on 26 Sep 2021 at 7:05
I have to do a search based computation with 6 coupled equation to calculate the sets of 8 unknows satisfying these equations. All unknows have 1000 values and size of computation is reaching 10^24. Code is getting stuck around 10^13 values since last 10 days. Can someone please help me to reduce the computation time.
As this size of matrix cannot fit in the mamory I have tried the following way.
Matlab Code
aa2=0:0.001:1; aa3=0:0.001:1; aa4=0:0.001:1;
bb1=0:0.001:1; bb2=0:0.001:1;bb3=0:0.001:1; bb4=0:0.001:1;
jj1=0;
k1=0;
for i1=1:length(aa2)
a2=aa2(i1)
for i2=1:length(aa3)
a3=aa3(i2);
for i3=1:length(aa4)
a4=aa4(i3);
for j1=1:length(bb1)
b1=bb1(j1);
for j2=1:length(bb2)
b2=bb2(j2);
for j3=1:length(bb3)
b3=bb3(j3);
for j4=1:length(bb4)
b4=bb4(j4);
a1=a1(a2,a3,a4,b1,b2,b3,b4);
B1=B1(a1,a3,a4,b1,b3,b4);
B2=B2(a1,a3,a4,b1,b3,b4);
B3=B3(a1,a3,a4,b1,b3,b4);
B1=B1(a1,a3,a4,b1,b3,b4);
B2=B2(a1,a3,a4,b1,b3,b4);
B3=B3(a1,a3,a4,b1,b3,b4);
k1=k1+1;
% five equations
f1=2*A1+5*A2;
f2=-6*B2-A2;
f3=A2-8*B2+A1;
f4=-9*B3-A3+A2;
f5=A3-2*B3;
f6=A3-2*B1+A2;
if f1==0.1 && f2==0.4 && f3<=0.2 && f4<=0 && f5=-0.3 && f5=-0.3
jj1=jj1+1;
final=[a1; a2;a3;a4;b1;b2;b3;b4];
fprintf('equation satisfied')
display(k1)
name1=['eqn stisfiled' num2str(jj1) '.csv'];
csvwrite(name1,final)
end
end
end
end
end
end
end
final=[f1 f2 f3 f4 f5]';
end

Chunru on 25 Sep 2021 at 12:43
Brute force searching for such problem is not feasible. If it takes around 10 days to reach to 10^13, it takes 10*10^11=10^12 days=2.7 billion years to reach to 10^24. Think of better algorithm.
##### 2 CommentsShowHide 1 older comment
Walter Roberson on 26 Sep 2021 at 7:05
Suppose you had a GPU that was able to execute 256 calculations simultaneously, and suppose each calculation was 100 times faster on the GPU than on the CPU.
Then
format long g
faster_by = 100;
num_simultaneous = 256;
how_many_days = days(10)*10^(23-13) / faster_by / num_simultaneous
how_many_days = duration
3906250 days
years(how_many_days)
ans =
10694.9492460489
So as a order of magnitude, it would take over 10000 years.
With a modern NVIDIA 3000 series GPU, you might have a raw computation rate of roughly 1 terraflop. Considering 6 equations and multiple variables, let us estimate that 100 flops are needed per combination. That would give us a rate of roughly 10^12/10^2 = 10^10 combinations evaluated per second, and would so need 10^13 seconds. Suppose you have a goal of finishing in 10^6 seconds (about 31 days): then how many such GPU would you need?
seconds(10^13) / seconds(10^6)
ans =
10000000
According to https://www.tomshardware.com/news/gpu-sales-report-q4-2020-jpr that would require about as many 3000 series GPU as NVIDIA ships in total worldwide sales (of all GPUs) for 3 months. Not impossible, perhaps, but enough to lead to a worldwide shortage of GPUs.

Walter Roberson on 25 Sep 2021 at 12:45
if f1==0.1 && f2==0.4 && f3<=0.2 && f4<=0 && f5=-0.3 && f5=-0.3
The only one of those values that is exactly representable in binary double precision, is the 0 .
You might not get any matches on the comparison.
You should use ismembertol()
Also, the f5=-0.3 is invalid syntax, as it is an assignment. You also repeat it in the statement.
SANJAY SINGH TOMAR on 26 Sep 2021 at 6:12
Thanks for your reply. Values in the equations are dummy. Main aim is to reduce the computational task. Can parallization help in this regard? Or any other grid search method as iterations are very but compution task per iteration is very small.

John D'Errico on 25 Sep 2021 at 17:30
Edited: John D'Errico on 25 Sep 2021 at 17:31
This is why there are optimization tools provided. Use them, instead of brute force search.
But really, this is a combinatorial problem, where you want to solve for combinations of variables that solve an underdetermined linear system of 5 equations in 8 unknowns. Is there a good reason you are doing this?
One idea might be to choose any 3 of those variables, fixing tham at some arbitrary set of values. Now use an INTEGER linear programming tool to find a solution to those 5 equations.
But first, you need to convert this to an integer problem, recognizing that as Walter said, you are doing this completely the wrong way. So multiply EVERYTHING by 1000. Now the variables are integers in the interval [0,1000].
Pick some integer values for aa2, aa3, aa4. Substitute them into the equations. Now you will be left with a set of Linear Diophantine equations in the remaining 5 variables. But intlinprog can handle exactly that problem, and do so efficiently. If a purely integer solution is found, it will be unique. Now continue with a new set of values for the first three variables.
Essentially, this shows there will never be more than 1001^3 possible solutions, but likely far fewer than that, since much of the time intlinprog may not produce any solution at all. Of course, if you allowed the variables to be continuous, then there would likely be an infinite 5-manifold of solutions, embedded in the 8 dimensional search space of your problem set. But you have chosen to limit the set by quantizing the problem.
Even at that, I still debate why you are doing all of this, a huge computation to solve a rather trivial problem, when likely the entire reason you are doing this computation in a brute force form is one that would be better handled by a simple constrained optimization. But that is your problem to resolve, not mine.
SANJAY SINGH TOMAR on 26 Sep 2021 at 6:19
Thanks for your reply. I have tried fminsearch, fmincon optimizers but results were different and not that convincing, so in order to get the best I had no option but to do a brute search like this. Actually I am trying to do the error estimation but as there can be infinite solutions I wanted to try at least best in this range.

Steven Lord on 25 Sep 2021 at 17:55
a1=a1(a2,a3,a4,b1,b2,b3,b4);
B1=B1(a1,a3,a4,b1,b3,b4);
B2=B2(a1,a3,a4,b1,b3,b4);
B3=B3(a1,a3,a4,b1,b3,b4);
B1=B1(a1,a3,a4,b1,b3,b4);
B2=B2(a1,a3,a4,b1,b3,b4);
B3=B3(a1,a3,a4,b1,b3,b4);
You may intend for MATLAB to evaluate functions a1, B1, B2, etc. and return the output from those functions into those variables, but that's not going to work. Since you're assigning to a1, B1, B2, etc. MATLAB will treat their use on the right-hand side as an attempt to index into those variables. Since those variables aren't six- or seven-dimensional and since the values of a1, a2, a3, a4, b1, b2, b3, and b4 are not positive integer values these should throw errors.
Perhaps if you show the mathematical equations you're trying to solve we may be able to offer some more specific guidance on how to solve them.
% five equations
f1=2*A1+5*A2;
f2=-6*B2-A2;
f3=A2-8*B2+A1;
f4=-9*B3-A3+A2;
f5=A3-2*B3;
f6=A3-2*B1+A2;
if f1==0.1 && f2==0.4 && f3<=0.2 && f4<=0 && f5=-0.3 && f5=-0.3
Anyway, why not solve these six algebraic equations to determine the values A1, A2, etc. must have then use fsolve from Optimization Toolbox to solve for a1, a2, etc. in the first set of equations I copied above?
SANJAY SINGH TOMAR on 26 Sep 2021 at 6:25
Thanks for your reply. There are 6 coupled equations (f1,f2...f6) which are function of 8 unknowns (a1,..a4, b1,...,b4). fsolve is not working we can use optimization tools like fminsearch and fmincon but as mentioned result with them were not convincing. So i tried this way.