An efficient method for constructing an ILU preconditioner for solving large sparse nonsymmetric linear systems by the GMRES method (Q1827264)

An incomplete LU decompositions (ILU) of a sparse \(n \times n\) matrix \(A\) is an LU decomposition which neglects entries not contained in a set \(P \subset \{1, \dots, n\} \times \{1, \dots, n\}\) during the elimination process. This limits the fill-in in the triangular factors \(L\) and \(U\) and may drastically reduce the computational requirements compared to a complete LU decomposition. Although an ILU itself does not admit the accurate solution of a system of linear equations, it is often successfully used as a preconditioner in iterative methods, such as GMRES or BiCG. The authors consider sets \(P\) that are determined by the generic nonzero pattern of the matrix \(A+A^2+\cdots A^m\), giving rise to ILU(\(m\)). It is proposed to use the Floyd-Warshall algorithm for constructing \(P\). Some numerical experiments illustrate the preconditioning capabilities of ILU(\(m\)) in combination with GMRES. However, there are no numerical comparisons to other ILU preconditioners, such as the very similar ILU(\(p\)) described in \textit{Y. Saad}'s book [Iterative methods for sparse linear systems (2nd ed., SIAM, Philadelphia) (2003; Zbl 1031.65046)].