"A Crout version of ILU"

Yousef Saad
Univ. of Minnesota.

Standard  ILU factorization  preconditioning often  utilize  a delayed
update Gaussian Elimination (GE) algorithm, sometimes known as the IKJ
variant of GE.   This leads to severe inefficiencies  when the fill-in
allowed  becomes   substantial.  The  main  problem   comes  from  the
requirement to process rows in a certain order in the main elimination
step,  leading to  expensive  searches.  Another  variant of  Gaussian
elimination  which  was  advocated  for  symmetric  positive  definite
matrices [Jones-Plassman, TOMS, 1995],  is shown to be quite effective
when  extended to the  nonsymmetric case.   An important  advantage of
this  algorithm is  that it  is  easily amenable  to the  use of  more
rigourous dropping strategies such  as those developed in [Bollhoefer,
2001].  We will describe the algorithm and some of its variations, and
report  on  some  experiments.   The  tests confirm  that  the  method
computes  better  preconditioners and  uses  less  storage than  other
implementations such as ILUT.

=======================================================================