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:
Zeroing columns in sparse matrix is slow

Subject: Zeroing columns in sparse matrix is slow

From: Cesar

Date: 15 Jun, 2009 04:09:01

Message: 1 of 9

I am developing a Finite Element Program using sparse matrices in Matlab 7.4 (2007a)
The size of the global stiffness matrix (GKConstant) is 67932x67932 (4.6148e+009 elements) and with 479047 nonzero elements.
To apply boundary conditions I execute the following lines:

    GKConstant(:,ConstDof)=0;
    GKConstant=GKConstant';
    GKConstant(:,ConstDof)=0;

    DiagForBC=spdiags(GKConstant,0);
    DiagForBC(ConstDof)=BCFact*ones(numel(ConstDof),1);
    GKConstant=spdiags(DiagForBC,0,GKConstant);

where ConstDof are the rows and columns that need to be zeroed out.

The issue I have is that the first line:
    GKConstant(:,ConstDof)=0;
takes 18 seconds to execute (as measured by the profiler) and the rest just a fraction of a second.

Any idea if it is possible to get this done in a more efficient way.

Subject: Zeroing columns in sparse matrix is slow

From: Siyi

Date: 15 Jun, 2009 06:15:08

Message: 2 of 9

One solution:

% data;
r = sprand(67932,67932,479047/67932^2); % GKConstant;
d = unique(randi(67932,1000,1)); % ConstDof;

% engine;

[sr,sc] = find(r(:,d));
r(sub2ind(size(r),sr,d(sc))) = 0;

Subject: Zeroing columns in sparse matrix is slow

From: Bruno Luong

Date: 15 Jun, 2009 06:28:01

Message: 3 of 9

Siyi <Mr.Siyi.Deng@gmail.com> wrote in message <94a2ba73-ca69-4b02-b5c2-4213ae21bb70@c20g2000prh.googlegroups.com>...
> One solution:
>
> % data;
> r = sprand(67932,67932,479047/67932^2); % GKConstant;
> d = unique(randi(67932,1000,1)); % ConstDof;
>
> % engine;
>
> [sr,sc] = find(r(:,d));
> r(sub2ind(size(r),sr,d(sc))) = 0;

Subject: Zeroing columns in sparse matrix is slow

From: Bruno Luong

Date: 15 Jun, 2009 06:41:01

Message: 4 of 9

Siyi <Mr.Siyi.Deng@gmail.com> wrote in message <94a2ba73-ca69-4b02-b5c2-4213ae21bb70@c20g2000prh.googlegroups.com>...
> One solution:
>
> % data;
> r = sprand(67932,67932,479047/67932^2); % GKConstant;
> d = unique(randi(67932,1000,1)); % ConstDof;
>
> % engine;
>
> [sr,sc] = find(r(:,d));
> r(sub2ind(size(r),sr,d(sc))) = 0;

One good habit to be acquired when working with sparse is never use linear indexing, because the linear index can be larger than 2^31-1 for large matrix (actual not so large, a matrix n x n with n>=46341).

Furthermore there is a nasty bug discussed here http://www.mathworks.com/matlabcentral/newsreader/view_thread/247772

A good alternative is use sparse acess in FEX

http://www.mathworks.com/matlabcentral/fileexchange/23488

GKConstant = sprand(67932,67932,479047/67932^2);

ConstDof=100;
n=size(GKConstant,2);

% Set a row to zero
GKConstant=setsparse(GKConstant,1:n,ConstDof+zeros(1,n),0);

Bruno

Subject: Zeroing columns in sparse matrix is slow

From: Siyi Deng

Date: 15 Jun, 2009 06:45:31

Message: 5 of 9

On Jun 14, 11:41 pm, "Bruno Luong" <b.lu...@fogale.findmycountry>
wrote:
> Siyi <Mr.Siyi.D...@gmail.com> wrote in message <94a2ba73-ca69-4b02-b5c2-4213ae21b...@c20g2000prh.googlegroups.com>...
> > One solution:
>
> > % data;
> > r = sprand(67932,67932,479047/67932^2); % GKConstant;
> > d = unique(randi(67932,1000,1)); % ConstDof;
>
> > % engine;
>
> > [sr,sc] = find(r(:,d));
> > r(sub2ind(size(r),sr,d(sc))) = 0;
>
> One good habit to be acquired when working with sparse is never use linear indexing, because the linear index can be larger than 2^31-1 for large matrix (actual not so large, a matrix n x n with n>=46341).
>
> Furthermore there is a nasty bug discussed herehttp://www.mathworks.com/matlabcentral/newsreader/view_thread/247772
>
> A good alternative is use sparse acess in FEX
>
> http://www.mathworks.com/matlabcentral/fileexchange/23488
>
> GKConstant = sprand(67932,67932,479047/67932^2);
>
> ConstDof=100;
> n=size(GKConstant,2);
>
> % Set a row to zero
> GKConstant=setsparse(GKConstant,1:n,ConstDof+zeros(1,n),0);
>
> Bruno

