Solving a large sparse system with a single dense row/column?
goodchil...@gmail.com
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
Anony
<goodchil...@gmail.com> wrote in message
news:d551fb33-0a82-44a2...@l17g2000pri.googlegroups.com...
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.
Alois Steindl
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
Carl Barron
<d551fb33-0a82-44a2...@l17g2000pri.googlegroups.com>,
<goodchil...@gmail.com> wrote:
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
Anony
"Alois Steindl" <Alois....@tuwien.ac.at> wrote in message
news:m363tp8...@mch2pc28.mechanik.tuwien.ac.at...
> 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)
Alois Steindl
> 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
Anony
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.
Alois Steindl
>
> 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
goodchil...@gmail.com
> 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
Anony
<goodchil...@gmail.com> wrote in message
news:d7dbcccb-8ce8-49e5...@c19g2000prf.googlegroups.com...
> 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.
Alois Steindl
>
> 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
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