Thread Subject:

FAST algorithm to jenga matrix?

I have a GIANT sparse matrix with scattered non-trivial elements ranging from 1:N, then I need to remove a M non-trivial elements and maintain the cardinality from 1:N-M. Is there a fast way to do it? Here's an example to illustrate what I'm trying to do (N=8, M=2):

>> A=[ 0 0 8 0 0 ; 1 4 0 0 2; 0 5 3 0 0; 7 0 0 6 0]
A =
     0 0 8 0 0
     1 4 0 0 2
     0 5 3 0 0
     7 0 0 6 0

>> sort(nonzeros(A))
ans =
     1
     2
     3
     4
     5
     6
     7
     8

------------------------------
Numbers to delete: 2, 6


desiredMatrix =
     0 0 6(-2) 0 0
     1 3(-1) 0 0 X
     0 4(-1) 2(-1) 0 0
     5(-2) 0 0 X 0

desiredMatrix =
     0 0 6 0 0
     1 3 0 0 0
     0 4 2 0 0
     5 0 0 0 0

>> sort(nonzeros(desiredMatrix))
ans =
     1
     2
     3
     4
     5
     6

Because the matrix is huge (but sparse), I don't want to use for loops. I kind of have a feeling that there must be a slick way to do it with a different way of thinking, and there must be some MATLAB master-minds here who can come up with a slick one-or-two-liners. :)

Thanks in advance

"Hoi Wong" <wonghoi.ee@gmailNOSPAM.com> wrote in message <gqmlmt$6tp$1@fred.mathworks.com>...
> I have a GIANT sparse matrix with scattered non-trivial elements ranging from 1:N, then I need to remove a M non-trivial elements and maintain the cardinality from 1:N-M. Is there a fast way to do it? Here's an example to illustrate what I'm trying to do (N=8, M=2):
>
> >> A=[ 0 0 8 0 0 ; 1 4 0 0 2; 0 5 3 0 0; 7 0 0 6 0]
> A =
> 0 0 8 0 0
> 1 4 0 0 2
> 0 5 3 0 0
> 7 0 0 6 0
>
> >> sort(nonzeros(A))
> ans =
> 1
> 2
> 3
> 4
> 5
> 6
> 7
> 8
>
> ------------------------------
> Numbers to delete: 2, 6
>
>
> desiredMatrix =
> 0 0 6(-2) 0 0
> 1 3(-1) 0 0 X
> 0 4(-1) 2(-1) 0 0
> 5(-2) 0 0 X 0
>
> desiredMatrix =
> 0 0 6 0 0
> 1 3 0 0 0
> 0 4 2 0 0
> 5 0 0 0 0
>
> >> sort(nonzeros(desiredMatrix))
> ans =
> 1
> 2
> 3
> 4
> 5
> 6
>
> Because the matrix is huge (but sparse), I don't want to use for loops. I kind of have a feeling that there must be a slick way to do it with a different way of thinking, and there must be some MATLAB master-minds here who can come up with a slick one-or-two-liners. :)
>
> Thanks in advance

  I'm afraid this isn't a one- or two-liner, but an eight-liner, Hoi. I couldn't think of anything shorter. Let d be a vector of the numbers to "delete".

 [r,c,v] = find(A);
 [v,p] = sort(v);
 v = 1;
 v(d) = 0;
 v = cumsum(v);
 v(d) = 0;
 v(p) = v;
 B = sparse(r,c,v,size(A,1),size(A,2));

B is the desired matrix.

  This depends on your statement that the non-zero elements of A are 1:N and those of B are are to be 1:N-M where M = size(d,2).

Roger Stafford

Here is a five-liner solution, but not much fundamentally different to Roger's solution:

A=[ 0 0 8 0 0 ;
    1 4 0 0 2;
    0 5 3 0 0;
    7 0 0 6 0];

d = [2 6]'; % To be removed

[I J Val]=find(A);
f=ismember(unique(Val),d);
NewVal=cumsum(1-f);
NewVal(f)=0;
B=sparse(I,J,NewVal(Val),size(A,1),size(A,2));

% Alternatively, if no matrix duplicating is required
% then the last line changes to this

[I J Val]=find(A);
f=ismember(unique(Val),d);
NewVal=cumsum(1-f);
NewVal(f)=0;
A(sub2ind(size(A),I,J))=NewVal(Val);

% Bruno

Here is a four-liner solution. I could merge the 2nd and 3rd lines but it does not bring any advantage beside having less lines:

[I J Val]=find(A);
u = unique(Val); % 1:n
[f NewVal]=ismember(u,setdiff(u,d));
B=sparse(I,J,NewVal(Val),size(A,1),size(A,2));

% Bruno

For fun, two-liner solution:

[f NewVal]=ismember(1:max(nonzeros(A)),setdiff(1:max(nonzeros(A)),d));
A(A~=0)=NewVal(nonzeros(A));

Now how to get to one-liner solution (challenge proposed by Roger)?

Bruno

>
> Now how to get to one-liner solution (challenge proposed by Roger)?
>

A=[ 0 0 8 0 0 ;
    1 4 0 0 2;
    0 5 3 0 0;
    7 0 0 6 0];
A=sparse(A)

d = [2 6]'; % To be removed

% One-liner solution !!!
A(A~=0) = subsref(subsasgn([],substruct('()',...
    {setdiff((1:max(nonzeros(A))),d)}), ...
     1:length(setdiff((1:max(nonzeros(A))),d))),...
     substruct('()',{nonzeros(A)}))

% Bruno

Sorry there is a bug in the previous code, it should be this:

% One-liner solution !!!
A(A~=0) = subsref(subsasgn(zeros(1,max(nonzeros(A))),substruct('()',...
    {setdiff((1:max(nonzeros(A))),d)}), ...
     1:length(setdiff((1:max(nonzeros(A))),d))),...
     substruct('()',{nonzeros(A)}))

% Bruno

% Another one-liner solution !!!
A(A~=0) = subsref(cumsum(~ismember(1:max(nonzeros(A)),d)).* ...
   ~ismember(1:max(nonzeros(A)),d),...
   substruct('()',{nonzeros(A)}))

% Bruno

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gqn6u7$1s2$1@fred.mathworks.com>...
> ......
> [r,c,v] = find(A);
> [v,p] = sort(v);
> v = 1;
> v(d) = 0;
> v = cumsum(v);
> v(d) = 0;
> v(p) = v;
> B = sparse(r,c,v,size(A,1),size(A,2));
> ......

  Sorry about the careless mistake, Hoi. The third line should read:

 v = ones(size(v));

Roger Stafford

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gqo4f5$qf8$1@fred.mathworks.com>...
> % Another one-liner solution !!!
> A(A~=0) = subsref(cumsum(~ismember(1:max(nonzeros(A)),d)).* ...
> ~ismember(1:max(nonzeros(A)),d),...
> substruct('()',{nonzeros(A)}))
>
> % Bruno

Thanks for your quick reply. I see a lot of ismember, unique, setdiff here which are famous for being slow. I'll set up a time test for all your solutions in a couple of days and see which one is the fastest :)

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gqo779$d3g$1@fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gqn6u7$1s2$1@fred.mathworks.com>...
> > ......
> > [r,c,v] = find(A);
> > [v,p] = sort(v);
> > v = 1;
> > v(d) = 0;
> > v = cumsum(v);
> > v(d) = 0;
> > v(p) = v;
> > B = sparse(r,c,v,size(A,1),size(A,2));
> > ......
>
> Sorry about the careless mistake, Hoi. The third line should read:
>
> v = ones(size(v));
>
> Roger Stafford

Thanks Roger! I've never given that much thought to the extended parameters for find(), sort() and a 5-argument use for sparse() though I've been using them for a while (sparse is quite new to me though. I'm developing a sparse_cell class/dataType and jengaMatrix is a piece of the puzzle)

My first algorithm was embarassing.......it's complicated, uses cellfun, sum, and runs 100000 times slower than any of yours, and it does not work for non-unique deletion list. Turns out that your 8-line solution is the fastest of all as I expected (because they are all built-in functions). Simple test is the matrix mentioned in my first post, and the second data set was captured from my project.

Here's the link to all of your algorithms and mine as well. jengaMatrixSpeedTest tests them all and generate the report below:

Does all algorithm give the same result for the simple test? true
---------------------------------------------------------------
Is the test matrices cardinal? true
Cardinality preserved? true
Is the deletion list unique? false
Roger: 0.00110589
Bruno1: 0.00870681
Bruno2: 0.02111930
Bruno4: 0.00462781
Bruno5: 0.00282878
Does all algorithm give the same result for the stress test (with non-unique deletion items)? true
Cardinality preserved? true
---------------------------------------------------------------
Hoi: 110.50091451
Roger: 0.00098781
Bruno1: 0.00648331
Bruno2: 0.00672234
Bruno4: 0.00160589
Bruno5: 0.00117171
Does all algorithm give the same result for the stress test (with unique deletion items)? true
Cardinality preserved? true