Thanks for this info. Does this bug apply to 64-bit systems as well?

Subject: Zeroing columns in sparse matrix is slow

From: Bruno Luong

Date: 15 Jun, 2009 06:55:03

Message: 6 of 9

Siyi Deng <mr.siyi.deng@gmail.com> wrote in message <c806e5cd-03fa-49ec-a394-9547272b95ec@y6g2000prf.googlegroups.com>...

> Thanks for this info. Does this bug apply to 64-bit systems as well?

No, BUG occurs only for just 32-bit machine.

Bruno

Subject: Zeroing columns in sparse matrix is slow

From: Cesar

Date: 16 Jun, 2009 18:26:01

Message: 7 of 9

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <h14qdt$qt5$1@fred.mathworks.com>...
> Siyi <Mr.Siyi.Deng@gmail.com> wrote in message <94a2ba73-ca69-4b02-b5c2-4213ae21bb70@c20g2000prh.googlegroups.com>...
> > One solution:
> >
> > % data;
> > r = sprand(67932,67932,479047/67932^2); % GKConstant;
> > d = unique(randi(67932,1000,1)); % ConstDof;
> >
> > % engine;
> >
> > [sr,sc] = find(r(:,d));
> > r(sub2ind(size(r),sr,d(sc))) = 0;
>
> One good habit to be acquired when working with sparse is never use linear indexing, because the linear index can be larger than 2^31-1 for large matrix (actual not so large, a matrix n x n with n>=46341).
>
> Furthermore there is a nasty bug discussed here http://www.mathworks.com/matlabcentral/newsreader/view_thread/247772
>
> A good alternative is use sparse acess in FEX
>
> http://www.mathworks.com/matlabcentral/fileexchange/23488
>
> GKConstant = sprand(67932,67932,479047/67932^2);
>
> ConstDof=100;
> n=size(GKConstant,2);
>
> % Set a row to zero
> GKConstant=setsparse(GKConstant,1:n,ConstDof+zeros(1,n),0);
>
> Bruno

I tried using setsparse but had the following problem:
ConstDof is actually a vector (37,000 elements) and so I am trying to zero out several columns with one instruction. To do this with setsparse, I would have to generate the row and column matrices and I would actually run out of memory (I am running in 32bit).

Subject: Zeroing columns in sparse matrix is slow

From: Bruno Luong

Date: 16 Jun, 2009 19:04:02

Message: 8 of 9

"Cesar " <cesar.carrasco@att.net> wrote in message <h18o3p$ov5$1@fred.mathworks.com>...


> I tried using setsparse but had the following problem:
> ConstDof is actually a vector (37,000 elements) and so I am trying to zero out several columns with one instruction. To do this with setsparse, I would have to generate the row and column matrices and I would actually run out of memory (I am running in 32bit).

You might filter out the indexes of non-zero elements before set them to zero. For example:

% Random matrix
GKConstant=sparse(ceil(rand(10)*9)-3);
ConstDof=[2 4]; % columns to be set to 0
full(GKConstant) % Display

% Set-to-zero engine
[I J]=find(GKConstant);
idxofzero = ismember(J,ConstDof); % Replace J by I to lock the rows
GKConstant=setsparse(GKConstant,I(idxofzero),J(idxofzero),0);

% Check
full(GKConstant)

% Bruno

Subject: Zeroing columns in sparse matrix is slow

From: Cesar

Date: 17 Jun, 2009 01:17:02

Message: 9 of 9

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <h18qb2$p95$1@fred.mathworks.com>...
> "Cesar " <cesar.carrasco@att.net> wrote in message <h18o3p$ov5$1@fred.mathworks.com>...
>
>
> > I tried using setsparse but had the following problem:
> > ConstDof is actually a vector (37,000 elements) and so I am trying to zero out several columns with one instruction. To do this with setsparse, I would have to generate the row and column matrices and I would actually run out of memory (I am running in 32bit).
>
> You might filter out the indexes of non-zero elements before set them to zero. For example:
>
> % Random matrix
> GKConstant=sparse(ceil(rand(10)*9)-3);
> ConstDof=[2 4]; % columns to be set to 0
> full(GKConstant) % Display
>
> % Set-to-zero engine
> [I J]=find(GKConstant);
> idxofzero = ismember(J,ConstDof); % Replace J by I to lock the rows
> GKConstant=setsparse(GKConstant,I(idxofzero),J(idxofzero),0);
>
> % Check
> full(GKConstant)
>
> % Bruno

Bruno,
Your solution worked perfectly.
Now that section of the code only takes 0.5 seconds instead of the 18.
Thanks

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