Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: FEM substructuring  (static condensation) -> out ot memory; ANSYS can do it
Date: Wed, 4 Jun 2008 10:44:02 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 79
Message-ID: <g25rli$8e8$1@fred.mathworks.com>
References: <g1rovt$8ep$1@fred.mathworks.com> <g1se12$sc2$1@fred.mathworks.com> <g1u2da$can$1@fred.mathworks.com> <g1utuj$bje$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1212576242 8648 172.30.248.35 (4 Jun 2008 10:44:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 4 Jun 2008 10:44:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1337510
Xref: news.mathworks.com comp.soft-sys.matlab:472129



> Thanks - glad the book helped, even if just a bit.  Yes,
> it's got a lot of combinatorial stuff in it - more of 
that
> than linear algebra.  That's the nature of sparse matrix
> computations.  They're not so much linear algebra as 
graph
> theoretic algorithms with reals that go along for the 
ride.
> 
> I'm not sure off-hand how you'd deal with the Schur
> complement implicitly.  The Sherman-Morrison update 
might be
> used - I'm not sure.
> 
> How bad is it to let backslash handle the whole K?  The
> "static condensation" is exploited internally, in either 
a
> multifrontal (LU) or supernodal (chol) way.
> 
> Consider this graph game.  Take a symmetric matrix.  Let
> there be one node per row/col, and let there be an edge
> (i,j) if A(i,j) is nonzero.
> 
> Now, pick a node, any node.  Add edges between all of its
> neighbors (they now form a clique), then eliminate the 
node
> you picked (and its incident edges).  Continue until the
> graph is gone.
> 
> Every edge that ever appeared ... gives you the nonzero
> pattern of L for the Cholesky factorization of 
L*L'=P*A*P'.
>  The P gives you the order in which you eliminated the 
nodes.
> 
> Now, for a FEM matrix, your graph starts out as a 
collection
> of cliques.  Static condensation consists of eliminating
> nodes whose neighbors already form a clique, so no new 
edges
> are added.
> 
> Those cliques give LU, or Chol, a way of exploiting dense
> matrix kernels (LU and CHOL both use the level-3 BLAS).  
If
> you pre-eliminate via static condensation, your cliques 
are
> smaller ... but there's less chance for using the BLAS.
> 
> So LU and CHOL naturally do "static condensation", if 
given
> the right ordering.
> 
> See what happens if you do a CHOL with the nodes to
> statically condense ordered first.  You can do this with
> AMD, or if you download CAMD from the File Exchange (in
> SuiteSparse), you can do it more easily with that (give 
CAMD
> a set of constraints to tell it how to order the nodes, 
with
> the statically condensed nodes ordered first, and the 
rest
> 2nd, so that you have 2 constraint sets).
> 
> Then try CHOL with the resulting permutation as the
> fill-reducing ordering.
> 
> The lower right corner of L will be the factor of your
> statically-condensed matrix.
> 


Thanks Tim for your hints, I'll try the ordering of the 
nodes and then use CHOL.

Can you suggest any introductory book on graphs and/or the 
combinatorial stuff which would help me make your book 
more understandable? Maybe there is some book for the 
introduction to the analysis of sparse algorithms?