Perturbed MILU conditioning for Neumann problems in two and three dimensions
Fix $d \in \{2, 3\}$ and a bounded connected smooth domain $\Omega \subset \mathbb{R}^d$. For $h > 0$, number the points $p \in h\mathbb{Z}^d$ whose cells $C_p = p + [-h/2, h/2]^d$ meet $\Omega$ as $1, \dots, N_h$, in lexicographic order. For two such points at distance $h$ let $$w_{pq} = \frac{\operatorname{vol}_{d-1}(C_p \cap C_q \cap \Omega)}{h^{d-1}},$$ and let $w_{pq} = 0$ for all other pairs. The Purvis–Burkhalter finite-volume discretisation of the Poisson equation with Neumann boundary conditions has the matrix $A$ with $A_{pq} = -w_{pq}$ for $p \ne q$ and $A_{pp} = a_p = \sum_q w_{pq}$; let $L$ be its strictly lower triangular part. For $\varepsilon > 0$ the perturbed MILU preconditioner is $M = (L + E)E^{-1}(E + L^{T})$, where $E = \operatorname{diag}(e_1, \dots, e_{N_h})$, $e_1 = a_1$ and $$e_p = (1 + \varepsilon)a_p - \sum_{q < p,\ w_{pq} > 0} \frac{w_{pq}}{e_q} \sum_{s > q} w_{qs} \qquad (p > 1).$$ This is the modified incomplete LU factorisation of $A + \varepsilon \operatorname{diag}(A)$, except that the first pivot is not perturbed, as in Lee and Min's definition. When every $e_p$ is positive, let $\kappa_+(M^{-1}A)$ be the ratio of the largest to the smallest positive eigenvalue of $M^{-1/2}AM^{-1/2}$; the zero eigenvalue, which comes from the constant vectors in the null space of $A$, is left out. Lee and Min posed the problem after numerical experiments in two and three dimensions, and proved the analogous bound $\kappa = O(h^{-1})$ for the relaxed incomplete LU preconditioner with mixing ratio $Ch^2$ on rectangles in two dimensions.
Problem. For every $d \in \{2, 3\}$ and every bounded connected smooth domain $\Omega \subset \mathbb{R}^d$, are there constants $c_\Omega, K_\Omega, h_\Omega > 0$ such that, for every $0 < h < h_\Omega$, the choice $\varepsilon = c_\Omega h^2$ makes every pivot $e_p$ positive and $$\kappa_+(M^{-1}A) \le K_\Omega h^{-1}?$$
Source: Lee and Min (2021), Section 4, the conjecture on perturbed MILU (PMILU); made precise by OpenProblemsInNLA (constants depending on Ω, positive pivots, face-area weights in three dimensions).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Keywords
- condition numbers, incomplete LU factorizations, OpenProblemsInNLA, preconditioners
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{lee2021,
author = {Lee, Byungjoon and Min, Chohong},
title = {Optimal preconditioners on solving the {P}oisson equation with {N}eumann boundary conditions},
journal = {J. Comput. Phys.},
volume = {433},
year = {2021},
pages = {110189},
doi = {10.1016/j.jcp.2021.110189},
}
@misc{openproblemsinnla-ie25,
author = {Townsend, Alex},
title = {{IE-25}: Perturbed MILU conditioning for Neumann problems in two and three dimensions},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-25/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00192, "Perturbed MILU conditioning for Neumann problems in two and three dimensions", clopen.solutions.