| |
 |
|
|
Science Forum Index » Math - Numerical Analysis Forum » Solving a large sparse system with a single dense...
Page 1 of 1
|
| Author |
Message |
| ... |
 Posted: Wed May 07, 2008 2:13 pm |
|
|
|
Guest
|
Are there any tricks for efficiently solving large systems of
equations which are very sparse except for a single dense row / dense
column? I'm interested in methods for both symmetric and non-
symmetric matrices.
Thanks,
Trevor |
|
|
| Back to top |
|
| Anony... |
| Posted: Wed May 07, 2008 7:53 pm |
|
|
|
Guest
|
<goodchild.trevor at (no spam) gmail.com> wrote in message
news:d551fb33-0a82-44a2-b9e4-729f84b64095 at (no spam) l17g2000pri.googlegroups.com...
Quote: Are there any tricks for efficiently solving large systems of
equations which are very sparse except for a single dense row / dense
column? I'm interested in methods for both symmetric and non-
symmetric matrices.
Thanks,
Trevor
Is the upper triangular part of your matrix as:
/ \
| x x |
| x x |
| x x |
| x x |
| x x |
| x x |
| x |
\ /
(or a dense row)? If so, you can solve it by sky-line solver. Or you can
renumber the sparse matrix to have a minimal bandwidth, and solve it by
constant band solver. |
|
|
| Back to top |
|
| Alois Steindl... |
| Posted: Thu May 08, 2008 2:13 am |
|
|
|
Guest
|
Hello,
the package BEMW by Willy Govaerts, to be found on NETLIB, would be a
good candidate.
Simply applying a bandwidth reduction by renumbering the variables
would save you only half the full bandwidth. But you could think of
reformulating your equations, if these derive from a differential
equation: For a single row, which corresponds to a integral, you could
introduce a differential equation I'=f_{n+1}(x), which only increases the
narrow band. Also a column, which corresponds to a parameter in the
system, could by replaced by a trivial DE: p'=0.
Good luck
Alois |
|
|
| Back to top |
|
| Carl Barron... |
| Posted: Thu May 08, 2008 4:19 am |
|
|
|
Guest
|
In article
<d551fb33-0a82-44a2-b9e4-729f84b64095 at (no spam) l17g2000pri.googlegroups.com>,
<goodchild.trevor at (no spam) gmail.com> wrote:
Quote: Are there any tricks for efficiently solving large systems of
equations which are very sparse except for a single dense row / dense
column? I'm interested in methods for both symmetric and non-
symmetric matrices.
Thanks,
Trevor
With no info about the sparse part there is:
A = S + uv^T
solve Sy = b and Sw = u
let k = v^Ty/(1+v^Tw)
then x = y - k w |
|
|
| Back to top |
|
| Anony... |
| Posted: Thu May 08, 2008 9:50 am |
|
|
|
Guest
|
"Alois Steindl" <Alois.Steindl at (no spam) tuwien.ac.at> wrote in message
news:m363tp8dzy.fsf at (no spam) mch2pc28.mechanik.tuwien.ac.at...
Quote: Hello,
the package BEMW by Willy Govaerts, to be found on NETLIB, would be a
good candidate.
Simply applying a bandwidth reduction by renumbering the variables
would save you only half the full bandwidth.
There is no way to agree with the opinion "renumbering .... save you only
half the full bandwidth".
Basically, you need a good renumbering scheme or tool. The following is a
link for renumbering
http://www.equation.com/servlet/equation.cmd?call=jcl
(or http://www.Equation.com) |
|
|
| Back to top |
|
| Alois Steindl... |
| Posted: Thu May 08, 2008 9:53 am |
|
|
|
Guest
|
"Anony" <no-email at (no spam) equation.com> writes:
assume an "arrow matrix" with fill in in the diagonal and the last row
and column.
What's the most efficient numbering?
What's the corresponding band width?
Alois |
|
|
| Back to top |
|
| Anony... |
| Posted: Thu May 08, 2008 5:11 pm |
|
|
|
Guest
|
"Alois Steindl" <Alois.Steindl at (no spam) tuwien.ac.at> wrote in message
news:m3tzh87sp8.fsf at (no spam) mch2pc28.mechanik.tuwien.ac.at...
Quote: "Anony" <no-email at (no spam) equation.com> writes:
There is no way to agree with the opinion "renumbering .... save you
only
half the full bandwidth".
Basically, you need a good renumbering scheme or tool. The following is
a
link for renumbering
http://www.equation.com/servlet/equation.cmd?call=jcl
(or http://www.Equation.com)
Hello,
assume an "arrow matrix" with fill in in the diagonal and the last row
and column.
What's the most efficient numbering?
What's the corresponding band width?
Alois
Hi, Alois,
Renumbering is not limited to produce constant bandwidth. As stated in my
origianl response, if the upper triangular part
is as:
/ \
| x x |
| x x |
| x x |
| x x |
| x x |
| x x |
| x |
\ /
variable bandwidth solver (i.e., skyline solver) is a choice. |
|
|
| Back to top |
|
| Alois Steindl... |
| Posted: Fri May 09, 2008 3:47 am |
|
|
|
Guest
|
"Anony" <no-email at (no spam) equation.com> writes:
Quote:
Hi, Alois,
Renumbering is not limited to produce constant bandwidth. As stated in my
origianl response, if the upper triangular part
is as:
/ \
| x x |
| x x |
| x x |
| x x |
| x x |
| x x |
| x |
\ /
variable bandwidth solver (i.e., skyline solver) is a choice.
Hello,
this case and the transposed one are quite trivial, but if there is a
full row and full column, then renumbering doesn't help much and you
need a different method.
Regards
Alois |
|
|
| Back to top |
|
| ... |
| Posted: Fri May 09, 2008 5:35 am |
|
|
|
Guest
|
On May 9, 1:47 am, Alois Steindl <Alois.Stei... at (no spam) tuwien.ac.at> wrote:
Quote: Hello,
this case and the transposed one are quite trivial, but if there is a
full row and full column, then renumbering doesn't help much and you
need a different method.
Regards
Alois
Yes, I should have been more specific: my system has a dense column
*and* a dense row. I.e., the matrix looks somewhat like this:
/ \
| x x |
| x x |
| x x |
| x x |
| x x |
| x x |
| x x x x x x x |
\ /
(though in reality there are more off-diagonal entries and the system
may have blocks that are not symmetric).
Sorry for the confusion,
Trevor |
|
|
| Back to top |
|
| Anony... |
| Posted: Fri May 09, 2008 12:23 pm |
|
|
|
Guest
|
<goodchild.trevor at (no spam) gmail.com> wrote in message
news:d7dbcccb-8ce8-49e5-a159-c4a7dec6357e at (no spam) c19g2000prf.googlegroups.com...
Quote: Yes, I should have been more specific: my system has a dense column
*and* a dense row. I.e., the matrix looks somewhat like this:
/ \
| x x |
| x x |
| x x |
| x x |
| x x |
| x x |
| x x x x x x x |
\ /
(though in reality there are more off-diagonal entries and the system
may have blocks that are not symmetric).
Sorry for the confusion,
Based on your description, it seems each X is a [X], a block (or a
submatrix) not a coefficient. If, so, that is not the one I responded
previously. If each entry in your system is a coefficient and your system is
symmetric, variable bandwidth solver can take advantage of the sparsity. If
each entry is a block, that would be a different story. Renumbering deals
with unknowns, not blocks.
Based on your description, it seems your system has a dense block column and
dense block row. Are those offdiaginal blocks dense? If they are sparse
blocks, you can renumber your system to take advantage of sparse solver. |
|
|
| Back to top |
|
| Alois Steindl... |
| Posted: Sat May 10, 2008 2:52 pm |
|
|
|
Guest
|
goodchild.trevor at (no spam) gmail.com schrieb:
Quote:
Yes, I should have been more specific: my system has a dense column
*and* a dense row. I.e., the matrix looks somewhat like this:
/ \
| x x |
| x x |
| x x |
| x x |
| x x |
| x x |
| x x x x x x x |
\ /
(though in reality there are more off-diagonal entries and the system
may have blocks that are not symmetric).
Sorry for the confusion,
Trevor
Hello,
Matrices with this structure are quite common in optimization problems
with integral constraints - in that case the matrices are usually
symmetric - and also in numerical treatment of bifurcation problems.
Could you tell us more about your application?
I guess, that Govaerts BEMW code is quite suitable for that type.
You could also try to resolve the problem yourself:
Let your equation be
A x + B y = b
C x + D y = c
where A is sparse, and B and D are your column and row matrices.
Then you could try to solve the first equation for x:
x = G y + H b
Inserting that into the second equation, you obtain a small system for
y. Of course the resulting system might be worse conditioned than the
original one.
Good luck
Alois |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Sun Jul 20, 2008 6:03 am
|
|
