Re: Terminology for static pivoting

To: csc-lVPF2Jp+hdv2fBVCVOL8/[email protected]
Subject: Re: [Csc] Terminology for static pivoting
In-reply-to: 
OF9FCA7F3C.FD54205D-ON852571E6.0072278F-852571E6.00731A2F-C8De+VPAFf1Coc0SRxUEnA@public.gmane.org
Date: Mon, 11 Sep 2006 15:08:45 -0700
Message-ID: <14727.1158012525-JbyIws30zmSdki8Cey591z//[email protected]>
From: Jason Riedy <ejr-JbyIws30zmSdki8Cey591z//[email protected]>

And Alex Pothen forwards from Iain Duff:
- My question to the group is what term should we use to describe this 
kind
- of strategy.  We [1] have used the term "static pivoting" and believe 
that
- this was first used in [2].

There are three aspects involved here:
1) When do you chose a pivot order?
2) How do you chose a pivot order?
3) How do you cope with small pivots?

To me, "static pivoting" implies an answer to the first
question and limits answers to the others.  It's a fair
description of the class of methods that chooses pivots
early and refuses to change them.  Any individual method's
description also must address the latter two questions.

- Normally if it is necessary to use a pivot that does not satisfy the
- numerical criterion it is replaced by some suitable value 
(conventionally
- ||A||*sqrt(epsilon)) and the factorization proceeds.  This will of 
course

BTW, that threshold is very sensitive to A's scaling.  A
better perturbation heuristic I've found is to save the
initial diagonal and perturb a pivot only when it's small
relative to the initial diagonal entry.  This doesn't seem
quite as dependent on the scaling and matching heuristics.

I know the idea of perturbing the pivots to avoid dynamic
changes is described in:
G. W. Stewart, "Modifying Pivot Elements in Gaussian Elimination",
Mathematics of Computation, v28, n126, 1974
http://links.jstor.org/sici?sici=0025-5718%28197404%2928%3A126%3C537%3AMPEIGE%3E2.0.CO%3B2-J 
(Anyone know if JSTOR does DOIs?)

which in turn cites an article I haven't read:
E. Hellerman and D. Rarick, "The Partitioned Preassigned Pivot
Procedure (P^4)", Sparse Matrices and Their Applications, Plenum
Press, New York, 1972.

There's another from 1971 with the same authors in Mathematical
Programming, and a 1985 article in SIAM Numerical Analysis by
Erisman, Grimes, Lewis, and Poole on a modification of P^4
(the precautionary partitioned preassigned pivot procedure,
which would be made simpler by working directly with the
strongly connected components).  Another fun reference in
this chain is the MCSPARSE system (1991), which combines a
form of bottleneck matching, a bordered block triangular form,
and limited pivoting for parallel factorization.

So it appears the phrase "preassigned pivot procedure" is
the, um, preassigned phrase for selecting the pivots early.
I'm not sure if all uses of that phrase refuse to change
the pivot order during factorization.  "Static pivoting"
seems a better choice for naming schemes that do refuse
to change the pivot sequence.

Plus, preassigned pivoting has the same initials as partial
pivoting, so it's not as useful for LAPACK-style naming. ;)

As far as "static pivoting" is concerned, I don't think
Olschowka and Neumaier ever use that phrase, so Li and
Demmel likely is the first use.

Jason

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