Independent Columns: A New Parallel ILU Preconditioner for the PCG Method (1996)

Author(s): M. Pakzad, J.L. Lloyd and C. Phillips

Abstact: This paper considers the parallel solution of finite element equations using the preconditioned conjugate gradient method on shared memory multiprocessors. The preconditioner used is an incomplete LU factorization of the stiffness matrix. We have designed a new method for implementing parallel forward and backward substitutions which requires the L and U factors to have an independent columns structure which we refer to as I2LU. The algorithm has been implemented on an Encore Multimax and has produced parallel efficiencies up to 80 percent of the maximum possible theoretical value. These are comparable to the efficiencies of our implementation of a similar row-oriented approach, level scheduling, tested with the same problems.