Path: news.mathworks.com!not-for-mail
From: "Tim Davis" <davis@cise.ufl.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Permutation of sparse matrices
Date: Thu, 15 Jan 2009 01:12:02 +0000 (UTC)
Organization: University of Florida
Lines: 21
Message-ID: <gkm2h2$1ga$1@fred.mathworks.com>
References: <gkjqkg$1u$1@fred.mathworks.com> <25017450.1231910094719.JavaMail.jakarta@nitrogen.mathforum.org> <gkk6ub$o5k$1@fred.mathworks.com>
Reply-To: "Tim Davis" <davis@cise.ufl.edu>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1231981922 1546 172.30.248.38 (15 Jan 2009 01:12:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 15 Jan 2009 01:12:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 45902
Xref: news.mathworks.com comp.soft-sys.matlab:511666

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