Re: Static Pivoting

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