Sharpened CG Iteration Bound for High-contrast Heterogeneous Scalar Elliptic PDEs
Going Beyond Condition Number
P.M. Soliman (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Alexander Heinlein – Mentor (TU Delft - Numerical Analysis)
Henk M. Schuttelaars – Graduation committee member (TU Delft - Mathematical Physics)
F.A. Cumaru Silva Alves – Mentor (TU Delft - Numerical Analysis)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This thesis addresses the limitations of the classical condition number-based Conjugate Gradient (CG) iteration bound in solving high-contrast heterogeneous scalar elliptic problems, particularly when employing two-level Schwarz preconditioners. The classical bound, which relies solely on the condition number of the system matrix, fails to accurately predict the convergence behavior in scenarios where the eigenspectrum of the preconditioned system exhibits pronounced clustering and spectral gaps. Motivated by this observation, the thesis develops and analyzes sharpened CG iteration bounds that incorporate detailed spectral information, offering a more nuanced and descriptive understanding of convergence.
Building on foundational work in spectral analysis and iterative solvers, the thesis introduces novel multi-cluster and tail-cluster bounds for the CG method. These bounds are derived through a combination of theoretical analysis and practical algorithms for partitioning eigenspectra, and are validated both analytically and numerically. The new bounds utilize key spectral characteristics, such as cluster condition numbers and spectral width, to more accurately estimate the number of iterations required for convergence. Numerical experiments demonstrate that the sharpened bounds can be up to 1000 times tighter than the classical bound and are effective in distinguishing the robustness of different Schwarz preconditioners.
Despite their improved accuracy, the practical application of these bounds for a priori iteration estimation is challenged by the need for detailed spectral information, which is often unavailable in the early stages of iterative solvers. The thesis discusses heuristic approaches for leveraging partial spectral data and highlights the dependency of bound accuracy on the choice of coefficient functions and preconditioners.
In conclusion, the sharpened CG iteration bounds developed in this work provide a significant advancement in predictive performance analysis for high-contrast elliptic problems. Future research directions include refining cluster partitioning algorithms, improving a priori spectral estimation, and extending the applicability of these bounds to more complex problems and preconditioners.