Thread Subject: Vectorisation game: How to optimise access in CELL arr.?

Dear all,

in an algorithm I am currently implementing I have a FOR loop which I
would very much like to reduce to implicit iteration involving
MATLAB's powerfull COLON-operator. I have tried various combinations
of CAT, MTIMES, SUM and TIMES to no avail.

More specifically, I have a 1 by m CELL array, V, (the contents of
which are of homogeneous type--basically matrices of the same
dimensions) and an m by 1 vector, y, of doubles. The loop in question
is this one

   U = y(1) * V{1};
   for k = 2:m,
      U = U + y(k) * V{k};
   end

so it is computing a linear combination of the V{k}'s.

I should note that m is not a large number, certainly no greater than
20 and typically around 5 or 10, so there may not be much gain in
vectorising the loop. To add insult to injury, a typical V{k} may
become very large so a vectorised loop may hit memory limits. Thus it
may in fact be less than ideal to perform this loop implicitly.

I guess what I'm wondering is how one might, at least hypothetically,
optimise the loop away using other constructs. As always, the
vectorisation game reveals deep insights into the construction of
efficient MATLAB programs and it is fun and rewarding and all that :-)

But there is no need to put very much effort into it. I won't lose
any sleep over it if the vectorisation cannot be accomplished. It
would just be interesting to know how all the experts view the
problem. Am I missing something obvious, or is there no solution?
Any and all insight would be much appreciated.


Regards,
--
Bård Skaflestad <bardsk@math.ntnu.no>
PhD student of numerical analysis, dept. math. sciences
Norwegian University of Science and Technology (NTNU)

given your data layout (y=|m,1], V={|1,k|}), <no-looper>s could look
like this:

U=y.'*cell2mat(V);
% or
U=y.'*reshape([V{:}],k,m).';
% or
U=y.'*vertcat(V{:});

for obvious reasons, however, they are (markedly) slower!

us

"Bård Skaflestad" <bardsk@math.ntnu.no> wrote in message
news:dfwu1vpzipl.fsf@poisson.math.ntnu.no...
> More specifically, I have a 1 by m CELL array, V, (the contents of
> which are of homogeneous type--basically matrices of the same
> dimensions) and an m by 1 vector, y, of doubles. The loop in
question
> is this one
>
> U = y(1) * V{1};
> for k = 2:m,
> U = U + y(k) * V{k};
> end

If your data consist of m matrices of equal size, why not define them
 as a 3-d array instead of a 1-d cell array of matrices? This
 {might / might not} be easier to vectorize; I imagine it would be
 faster though.
 

 -Brandon

"Brandon Kuczenski" <brandon_kuczenski@kensingtonlabs.com> writes:

> If your data consist of m matrices of equal size, why not define them
> as a 3-d array instead of a 1-d cell array of matrices?

I guess I didn't specify the situation well enough. The contents of
the cell array may well be traditional n-by-n matrices in one
particular run (and they are in my test examples). However the
algorithm as such will work equally well if they are
n1-by-n2-by-...-by-nd arrays (I don't know wheter MATLAB has a
specific word for such a beast).

Hence the cell array makes sense (at least to me) as a top level
container. One approach to the vectorisation might be to just build
the V array as (the eqivalent of)

   % object comes from the outside
   nd = ndims(object);
   [siz{1:nd}] = size(object);

   % This computes the objects and this loop cannot be avoided
   for j = 1:m,
      % ...
      V(:,j) = obj(:);
      % ...
   end
   % ... Compute y

   U = reshape(V * y, siz{:})

This scheme will work but I don't find it particularly elegant, that's
all. Maybe it's just me. Thank you all very much for the suggestions
though.


Regards,
--
Bård Skaflestad <bardsk@math.ntnu.no>
PhD student of numerical analysis, dept. math. sciences
Norwegian University of Science and Technology