Analysis of Block Jacobi/Gauss-Seidel and additive/multiplicative Schwarz preconditioning through the theory of GLT sequences, with applications to domain decomposition discretizations
It is proved that, if the BJ, BGS, and MS preconditioners are GLT sequences with symbol $\kappa$, then the sequences of the BJ, BGS, and MS preconditioners are GLT sequences with symbol $\kappa$.
Abstract
When a linear differential problem is discretized by a linear numerical method characterized by a mesh fineness parameter $n$, the computation of the numerical solution reduces to solving a linear discrete problem identified by a matrix $A_n$ whose size grows with $n$. The sequence of discretization matrices $\{A_n\}_n$ often falls within the class of generalized locally Toeplitz (GLT) sequences, even when the numerical method belongs to the family of domain decomposition methods (DDMs), as illustrated herein through examples. Four widely used preconditioners for DDM discretization matrices are the block Jacobi (BJ), block Gauss--Seidel (BGS), additive Schwarz (AS), and multiplicative Schwarz (MS) preconditioners. In this paper, we provide formal definitions of the BJ/BGS/AS/MS preconditioners for arbitrary multilevel block matrices. These definitions and the associated notations are inspired by the theory of GLT sequences and are proposed as alternatives to those commonly used by the DDM community. We analyze the structure of the BJ/BGS/AS/MS preconditioners when applied to multilevel block matrices $A_n$ belonging to a GLT sequence $\{A_n\}_n$. Every GLT sequence $\{A_n\}_n$ is uniquely associated with a special function $\kappa$ called symbol. We prove that, if $\{A_n\}_n$ is a GLT sequence with symbol $\kappa$, then the sequences of the BJ, BGS, and MS preconditioners are GLT sequences with symbol $\kappa$. For the AS preconditioner, we prove that $\{P_n^{AS}(A_n)\}_n$ is a GLT sequence with symbol $\kappa^{AS}\approx\kappa$, and $\kappa^{AS}=\kappa$ whenever the overlaps in the subdomains used for the construction of $P_n^{AS}(A_n)$ vanish as $n\to\infty$. A numerical validation of these results in the context of isogeometric DDMs is presented.
We study a class of nonlocal evolutionary partial differential equations with weakly singular temporal kernel and spatially variable diffusion coefficient. The model is posed on $\Omega \subset \mathbb{R}$, and involves a left-sided Riemann--Liouville fractional derivative in space multiplied by a variable coefficient $a(x)$. The temporal derivative is approximated by an $L1$ type scheme, while the spatial operator is discretized by finite difference techniques, resulting in large scale all at once linear systems with a twolevel Toeplitz like structure. We develop and analyze a block lower triangular strategy that mimics the structure of the coefficient matrix while simplifying its components for computational efficiency. The analysis is carried out at the level of matrix sequences by means of generalized locally Toeplitz (GLT) theory. Within this framework, we characterize the asymptotic spectral distribution of the discretized operators and use the associated GLT symbol to guide the construction of the structured approximation. Numerical experiments using the GMRES solver demonstrate that the proposed preconditioning strategy significantly improves convergence rates, robustness, and scalability for large-scale problems. Open problems and possible extensions are briefly discussed at the end of the present work.
Muhammad Faisal Khan, Stefano Serra-Capizzano· 0 citations
The resulting V-cycle, used as a conjugate-gradient preconditioner for continuous lagrangian finite element discretizations, maintains stable iteration counts and remains effective in regimes where standard AMG deteriorates.
Davide Polverino, Marco Feder, Luca Heltai· arXiv.org· 0 citations
Finite-element mass matrix solves and approximate inverses arise often in explicit time integration as well as Schur-complement-based block preconditioning. A diagonal approximation of the mass matrix is cheap and widely used, but can be a poor approximation, particularly for high-order elements. This paper introduces a broken-space additive Schwarz (BRAS) mass inverse approximation, formed by applying exact element-local inverse mass matrices on the broken finite-element space and averaging the result back to the conforming space. The construction uses the same element matrices and local-to-global maps as standard mass assembly, has the same element-adjacency sparsity graph as the conforming mass matrix, and is symmetric positive definite for any conforming space, mesh geometry, and polynomial basis. We prove spectral bounds for the preconditioned mass matrix, and wide-ranging numerical experiments for \(H^1\), \(H(\operatorname{curl})\), and \(H(\operatorname{div})\) finite elements on two- and three-dimensional simplicial meshes show that BRAS reduces spectral condition numbers, Krylov iterations, and solve times relative to diagonal preconditioning. For preconditioned conjugate gradient (CG), BRAS yields a 1.1--4.7$\times$ speedup over diagonal/Jacobi preconditioning across all cases tested over finite-element orders $p\in[1,4]$. Further, theory and numerical experiments show that in the block-preconditioning case, BRAS can improve Schur-complement approximations and reduce outer solve times. On mixed Poisson and biharmonic systems, BRAS yields a 1.5--3$\times$ speedup in time-to-solution over a standard diagonal-based preconditioning approach.
O. Krzysik, B. Southworth, G. Wimmer· arXiv.org· 1 citation
The computation of the action of a matrix function on a vector, $f(A)b$, is a major computational bottleneck for large, sparse matrices, particularly when unfavorable spectral distributions cause standard Krylov subspace methods to stagnate. In this work, we propose a unified framework for preconditioning $f(A)b$ based on the Cauchy integral representation of the matrix function. By exploiting shift-invariance properties, we decouple the preconditioner evaluation from the Krylov subspace generation. We develop this framework in two distinct directions. First, for rational shift-and-invert preconditioning, we resolve a fundamental trade-off between optimal spectral compression and finite-precision instability. We achieve this by formulating a closed-form extraction stabilized via Double Modified Gram-Schmidt reorthogonalization, which eliminates the formation of spurious phantom poles. Second, we present a matrix-free polynomial approach. To ensure numerical stability, we isolate the continuous numerical quadrature step using a Schur decomposition of the projected Hessenberg matrix. To further stabilize the integration near contour singularities and accelerate overall convergence, we incorporate an exact LR-deflation scheme targeting the critical low modes of the preconditioned operator. We analyze the asymptotic stability and proximity to singularity of these methods, and present numerical experiments demonstrating their efficiency on the 2D Laplacian with $f=\textrm{exp}$, and a highly ill-conditioned Wilson-Dirac operator from lattice quantum chromodynamics with $f=\textrm{sign}$, although the framework can be in principle used with any $f$ and it is particularly beneficial when applying $f(A)b_{i}$ with many different vectors $b_{i}$.
This paper develops a matrix‐collocation method based on the Frobenius–Euler polynomial family Hn(λ;x)${{H}_n}( {\lambda ;x} )$ for nonlinear Duffing‐type oscillators. The Appell structure of the Frobenius–Euler basis yields a parameter‐independent subdiagonal operational derivative matrix, while the parameter λ$\lambda $ controls the conditioning of the resulting linear system through the basis evaluation. The method uses Chebyshev–Gauss–Lobatto collocation nodes on the unit interval, a Newton–Raphson scheme with analytical Jacobian and homotopy continuation in the cubic coefficient, and a piecewise extension for long‐time integration over multiple oscillation periods. A structural conditioning analysis identifies a stable parameter regime λ∈[−2,−0.5]$\lambda \in [ { - 2, - 0.5} ]$ in which the condition number of the collocation system is smaller than that of the Bernoulli operational matrix scheme by a factor of 30$\hskip.001pt 30$ – 150$\hskip.001pt 150$ at truncation orders N∈[6,14]$N\in [ {6,14} ]$ , while the achievable accuracy matches that of the Bernoulli basis to floating‐point precision in the benchmark problems considered. The mechanism behind the conditioning advantage is explained through the proximity of a removable but numerically dangerous singularity in the Frobenius–Euler generating function at λ=1$\lambda = 1$ . Numerical experiments on three standard Duffing benchmark problems establish accuracy comparable to that of the improved Taylor matrix method (ITMM), the Laplace decomposition algorithm, the quasilinearized Bessel polynomial collocation method (QBPCM), and the modified variational iteration method; the piecewise scheme with K=8$K = 8$ segments of degree N=8$N = 8$ achieves final‐time errors below 5×10−8$5 \times {{10}^{ - 8}}$ over four oscillation periods of the unforced cubic Duffing oscillator.
N. B. Savaşaneril· ZAMM - Journal of Applied Ma...· 0 citations
Three-dimensional time-harmonic Maxwell simulations generate massive complex indefinite systems whose mesh coarsening is strictly limited by phase accuracy. Although matrix-free finite element kernels utilize GPU throughput efficiently, standard multilevel solvers are ultimately bottlenecked by the memory and communication costs of exact coarse-grid factorizations. We present a fully matrix-free, factorization-free three-grid preconditioner for curl-conforming N{\'e}delec discretizations with perfectly matched layers (PML) and optimally blended quadrature. The method employs an outer FGMRES to solve the unshifted fine-grid equation, while an intermediate-grid correction is computed by a fixed-work FGMRES preconditioned with a complex-shifted $2h$--$4h$ cycle. This strategically confines the complex shift to an auxiliary preconditioner, preserving the physical Maxwell operator. A local Fourier analysis derives the blended Maxwell branches and compatible edge transfers, identifying robust shift and Jacobi damping parameters. Validated against the analytical Maxwell Green tensor, our approach demonstrates extreme scalability: using a single solver configuration, both homogeneous and highly heterogeneous systems with approximately 10.89 billion complex edge unknowns are solved in 42.0--72.0 seconds on just 64 NVIDIA A100 GPUs.
Shubin Fu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
