Since a number of colleagues have already weighed in on the
nomenclature aspect of "static pivoting," I am going to stir
up some controversy (and hopefully stimulate further discussion)
over another quote from Iain's original posting.
Iain writes about static pivoting, "This clearly has important
implications for limiting storage and for parallelism."
The statement would probably have been more accurate a few years
ago, but I believe that it does not really reflect the current
state of the art in direct solvers for general matrices.
Lets first closely examine if static pivoting really helps limit
storage. I think what helps limit the storage is the unsymmetric
permutation to maximize the magnitude of the product of the diagonals
and the corresponding scaling that precede static pivoting, not
static pivoting itself. There are numerous recent results in the
literature that show that dynamic pivoting requires a fairly small
threshold and very few swaps if preceded by the same preprocessing
steps for most matrices. This translates to very little extra
memory consumption due to pivoting. If a matrix is such that even
after this preprocessing, it requires a large number of swaps in
dynamic pivoting, then static pivoting is likely to fail on this
matrix anyway because of excessive perturbation and/or excessive
growth. So static pivoting typically works for only those coefficient
matrices for which dynamic pivoting does not result in significant
extra memory consumption, provided that the same preprocessing
is applied in both cases.
Now lets focus on parallelism. It appears quite intuitive that static
pivoting would parallelize and scale better than dynamic pivoting by
avoiding the communication overhead of the latter. However, this
holds only if we ignore the inevitable solve phase. The solve phase
is memory/communication bound and scales fairly poorly compared to
factorization in a parallel setting. As a result, whatever little
is gained in terms of communication by static pivoting during factorization
is lost during the additional steps of iterative refinement that are
usually required to recover the accuracy lost due to perturbation.
The real advantage of static pivoting, in my opinion, is that it
is easier to implement in parallel than dynamic pivoting. So for
the applications where it works, one can get away with a simpler solver.
-anshul
_______________________________________________
Csc mailing list
Csc@...
http://list.odu.edu/listinfo/csc
