Localized Estimation of Condition Numbers for MILU Preconditioners on a Graph

Geonho Hwang, Yesom Park, Yueun Lee, Jooyoung Hahn, Myungjoo Kang

Abstract

This paper proposes a theoretical framework for analyzing Modified Incomplete LU (MILU) preconditioners. Considering a generalized MILU preconditioner on a weighted undirected graph with self-loops, we extend its applicability beyond matrices derived by 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 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 to 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.

Introduction

In large-scale physics simulations—ranging from fluid dynamics to electromagnetics—the computational bottleneck often lies in solving massive, sparse linear systems of the form $Ax = b$. While iterative solvers like the Conjugate Gradient (CG) method are standard, their efficiency is dictated by the condition number of the matrix $A$. A high condition number leads to slow convergence and prohibitive computational costs.

Preconditioning is the primary strategy used to address this, transforming the system into $M^{-1}Ax = M^{-1}b$ to improve the condition number. Among these, the Modified Incomplete LU (MILU) factorization is favored for its memory efficiency and performance. However, theoretical guarantees for MILU have historically been limited to simple, uniform grids. This research introduces a new framework to analyze MILU performance in complex, real-world scenarios, such as adaptive grids and high-order schemes, using a graph-theoretical approach.

The Localized Estimator of Condition Number (LECN)

The core innovation of this work is the Localized Estimator of Condition Number (LECN), denoted as $\tau_K$. Rather than attempting to analyze the global properties of the preconditioned matrix directly—a task that becomes mathematically intractable for irregular grids—the authors re-imagine the matrix $A$ as a weighted undirected graph. In this representation, each row and column corresponds to a vertex, and non-zero entries represent edges.

Local Measurement and Global Bounds

The LECN framework operates on two levels:

  1. Local Measurement: At each individual vertex, $\tau_K$ calculates a ratio based on the MILU factorization and the specific ordering of the nodes (the sequence in which they are processed). This ratio essentially measures the local stability of the preconditioner.
  2. The Upper Bound: The authors mathematically prove that the maximum value of $\tau_K$ across the entire graph serves as a rigorous upper bound for the condition number of the preconditioned system.

This "local-to-global" bridge allows researchers to guarantee the stability and efficiency of a global solver simply by controlling local graph properties, such as the ratio of "precursors" (processed neighbors) to "successors" (unprocessed neighbors) in the node ordering.

Applications in Complex Numerical Schemes

The utility of the LECN framework is demonstrated through three challenging cases that were previously difficult to analyze:

1. Uniform Grids and Node Ordering

The framework provides a theoretical explanation for why certain node orderings, such as "Sectored-MILU," outperform standard lexicographical orderings. By maintaining a favorable ratio of precursors at each node, these orderings minimize the local $\tau_K$ values, leading to a lower global condition number.

2. High-Order Implicit Finite Difference (HIFD)

High-order schemes utilize "wide stencils" that connect a node to many distant neighbors. While these schemes offer higher accuracy, their complexity usually breaks standard MILU proofs. The LECN framework handles these wide stencils naturally by treating the additional connections as weighted edges in the graph.

3. Hierarchical Adaptive Grids (Quadtrees and Octrees)

Adaptive grids vary resolution locally to focus computational power on areas of interest (e.g., near a wing surface in an airflow simulation). This creates "T-junctions" where cells of different sizes meet, introducing irregularities that typically complicate numerical analysis. The LECN framework proves that MILU still achieves an optimal $O(h^{-1})$ condition number scaling on these grids, even with variable coefficients.

Numerical Validation and Results

The theoretical findings were validated using synthetic Poisson problems with both oscillatory and steep variable coefficients on randomly generated quadtrees.

Key findings include: * Condition Number Reduction: The analysis confirmed that MILU reduces the condition number growth from $O(h^{-2})$ to $O(h^{-1})$, where $h$ is the grid spacing. This represents a significant improvement in scaling as the simulation resolution increases. * Iteration Efficiency: In numerical tests on a quadtree with approximately 75,000 cells, the MILU-preconditioned solver reached target accuracy in only 8% of the iterations required by a Jacobi preconditioner and 26% of those required by a standard ILU preconditioner. * Predictive Power: Log-scale plots of the condition number versus grid refinement levels showed that the actual condition number grew linearly, precisely as predicted by the LECN upper bound.

Conclusion

The LECN framework represents a significant step forward in the theoretical understanding of MILU preconditioners. By shifting the focus to local graph measurements, it provides a versatile tool for analyzing and optimizing solvers on the complex, adaptive meshes required for modern engineering and physics simulations.

Future work remains to extend this theory beyond Symmetric Positive Definite (SPD) M-matrices to more general matrix structures and to explore its application to Neumann boundary conditions and more complex polyhedral meshes.

Summary updated

Abstract

This paper proposes a theoretical framework for analyzing Modified Incomplete LU (MILU) preconditioners. Considering a generalized MILU preconditioner on a weighted undirected graph with self-loops, we extend its applicability beyond matrices derived by Poisson equation solvers on uniform grids with compact stencils. A major contribution is, a novel measure, the \textit{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 estimation of the condition number using only local measurements. This localized approach significantly simplifies the condition number estimation and provides a powerful tool or analyzing the MILU preconditioner applied to previously unexplored matrix structures. To demonstrate the usability of LECN analysis, we present three cases: (1) revisit to 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.
BibTeX
@article{hwang2026localized,
  author = {Geonho Hwang and Yesom Park and Yueun Lee and Jooyoung Hahn and Myungjoo Kang},
  title = {{Localized Estimation of Condition Numbers for MILU Preconditioners on a Graph}},
  journal = {SIAM J. Numer. Anal.},
  year = {2026},
  doi = {10.1137/24m1722134},
}
Figure