Thread Subject:

Permutation of sparse matrices

I'm working on a combination graph theory/matrix operation research project, and right now I'm having some trouble with some Matlab stuff, at least, syntactically speaking. What I need to do is basically reorder a matrix based on a list of numbers. For example, for a 4 x 4 matrix like so:

1 1 1 1
1 1 0 0
1 0 1 0
1 0 0 1

and an ordering of [4 3 2 1], the re-ordered matrix would be:

1 0 0 1
0 1 0 1
0 0 1 1
1 1 1 1

This can be achieved through pre and post multiplication with a permutation matrix with the 1 of each column being in the row of the corresponding column of the ordering. The permutation matrix for the above example would be this:

0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0

Is there any faster way to change the given matrix in this way that wouldn't require such huge multiplications? The matrices that I'm using have tens of thousands of rows and columns. Thanks for the help in advance.

~John

John Montgomery <experimentmonty@gmail.com> wrote in message <19825854.1231902490721.JavaMail.jakarta@nitrogen.mathforum.org>...
> ......
> Is there any faster way to change the given matrix in this way that wouldn't require such huge multiplications? The matrices that I'm using have tens of thousands of rows and columns. Thanks for the help in advance.
> .....

  You are apparently permuting the rows and columns of your matrix in the same way, though I can't be sure since your examples are all symmetric. If so, you can do it this way:

 p = [4 3 2 1];
 B = A(p,p);

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gkjmse$anf$1@fred.mathworks.com>...
> John Montgomery <experimentmonty@gmail.com> wrote in message <19825854.1231902490721.JavaMail.jakarta@nitrogen.mathforum.org>...
> > ......
> > Is there any faster way to change the given matrix in this way that wouldn't require such huge multiplications? The matrices that I'm using have tens of thousands of rows and columns. Thanks for the help in advance.
> > .....
>
> You are apparently permuting the rows and columns of your matrix in the same way, though I can't be sure since your examples are all symmetric. If so, you can do it this way:
>
> p = [4 3 2 1];
> B = A(p,p);
> ......

  I have read your description more carefully, John. You stated "... pre and post multiplication with a permutation matrix ..." by which I understand you to mean that both the two permutation matrices for pre and post multiplication are to be the same matrix. In that case the code I gave you was incorrect and should be revised to this:

 p = randperm(size(A,1));
 A(p,:) = A(:,p);

or to preserve A,

 B = zeros(4);
 B(p,:) = A(:,p);

  There is an obvious generalization for this when the pre and post permutation matrices are different.

Roger Stafford

Yes, all of the matrices are meant to be symetric, as they're meant to be the representation of an undirected graph. Basically, the permutation is just meant to be changing the order of solving a graph, such as using a natural ordering or using the ordering of the largest incidence degree first, so the rows and the columns do need to be permuted, as you gathered.

Also, the pre and post multiplication will use the same permutation matrix, as you gathered as well. Thanks for your help with this.

John Montgomery

John Montgomery <experimentmonty@gmail.com> wrote in message <25017450.1231910094719.JavaMail.jakarta@nitrogen.mathforum.org>...
> Yes, all of the matrices are meant to be symetric, as they're meant to be the representation of an undirected graph. Basically, the permutation is just meant to be changing the order of solving a graph, such as using a natural ordering or using the ordering of the largest incidence degree first, so the rows and the columns do need to be permuted, as you gathered.
>
> Also, the pre and post multiplication will use the same permutation matrix, as you gathered as well. Thanks for your help with this.
>
> John Montgomery

  As you may have gathered by now, John, given your description of how the post (on the right) multiplication matrix is defined, it results in the given permutation being performed on the matrix A columns, which accounts for the A(:,p) on the right side of the assignment. Multiplication by the same pre multiplication matrix (on the left) will result in the inverse of this same permutation applied to the rows of A, which is the reason for the A(p,:) on the left side of the assignment.

  Are you certain this is the kind of permutation you are seeking - as contrasted with, say, the same permutation being performed on both the columns and the rows?

Roger Stafford

John Montgomery <experimentmonty@gmail.com> wrote in message <19825854.1231902490721.JavaMail.jakarta@nitrogen.mathforum.org>...

