Localized Estimation of Condition Numbers for MILU Preconditioners on a Graph

Abstract

This paper proposes a theoretical framework for analyzing modified incomplete LU (MILU) preconditioners for coefficient matrices that are symmetric positive definite M-matrices. Considering a generalized MILU preconditioner on a weighted undirected graph with self-loops, we extend its applicability beyond matrices derived from Poisson equation solvers on uniform grids with compact stencils. A major contribution is a novel measure, the localized estimator of condition number (LECN), which quantifies the condition number locally at each vertex of the graph. We prove that the maximum value of the LECN provides an upper bound for the condition number of the MILU-preconditioned system, offering an estimation of the condition number using only local measurements. This localized approach significantly simplifies the condition number estimation and provides a powerful tool for analyzing the MILU preconditioner applied to previously unexplored matrix structures. To demonstrate the usability of LECN analysis, we present three cases: (1) a revisit of existing results of MILU preconditioners on uniform grids, (2) analysis of high-order implicit finite difference schemes on wide stencils, and (3) analysis of variable coefficient Poisson equations on hierarchical adaptive grids such as quadtree and octree. For the third case, we also validate LECN analysis numerically on a quadtree.