Re: Solving a large, sparse, nearly symmetric system
- From: Carl Barron <cbarron413@xxxxxxxxxxxx>
- Date: Mon, 26 May 2008 04:30:14 -0400
In article <g110ks$c1j$1@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>, Peter
Spellucci <spellucci@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
In article <200520082258269374%cbarron413@xxxxxxxxxxxx>,The op might be interested in this link as it seems very related to
Carl Barron <cbarron413@xxxxxxxxxxxx> writes:
In article
<416e63ba-a9a7-44e7-917c-5882e78c9827@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<goodchild.trevor@xxxxxxxxx> wrote:
On May 16, 9:17 pm, cbarr...@xxxxxxxxxxxxx (Carl Barron) wrote:
Assuming A is m x m and B is n x m m much biger than n. One can
solve two sets of n equations and n unknowns both with with the same
left hand size BB^T which is n x n and psd.
snip
The only thing I can come up with requres n+1 m dimensional band
solvers and one n x n dense system but does not take advantage of B
being fixed.
| I 0 | |A B^T | = |A B^T| CA = B
|-C I | |B 0 | | 0 D | D = -CB^T
|A B^T | |x1| = | b|
|0 D | |x2| | d - Cb|
x = |x1|
|x2|
but I really dont like it.
since you have no symmetry in A (but strict diagonal dominance if I remember
right, you even cannot apply the special software for KKT systems (there is
now a vast literature about this)) but you could do an ordinary sparse
LU decomposition (without pivoting first, evenyually after rescaling B ,
which is of no promlem in your case). then you could use this one as
preconditioner
for an iterative solver if A has changed (a little)
e.g. bicg-stab. the usual way to exploit the properties you mention would be:
use a sparse QR decomposition of B, transform the system using this
(this fixes x partly) and then to resolve "for the rest". For A you could
use a A= LU decomposition without pivoting. but then
it remains so to solve a subsystem of the form
[O,I_{m-n}]QLUQ'[O;I_{n-m}] tilde x_2 = tilde b_2
and although you could have Q represented in sparse Givens or Householder
factor and L and U banded and sparse the matrix on the left would usually
be dense. hence this approach would make sense only in an iterative solver
scheme but this will work only if the spectrum of A is well behaved and
which does not need to compute the matrix explicitly.
you have the relation
Q x = tilde x
and tilde x_2 are the last n-m components of it. maybe you can invent
a special iterative scheme for this ?
hth
peter
the problem:
www.precond07.enseeiht.fr/Talks/sameh/sameh.pdf
google sameh fluid dynamics will find it also.
.
- References:
- Solving a large, sparse, nearly symmetric system
- From: goodchild . trevor
- Re: Solving a large, sparse, nearly symmetric system
- From: goodchild . trevor
- Re: Solving a large, sparse, nearly symmetric system
- From: Carl Barron
- Re: Solving a large, sparse, nearly symmetric system
- From: goodchild . trevor
- Re: Solving a large, sparse, nearly symmetric system
- From: Carl Barron
- Re: Solving a large, sparse, nearly symmetric system
- From: Peter Spellucci
- Solving a large, sparse, nearly symmetric system
- Prev by Date: Re: Gauss Jordan elimination/Numerical Recipies in C
- Next by Date: eigenvalues in LDA
- Previous by thread: Re: Solving a large, sparse, nearly symmetric system
- Next by thread: Re: Solving a large, sparse, nearly symmetric system
- Index(es):
Relevant Pages
|