>
> Is there any faster way to change the given matrix in this way that wouldn't require such huge multiplications? The matrices that I'm using have tens of thousands of rows and columns. Thanks for the help in advance.
>

Is it huge? The permutation can be create as sparse and it is still small in RAM for thousands rows and columns. Multiplication such sparse matrix is fast.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gkjv4q$gk2$1@fred.mathworks.com>...
> Is it huge? The permutation can be create as sparse and it is still small in RAM for thousands rows and columns. Multiplication such sparse matrix is fast.
>
> Bruno

  The assignment

 A(p,:) = A(:,p)

with permutation vector p will leave a sparse matrix A still sparse even if p is not. Which is faster, multiplication on both sides of A by a sparse permutation matrix P or the above assignment with the corresponding vector p?

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gkk26a$9rc$1@fred.mathworks.com>...
Which is faster, multiplication on both sides of A by a sparse permutation matrix P or the above assignment with the corresponding vector p?
>

n=10000; % matrix dimension
k=ceil((n^2-1)*rand(1,4*n)); % (4*n) non-zero elements
[i j]=ind2sub([n n],k);
A=sparse(i,j,rand(size(k)),n,n);

p=randperm(n);

tic
B=A(:,p);
toc % 0.001503 seconds.

P=sparse(p,1:n,ones(1,n));
tic
B=A*P;
toc % 0.002144 second

% Bruno

John Montgomery <experimentmonty@gmail.com> wrote in message <25017450.1231910094719.JavaMail.jakarta@nitrogen.mathforum.org>...
> Yes, all of the matrices are meant to be symetric, as they're meant to be the representation of an undirected graph. Basically, the permutation is just meant to be changing the order of solving a graph, such as using a natural ordering or using the ordering of the largest incidence degree first, so the rows and the columns do need to be permuted, as you gathered.
>
> Also, the pre and post multiplication will use the same permutation matrix, as you gathered as well. Thanks for your help with this.
>
> John Montgomery

 John, at one point you stated, "all of the matrices are meant to be symetric." I should point out that with the multiplication P*A*P where P is a permutation matrix of the kind you described, the resulting matrix product does not necessarily remain symmetric. It retains its symmetry only if the original permutation p is of a special kind that is a self-inverse (involution) permutation - that is, if p(p) gives the identity permutation.

  I say this because I would think you would want the product P.'*A*P where the left matrix is the transpose of the right one. This would permute the columns of A with the same permutation as with its rows and therefore give a symmetric result. This could also be accomplished by the operation

 A = A(p,p);

that I gave earlier.

Roger Stafford

Thanks for the stats Bruno, and yes Roger, what you mentioned with the transposed matrix is right, I have that on my notes paper, but I didn't really transfer that to my message, that's my fault. Thanks for looking out for me though.

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gkk6ub$o5k$1@fred.mathworks.com>...
> John Montgomery <experimentmonty@gmail.com> wrote in message <25017450.1231910094719.JavaMail.jakarta@nitrogen.mathforum.org>...
> > Yes, all of the matrices are meant to be symetric, as they're meant to be the representation of an undirected graph. Basically, the permutation is just meant to be changing the order of solving a graph, such as using a natural ordering or using the ordering of the largest incidence degree first, so the rows and the columns do need to be permuted, as you gathered.
> >
> > Also, the pre and post multiplication will use the same permutation matrix, as you gathered as well. Thanks for your help with this.
> >
> > John Montgomery
>
> John, at one point you stated, "all of the matrices are meant to be symetric." I should point out that with the multiplication P*A*P where P is a permutation matrix of the kind you described, the resulting matrix product does not necessarily remain symmetric. It retains its symmetry only if the original permutation p is of a special kind that is a self-inverse (involution) permutation - that is, if p(p) gives the identity permutation.
>
> I say this because I would think you would want the product P.'*A*P where the left matrix is the transpose of the right one. This would permute the columns of A with the same permutation as with its rows and therefore give a symmetric result. This could also be accomplished by the operation
>
> A = A(p,p);
>
> that I gave earlier.
>
> Roger Stafford


A=A(p,p) is also probably a lot faster than A(p,:)=A(:,p), anyway. sub matrix assignment (A(i,j) = ...) is in general a lot slower than submatrix reference (= A(i,j)) for sparse A.