  Incomplete factorization is a powerful preconditioner for Krylov subspace
methods for solving large-scale sparse linear systems. Existing incomplete
factorization techniques, including incomplete Cholesky and incomplete LU
factorizations, are typically designed for symmetric or nonsymmetric matrices.
For some numerical discretizations of partial differential equations, the
linear systems are often nonsymmetric but predominantly symmetric, in that they
have a large symmetric block. In this work, we propose a multilevel incomplete
LU factorization technique, called PS-MILU, which can take advantage of
predominant symmetry to reduce the factorization time by up to half. PS-MILU
delivers robustness for ill-conditioned linear systems by utilizing diagonal
pivoting and deferred factorization. We take special care in its data
structures and its updating and pivoting steps to ensure optimal time
complexity in input size under some reasonable assumptions. We present
numerical results with PS-MILU as a preconditioner for GMRES for a collection
of predominantly symmetric linear systems from numerical PDEs with unstructured
and structured meshes in 2D and 3D, and show that PS-MILU can speed up
factorization by about a factor of 1.6 for most systems. In addition, we
compare PS-MILU against the multilevel ILU in ILUPACK and the supernodal ILU in
SuperLU to demonstrate its robustness and lower time complexity.
