Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Reducing memory requirements for tiled matrices

Subject: Reducing memory requirements for tiled matrices

From: Harry Commin

Date: 13 Nov, 2012 21:32:18

Message: 1 of 6

I need to perform element-by-element multiplication between two "tiled" matrices (i.e. where relatively few unique values are repeated in a structured, tiled manner). However, these matrices (formed by a double Kronecker product) are large and I only have enough memory to process one of them at a time.

Using (x) to denote a Kronecker product, the required operation is:

(ones(1,Ms) (x) F (x) ones(Ns,1)) .* (ones(Nf,1) (x) S (x) ones(1,Mf))

where F is (Nf*N0 x Mf)
and S is (Ns*N0 x Ms)

Is there a computationally efficient way of getting this result? I feel that so few unique values should not need to hog so much memory. I know I can replace ones() (x) A with a repmat() operation, but other than that I'm stumped.

Subject: Reducing memory requirements for tiled matrices

From: Roger Stafford

Date: 14 Nov, 2012 01:19:12

Message: 2 of 6

"Harry Commin" wrote in message <k7ue91$mh1$1@newscl01ah.mathworks.com>...
> I need to perform element-by-element multiplication between two "tiled" matrices (i.e. where relatively few unique values are repeated in a structured, tiled manner). However, these matrices (formed by a double Kronecker product) are large and I only have enough memory to process one of them at a time.
>
> Using (x) to denote a Kronecker product, the required operation is:
>
> (ones(1,Ms) (x) F (x) ones(Ns,1)) .* (ones(Nf,1) (x) S (x) ones(1,Mf))
>
> where F is (Nf*N0 x Mf)
> and S is (Ns*N0 x Ms)
>
> Is there a computationally efficient way of getting this result? I feel that so few unique values should not need to hog so much memory. I know I can replace ones() (x) A with a repmat() operation, but other than that I'm stumped.
- - - - - - - -
  Your final kronecker product will be an Nf*Ns*N0 by Mf*Ms matrix in size. Furthermore each of its elements is different in general - that is, each is a product of a different pair of factors from F and S. Therefore if you are having memory problems, this size itself is a major part of that memory usage. Presumably you could use a set of for-loops to directly generate this result and thereby avoid having to store intermediate 'kron' products, but I doubt if you would gain much more than a one-third savings in memory usage this way.

  As I see it your principal difficulty is that even though there may be relatively few unique values in each of the two separate double kronecker products, when they are element-by-element multiplied together, each of the element products in the result is as I say unique.

  Perhaps the real question to ask is what you intend to do with these final matrices if you have a number of them to generate. You won't have enough memory to store more than a very few at any one time. Perhaps there is some shortcut in achieving this purpose that can be accomplished without creating these huge matrices.

Roger Stafford

Subject: Reducing memory requirements for tiled matrices

From: Roger Stafford

Date: 14 Nov, 2012 07:49:22

Message: 3 of 6

"Roger Stafford" wrote in message <k7urig$875$1@newscl01ah.mathworks.com>...
> ....... Presumably you could use a set of for-loops to directly generate this result and thereby avoid having to store intermediate 'kron' products, ......
- - - - - - - - -
  The following code uses the for-loop method I mentioned earlier. It will compute your element-by-element product of the two double kronecker products you described using your definitions of N0, Nf, Ns, Mf, and Ms for the sizes involved. The only matrix it creates is 'K' containing the desired result, so it will save you memory space, but at the cost of slower execution than with the use of the 'kron' function.

K = zeros(Nf*Ns*N0,Mf*Ms);
for i1 = 1:Nf*N0
 for j1 = 1:Mf
  t = F(i1,j1);
  for i2 = 1:Ns
   for j2 = 1:Ms
    K(i2+Ns*(i1-1),j1+Mf*(j2-1)) = t;
   end
  end
 end
end
for i1 = 1:Ns*N0
 for j1 = 1:Ms
  t = S(i1,j1);
  for i2 = 1:Nf
   for j2 = 1:Mf
    K(i1+Ns*N0*(i2-1),j2+Mf*(j1-1)) = ...
       K(i1+Ns*N0*(i2-1),j2+Mf*(j1-1))*t;
   end
  end
 end
