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:
Speeding up calculation of matrix

Subject: Speeding up calculation of matrix

From: Michael

Date: 26 Mar, 2012 19:09:12

Message: 1 of 6

Hi,

I am calculating a matrix M from two column vectors and two coefficients, calculated like so:

%%%%%%%%%%%%%
x=rand(10,1);
y=rand(10,1);
fit_x = 2;
fit_y = 3;

% initialize M
nRows = length(x);
nCols = (fit_x+1)*(fit_y+1);
M=ones(nRows,nCols);

% build each column of M
iCol = 1;
for px=0:fit_x
    for py=0:fit_y
        M(:,iCol)=x.^px .* y.^py;
        iCol=iCol+1;
    end
end

%%%%%%%%%%%%%

where x and y are normally input vectors, and fit_x and fit_y are input scalars. This function is called many times by my code, and after profiling, a significant portion of time is spent generating this M matrix.

Is there a better way to do this? I feel like I am overlooking a one-line vectorized solution to this, replacing the loop. I have tried:

%%%%%%%%%%%%

x_power = kron(0:fit_x,ones(nRows,fit_y+1));
y_power = repmat(0:fit_y,nRows,fit_x+1);

    
x2 = repmat(x,1,nCols);
y2 = repmat(y,1,nCols);
    
M2 = x2.^x_power .* y2.^y_power;
%%%%%%%%%%%%

to compute the matrix in one shot, but it takes significantly longer - in fact, each call to repmat in the second method takes about as long as generating the matrix using the double loop. Any suggestions?

Subject: Speeding up calculation of matrix

From: Roger Stafford

Date: 26 Mar, 2012 19:43:10

Message: 2 of 6

"Michael" wrote in message <jkqeso$bup$1@newscl01ah.mathworks.com>...
> Hi,
>
> I am calculating a matrix M from two column vectors and two coefficients, calculated like so:
>
> %%%%%%%%%%%%%
> x=rand(10,1);
> y=rand(10,1);
> fit_x = 2;
> fit_y = 3;
>
> % initialize M
> nRows = length(x);
> nCols = (fit_x+1)*(fit_y+1);
> M=ones(nRows,nCols);
>
> % build each column of M
> iCol = 1;
> for px=0:fit_x
> for py=0:fit_y
> M(:,iCol)=x.^px .* y.^py;
> iCol=iCol+1;
> end
> end
>
> %%%%%%%%%%%%%
>
> where x and y are normally input vectors, and fit_x and fit_y are input scalars. This function is called many times by my code, and after profiling, a significant portion of time is spent generating this M matrix.
>
> Is there a better way to do this? I feel like I am overlooking a one-line vectorized solution to this, replacing the loop. I have tried:
>
> %%%%%%%%%%%%
>
> x_power = kron(0:fit_x,ones(nRows,fit_y+1));
> y_power = repmat(0:fit_y,nRows,fit_x+1);
>
>
> x2 = repmat(x,1,nCols);
> y2 = repmat(y,1,nCols);
>
> M2 = x2.^x_power .* y2.^y_power;
> %%%%%%%%%%%%
>
> to compute the matrix in one shot, but it takes significantly longer - in fact, each call to repmat in the second method takes about as long as generating the matrix using the double loop. Any suggestions?
- - - - - - - - -
 [py,px] = ndgrid(0:fit_y,0:fit_x);
 M = bsxfun(@power,x,px(:).')+bsxfun(@power,y,py(:).');

Roger Stafford

Subject: Speeding up calculation of matrix

From: Roger Stafford

Date: 26 Mar, 2012 19:48:13

Message: 3 of 6

"Roger Stafford" wrote in message <jkqgse$jaa$1@newscl01ah.mathworks.com>...
> [py,px] = ndgrid(0:fit_y,0:fit_x);
> M = bsxfun(@power,x,px(:).')+bsxfun(@power,y,py(:).');
>
> Roger Stafford
- - - - - - - - -
  Perhaps this is a little better:

 [py,px] = ndgrid(0:fit_y,0:fit_x);
 M = bsxfun(@power,x,reshape(px,1,[]))+bsxfun(@power,y,reshape(py,1,[]));

Roger Stafford

Subject: Speeding up calculation of matrix

From: Roger Stafford

Date: 26 Mar, 2012 20:57:17

Message: 4 of 6

"Roger Stafford" wrote in message <jkqh5t$ka3$1@newscl01ah.mathworks.com>...
> [py,px] = ndgrid(0:fit_y,0:fit_x);
> M = bsxfun(@power,x,reshape(px,1,[]))+bsxfun(@power,y,reshape(py,1,[]));
- - - - - - - - - -
  As a third alternative you could try this to minimize the total number of power operations (70 vs 240):

 n = size(x,1);
 M = reshape(bsxfun(@plus,bsxfun(@power,y,0:fit_y), ...
             reshape(bsxfun(@power,x,0:fit_x),n,1,[])) ,n,[]);
  
Roger Stafford

Subject: Speeding up calculation of matrix

From: Michael

Date: 27 Mar, 2012 13:43:14

Message: 5 of 6

"Roger Stafford" wrote in message <jkql7d$5r1$1@newscl01ah.mathworks.com>...
> "Roger Stafford" wrote in message <jkqh5t$ka3$1@newscl01ah.mathworks.com>...
> > [py,px] = ndgrid(0:fit_y,0:fit_x);
> > M = bsxfun(@power,x,reshape(px,1,[]))+bsxfun(@power,y,reshape(py,1,[]));
> - - - - - - - - - -
> As a third alternative you could try this to minimize the total number of power operations (70 vs 240):
>
> n = size(x,1);
> M = reshape(bsxfun(@plus,bsxfun(@power,y,0:fit_y), ...
> reshape(bsxfun(@power,x,0:fit_x),n,1,[])) ,n,[]);
>
> Roger Stafford

Thanks Roger - I am getting about a 30% reduction in run time using this method (after replacing the first function call to @times instead of @plus). Exactly the kind of solution I was looking for. The solution using ndgrid ran a bit slower - the ndgrid call took a while to compute.

Thanks again,
Michael

Subject: Speeding up calculation of matrix

From: Roger Stafford

Date: 27 Mar, 2012 15:21:12

Message: 6 of 6

"Michael" wrote in message <jksg5i$sd8$1@newscl01ah.mathworks.com>...
> Thanks Roger - I am getting about a 30% reduction in run time using this method (after replacing the first function call to @times instead of @plus). Exactly the kind of solution I was looking for. The solution using ndgrid ran a bit slower - the ndgrid call took a while to compute.
>
> Thanks again,
> Michael
- - - - - - - -
  I'll have to get my eyes checked. Somehow that ".*" operation registered in my head as a plus sign. Sorry!

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