Stability and Fast Algorithms of Incomplete LU Factorization with Zero‐Fill for Nine‐Diagonal Matrices
Zhenyue Zhang, Min Fang, Jing Wang · SIAM Journal on Matrix Analysis and Applications · 2007
Stability and fast algorithms of zero‐fill incomplete LU factorization for nonsymmetric nine‐diagonal matrices are considered. Based on a convergence analysis of the diagonal sequences in the LU factors of a monotone nine‐diagonal matrix, we give necessary and sufficient conditions for stably computing the ILU factorization in terms of an extreme solution to a system of nonlinear equations. Furthermore, the extreme solution is used to construct a fast ILU factorization with much less cost in flops and storage. Basically we use the standard ILU recursions up to a certain point and then replace the remaining terms of the recursive sequences by their limit values that can be determined by the extreme solution. Two strategies, preconditioning the nonlinear system to suit for Newton iterations and estimating the solution to get a good initial for the iterations, are discussed for computing the extreme solution efficiently. We also generalize the stability analysis and propose fast algorithms for nine‐diagonal matrices with periodically monotone diagonals or other nonconstant diagonals. Numerical examples show the efficiency of the proposed fast algorithms.