Preallocation: speeding up loop with variable dimensions

Dear community,

I use this segment of code frequently to make 3D models using the electrical impedance tomography (EIT) package EIDORS. I am producing a multi-layered head model by subtracting the overlapping tetrehedra of STL files of skull, brain, etc. from meshed head models using the MATLAB functions find() and any().

How can I speed up this function given that the (number of) overlapping elements for each layer depend(s) on the geometries of each individual model?

load(meshedHeads); % contains struct with forward model 'fwd_mdlHeadWithElec'

%% first, remove the smallest model from the head (the ventricles)
fwd_mdlvent = stl_read(STLfilenames{v}); % v = first ventricle STL filename

elems_with_nodes_inside_vent_border = []; % ventricle element array we are building

% finds 3D points in solid head model that overlap with ventricles model
node_row_value = intriangulation(fwd_mdlvent.nodes,fwd_mdlvent.elems,fwd_mdlHeadWithElec.nodes);
% isolate points which do indeed overlap
node_row_value_if_inside_border = find(node_row_value); % Gather the ones

% SLOW LOOP, no way to preallocate
for k = 1:size(node_row_value_if_inside_border,1)
    %could speed up by indexing by column instead of row? length of this array varies widely based on models:
    elems_with_this_node_value = find(any(fwd_mdlHeadWithElec.elems==node_row_value_if_inside_border(k),2));
    %concatenate array
    elems_with_nodes_inside_vent_border = [elems_with_nodes_inside_vent_border; elems_with_this_node_value];
end

elems_with_nodes_inside_vent_border = unique(elems_with_nodes_inside_vent_border); % remove duplicates

%...repeat for brain, CSF, etc.

%remove elements which represent ventricles from brain model, result is a
% 3D brain model with a cavity in the shape of the ventricles
elems_with_nodes_inside_brain_border = setdiff(elems_with_nodes_inside_brain_border,elems_with_nodes_inside_vent_border);

%...repeat for other model layers, assign conductivities to each layer

%save the model set as a .mat file
save(filename,'headImageCases');

The result is a nested struct with a forward model of the layered-head with shell elements (points) separated by material index.

I hope this explains my problem, though I know it is highly specific. Thank you in advance and I look forward to discussing further with you.

-Jared

**PS - I recognize that it may be helpful for me to provide the full code for this process in the case that my explanations are unclear, but the models and required files make this quite complicated so I hoped that someone may be able to help with just the provided snippet. If including everything will help you to address my problem then please leave a comment and I will take the time to upload/explain the required files and full code.

Answer 1

[Max Heimann]

Are you sure your code is slow due to non-preallocated elements? If you want to improve the performance i would suggest you use the "run and time" option in matlab, or use the profiler from the console:

profile on
profile clear
>> execute_your_code
profile viewer

This should give you a detailed view about where your code spends most of its time. It may very well be, that preallocation can help, but it could also just be a time consuming calculation. Personally i dont understand enough about what it is that you are doing to give you a usefull hint regarding how to preallocate for your specific project.

[J Culp]

Hi Max,

Thank you for your response. Before asking this question I had pursued this and saw that the majority of time was spent in this function, and coupled with the warning regarding pre-allocation and my own experience with pre-allocating a large matrix greatly improving speed, I concluded that this was the problem.

After revisiting the profiler and looking deeper into the details I can see that 99.5% of the time is spent on the find(any()) operation, while the remaining 0.5% of time is spent concatenating the array, so you are clearly correct. Thank you again for taking the time to respond and help me.

All the best,

JC