Re: strict static pivoting vs pliable static pivoting

[From Jason Reidy,  the csc list serve does not seem to receive his 
messages...]


And Cleve Ashcraft writes:
- Pivoting within a supernode could be called "restricted pivoting".

It could also be called "probably useless."  For a given
set of heuristics, static pivoting failure cases fall
into two classes: those that fail because element growth
annihilates crucial information, and those that fail
because any perturbation will induce failure (too ill-
conditioned).

For the former case, the destructive element growth
seems to occur after pivots in leaves of the elimination
tree.  The supernodes are small, and no other column in
the column supernode appears to be a better pivot (but
I'm not 100% sure of those results).  A restricted
pivoting scheme would help only if it prevents the
off-diagonals from becoming large, but they often come
from the original matrix.  A different matching simply
shuffles the problem to a different pivot.

Better equilibration and a different perturbation
heuristic seem to be more successful in solving problems
with element growth.

And the ill-conditioned cases are just ill-conditioned.
Take the lhr* matrices, for example.  Full partial
pivoting leads to small backward errors, which is all
that matter in the original application.  But it seems
that any threshold pivoting or perturbation method fails.
A better equilibration; in particular, using the strongly
connected components to determine equilibration factors;
may be more successful, but I haven't completed those
tests yet.

Of course, these observations are general.  Any specific
application may find restricted pivoting useful.  But
reducing the ill-conditioning is far more important.
The main tool a black-box solver has for ameliorating
ill-conditioning is equilibration, which also helps in
controlling element growth.

And finding good equilibration factors for sparse
matrices leads back to the same interesting question of
how the matrix values are related to the sparsity
structure...  At first blush, simple schemes coupled
with combinatorial information like the strongly
connected components seem more successful than
complicated equlibration schemes.  But the complicated
schemes are much easier to implement in parallel. blah.

Jason

_______________________________________________
Csc mailing list
Csc-lVPF2Jp+hdv2fBVCVOL8/[email protected]
http://list.odu.edu/listinfo/csc