end

Roger Stafford

Subject: Reducing memory requirements for tiled matrices

From: Harry Commin

Date: 14 Nov, 2012 11:58:14

Message: 4 of 6

> The following code uses the for-loop method I mentioned earlier ... it will save you memory space, but at the cost of slower execution than with the use of the 'kron' function.

Yes, using multiple loops was actually my starting point, but then I removed the loops in an attempt to speed up execution. This worked pretty well for modestly-sized matrices (allowing execution to finish within a day or two). However, I've hit a wall with this slightly larger data size in that I now run out of memory.

I suppose a brute-force approach would be to get my hands on a 64-bit architecture. Or I could try keeping "some" loops and not others... but it's difficult to identify a good trade-off.

Subject: Reducing memory requirements for tiled matrices

From: Steven_Lord

Date: 14 Nov, 2012 14:53:51

Message: 5 of 6



"Harry Commin" <hmc05_remove_this_@ic.ac.uk> wrote in message
news:k8010m$98f$1@newscl01ah.mathworks.com...
>> The following code uses the for-loop method I mentioned earlier ... it
>> will save you memory space, but at the cost of slower execution than with
>> the use of the 'kron' function.
>
> Yes, using multiple loops was actually my starting point, but then I
> removed the loops in an attempt to speed up execution. This worked pretty
> well for modestly-sized matrices (allowing execution to finish within a
> day or two). However, I've hit a wall with this slightly larger data size
> in that I now run out of memory.
>
> I suppose a brute-force approach would be to get my hands on a 64-bit
> architecture. Or I could try keeping "some" loops and not others... but
> it's difficult to identify a good trade-off.

Those are two options, but first I recommend that you answer Roger's "real
question":

"Roger Stafford" wrote:
> > Perhaps the real question to ask is what you intend to do with these
> > final matrices if you have a number of them to generate. You won't have
> > enough memory to store more than a very few at any one time. Perhaps
> > there is some shortcut in achieving this purpose that can be
> > accomplished without creating these huge matrices.

This group has readers and posters with experience in many different
application areas. One of them may recognize your description of your goal
as a common problem in their application area and suggest an algorithm or
function that avoids having to create such matrices altogether.

If not, switching to a 64-bit OS and 64-bit MATLAB or even to a parallel
computing cluster using Parallel Computing Toolbox and MATLAB Distributed
Computing Server are other potential options.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Subject: Reducing memory requirements for tiled matrices

From: Roger Stafford

Date: 14 Nov, 2012 16:27:16

Message: 6 of 6

"Harry Commin" wrote in message <k8010m$98f$1@newscl01ah.mathworks.com>...
> Yes, using multiple loops was actually my starting point, but then I removed the loops in an attempt to speed up execution. This worked pretty well for modestly-sized matrices (allowing execution to finish within a day or two). However, I've hit a wall with this slightly larger data size in that I now run out of memory.
>
> I suppose a brute-force approach would be to get my hands on a 64-bit architecture. Or I could try keeping "some" loops and not others... but it's difficult to identify a good trade-off.
- - - - - - - - - - -
   Just in case you are still interested in "loops" solutions, here is a modification of the code I sent before. I think you can replace the repmat term with just the scalar F(i1,j1). I had to use the repmat version on my very ancient system.

K = zeros(Nf*Ns*N0,Mf*Ms);
for i1 = 1:Nf*N0
 for j1 = 1:Mf
  K(1+Ns*(i1-1):Ns*i1,j1:Mf:j1+Mf*(Ms-1)) = repmat(F(i1,j1),Ns,Ms);
 end
end
for i1 = 1:Ns*N0
 for j1 = 1:Ms
  i2 = i1:Ns*N0:i1+Ns*N0*(Nf-1);
  j2 = 1+Mf*(j1-1):Mf*j1;
  K(i2,j2) = K(i2,j2)*S(i1,j1);
 end
end

Roger Stafford

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us