Prev: mex
Next: gravity help
From: Bruno Luong on 10 Jul 2010 05:45
"Ross Anderson" <rpa5nospam(a)cornell.edu> wrote in message <i180dd$sid$1(a)fred.mathworks.com>...
> Hi all,
>
> I have Ax=B where A and B are sparse. I want to reduce this so any row ax=b is unique, but I don't have the resources to make A and B full first. If I could, I could say
>
> Afull = [full(A) full(B)];
> [newmat,index] = unique(Afull,'rows','first');
> repeatedIndex = setdiff(1:size(Afull,1),index);
> Af = full(A);
> Bf = full(B);
> Af(repeatedIndex,:) = [];
> Bf(repeatedIndex)=[];
> A = sparse(Af);
> B = sparse(Bf);
>
> but is there a way to do this without un-sparsifying A and B?
> I have the components of A and B in vectors
> A = sparse(rows(:,1),rows(:,2),rows(:,3),numrows,sizeX);
> and I can guarantee that for a row the non-zero elements are in ascending order. I was thinking I might search the matrix rows for a block [rows(:,2) rows(:,3)] with a different rows(:,1). But that seems overly complicated and slow.
>
> Suggestions?

I can't see any short and efficient way to Matlab code this problem. But here are few ideas:

We can define a relational order between two rows r1 and r2 as following

r1 < r2 <=> issorted([r1; r2], 'rows');

% Example:

>> r1=ceil(10*rand(1,5));
>> r2=ceil(10*rand(1,5));
>> [r1; r2]

ans =

1 1 9 7 4
10 1 5 4 8

>> issorted([r1; r2],'rows')

ans =

1

Now you can use this specific definition to sort the rows of the concatenated sparse matrix. You have to code your own sorting algorithm though to make it works on SPARSE without converting to FULL, because the comparison operator is specific and no built-in sorting is able to do that.

After sorting, you can easily remove duplicated rows because they are now grouped together.

Two practical considerations: It is better to program a sorting without moving the matrix data, but keep the sorted index. You might also work on COLUMN rather than ROW because extraction column on sparse matrix is much faster than row due to the internal storing.

Bruno
 | 
Pages: 1
Prev: mex
Next: gravity help