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:
Permutation of sparse matrices

Subject: Permutation of sparse matrices

From: John Montgomery

Date: 14 Jan, 2009 03:07:40

Message: 1 of 11

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

Subject: Permutation of sparse matrices

From: Roger Stafford

Date: 14 Jan, 2009 03:41:02

Message: 2 of 11

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

Subject: Permutation of sparse matrices

From: Roger Stafford

Date: 14 Jan, 2009 04:45:04

Message: 3 of 11

"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

Subject: Permutation of sparse matrices

From: John Montgomery

Date: 14 Jan, 2009 05:14:24

Message: 4 of 11

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

Subject: Permutation of sparse matrices

From: Roger Stafford

Date: 14 Jan, 2009 05:47:02

Message: 5 of 11

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

Subject: Permutation of sparse matrices

From: Bruno Luong

Date: 14 Jan, 2009 06:02:02

Message: 6 of 11

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

Subject: Permutation of sparse matrices

From: Roger Stafford

Date: 14 Jan, 2009 06:54:02

Message: 7 of 11

"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

Subject: Permutation of sparse matrices

From: Bruno Luong

Date: 14 Jan, 2009 07:09:07

Message: 8 of 11

"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

Subject: Permutation of sparse matrices

From: Roger Stafford

Date: 14 Jan, 2009 08:15:07

Message: 9 of 11

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

Subject: Permutation of sparse matrices

From: John Montgomery

Date: 14 Jan, 2009 20:27:07

Message: 10 of 11

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.

Subject: Permutation of sparse matrices

From: Tim Davis

Date: 15 Jan, 2009 01:12:02

Message: 11 of 11

"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.

Tags for this Thread

No tags are associated with 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