MATLAB Central Newsreader - sparse matrix reordering

sparse matrix reordering

A B — Fri, 12 Dec 2008 16:28:02 -0500

Hi,

I'm having a symmetric sparse matrix and I want to reorder it, which I am doing
with:

A = sparse(row,col,val);
p=symamd(A);

That of course works fine...

Now, as I often change the values of the matrix A, but not it's structure I wanted to keep the three vectors, row, col, val and just reorder in the vectors row and col. That way I only have to work with the vector val and not perform operations on a sparse matrix.

So I did:
reorder_row = p(row);
reorder_col = p(col);

However the matrices

A1 = sparse(reorder_row,reorder_col,val);
A2 = A(p,p)

don't have the same structure. Obviously, A2's structure is as expected, but A1 is completly wrong.

I just got some knot in my brain and don't see the reason for this. Can anyone help me and explain me why it's different and how I would properly do it.

Thank you very very much

Re: sparse matrix reordering

Tim Davis — Fri, 12 Dec 2008 22:31:02 -0500

"A B" <gitsnedbutzi@hotmail.com> wrote in message <ghu3ei$nl7$1@fred.mathworks.com>...
> Hi,
>
> I'm having a symmetric sparse matrix and I want to reorder it, which I am doing
> with:
>
> A = sparse(row,col,val);
> p=symamd(A);
>
> That of course works fine...
>
> Now, as I often change the values of the matrix A, but not it's structure I wanted to keep the three vectors, row, col, val and just reorder in the vectors row and col. That way I only have to work with the vector val and not perform operations on a sparse matrix.
>
> So I did:
> reorder_row = p(row);
> reorder_col = p(col);
>
> However the matrices
>
> A1 = sparse(reorder_row,reorder_col,val);
> A2 = A(p,p)
>
> don't have the same structure. Obviously, A2's structure is as expected, but A1 is completly wrong.
>
> I just got some knot in my brain and don't see the reason for this. Can anyone help me and explain me why it's different and how I would properly do it.
>
> Thank you very very much

The vector p can be considered a function whose input is k where k is a row/column index in the *new* matrix, and the output is i where i is a row/column of the old (unpermuted) matrix. that is, i=p(k). But if you want to change the *old* row/column indices to the *new* ones to use in sparse(...) then you need the inverse of this function, k=inverse_of_p(i). You can compute the inverse permutation vector using:

n = size(A,1);
invp = zeros (1,n) ;
invp (p) = 1:n ;

then do

A1 = sparse (invp (row), invp (col), val) ;

by the way, p=amd(A) is faster than symamd.

Re: sparse matrix reordering

A B — Sun, 14 Dec 2008 08:38:03 -0500

> The vector p can be considered a function whose input is k where k is a row/column index in the *new* matrix, and the output is i where i is a row/column of the old (unpermuted) matrix. that is, i=p(k). But if you want to change the *old* row/column indices to the *new* ones to use in sparse(...) then you need the inverse of this function, k=inverse_of_p(i). You can compute the inverse permutation vector using:
>
> n = size(A,1);
> invp = zeros (1,n) ;
> invp (p) = 1:n ;
>
> then do
>
> A1 = sparse (invp (row), invp (col), val) ;
>
> by the way, p=amd(A) is faster than symamd.

if there's a sparse matrix problem, there's always a tim davis :-)

i would never have come up with using the inverse, as i always considered the vector p to be a function whose's input is the row/column index of the old matrix and the output the indices of the new one.

thanks, that helped a lot.