PaperlayerView exact revision on arXiv

Source-linked AI summary

Block preconditioning for all-at-once variable-coefficient fractional evolution equations via the GLT analysis

Muhammad Faisal Khan, Stefano Serra-Capizzano

arXiv:2608.25796v1math.NA

TL;DR

The paper studies dense all-at-once systems from nonlocal evolutionary fractional equations with weakly singular temporal kernels and variable diffusion coefficients. It uses GLT analysis to construct a simplified block lower triangular preconditioner, whose effectiveness is supported by spectral clustering and GMRES experiments.

  • Problem

    Nonlocal fractional discretizations with variable diffusion produce dense large-scale all-at-once systems whose spectral structure must be characterized for effective preconditioning.

  • Method

    The paper uses GLT matrix-sequence analysis to design a block lower triangular preconditioner that mimics the coefficient matrix while simplifying its components.

  • Results

    The proposed preconditioners significantly reduced condition numbers, GMRES iterations, and computational cost, with observed spectral clustering consistent with the GLT analysis.

  • Takeaways & Limitations

    The strategy is effective for both constant and variable diffusion coefficients and improves convergence behavior in the tested cases.

  • Takeaways & Limitations

    A complete theoretical proof for the eigenvalue distribution of the variable-coefficient spatial case remains unavailable and is identified as an open problem.

Abstract

from arXiv · show

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 $Ω\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.

1. Introduction

The paper addresses dense all-at-once systems from nonlocal evolutionary fractional equations with variable diffusion, using GLT analysis to design an efficient block lower triangular preconditioner.

  • Motivation: Weakly singular temporal kernels and nonlocal spatial operators produce dense discretized systems, making direct methods costly for large problems.Shift-invariant fractional kernels nevertheless induce Toeplitz-type structure.
  • Motivation: All-at-once methods solve the entire space-time system simultaneously rather than advancing sequentially through time.This formulation exposes a structured global linear system suitable for matrix-sequence analysis.
  • Approach: The work focuses on d = 1 and uses GLT theory to characterize the spectral behavior of matrix sequences arising from the discretization.The analysis targets the coefficient matrix so the preconditioner can approximate it spectrally.
  • Approach: The proposed block lower triangular preconditioner mimics the all-at-once coefficient matrix while simplifying its components for computational efficiency.Its construction preserves the essential spectral features associated with the variable diffusion coefficient.
  • Analysis and scope: The preconditioned matrix differs from the identity by a low-rank correction, yielding weak eigenvalue clustering at 1 and validation through GMRES experiments.The paper also notes extensions to general d-dimensional and non-Cartesian problems through reduced multilevel GLT structures.

2. Preliminaries

This section introduces matrix-sequence, spectral-distribution, clustering, and GLT concepts used to analyze discretized operators asymptotically.

  • Matrix sequences: A matrix sequence is a family {A_n}_n whose square dimensions d_n increase monotonically to infinity.The framework studies asymptotic behavior as matrix size grows.
  • Spectral tools: Spectral and singular-value distributions describe the limiting behavior of eigenvalues or singular values through a measurable function ψ.The notation used is {A_n}_n ∼λ ψ for eigenvalues and {A_n}_n ∼σ ψ for singular values.
  • Spectral tools: For large n, the values are interpreted as samples of ψ or |ψ| over its domain, apart from at most o(d_n) outliers.The essential range of ψ provides the corresponding weak-clustering set.
  • Clustering: Weak clustering means that the number of eigenvalues outside every ε-neighborhood of a set S is negligible relative to the matrix size.Strong clustering instead bounds that number by a constant independent of n.
  • GLT framework: A GLT sequence belongs to the *-algebra generated by zero-distributed, Toeplitz, and diagonal sampling matrix sequences and has an essentially unique measurable symbol κ.GLT theory directly yields singular-value distributions, and eigenvalue distributions additionally when the matrices are Hermitian.

Zero-distributed sequences.

The preliminaries characterize zero-distributed sequences through singular values and introduce Toeplitz matrices and diagonal sampling matrices as GLT building blocks.

  • Zero-distributed sequences: A sequence is zero-distributed when its singular-value distribution is described by the zero function.A practical characterization represents each matrix as a sum of a small-rank term and a term with vanishing norm, as specified by the lemma.
  • Toeplitz sequences: A Toeplitz matrix has constant entries along its diagonals and is generated by Fourier coefficients of a function f.The family {T_n(f)}_n is the Toeplitz sequence associated with f.
  • Toeplitz sequences: The Wiener class consists of continuous periodic functions whose Fourier series is absolutely convergent.This class is used to specify regularity for Toeplitz generating functions.
  • Diagonal sampling sequences: A diagonal sampling matrix samples a coefficient function a(x) on the grid and places the samples on its diagonal.These matrices provide the discrete representation of variable coefficients.

Diagonal sampling sequences.

Diagonal sampling sequences encode variable coefficients within the GLT algebra, whose operative properties determine symbols for sums, products, and tensor constructions.

  • Diagonal sampling sequences: The family of diagonal sampling matrices generated by a(x) is denoted {D_n(a)}_n.The matrices are formed by sampling a on the discretization grid.
  • GLT properties: For an almost-everywhere continuous function a, {D_n(a)}_n is a GLT sequence with symbol κ(x, θ) = a(x).The symbol is independent of θ for diagonal sampling sequences.
  • GLT properties: GLT symbols inherit algebraic operations: linear combinations of sequences correspond to the same linear combinations of their symbols.Zero-distributed sequences have the zero GLT symbol.
  • GLT properties: Tensor products of GLT sequences form multilevel GLT sequences whose symbols are tensor products of the component symbols.This supports higher-dimensional constructions.

3. Discretization of (1) and the space-time linear system

The paper discretizes the fractional evolution equation in time with an L1 scheme and in space with a shifted Grünwald finite-difference scheme. These discretizations produce an all-at-once system with temporal lower triangular Toeplitz and spatial nonsymmetric Toeplitz structure.

  • Temporal discretization: The time discretization uses the L1 scheme with temporal step size Δt = T/M.The temporal derivative is discretized at times t_m = mΔt using L1 coefficients.
  • Spatial discretization: The spatial operator uses a left-sided Riemann–Liouville derivative approximated by a shifted Grünwald scheme.The resulting spatial matrix is nonsymmetric Toeplitz.
  • Spatial discretization: The variable diffusion coefficient is represented by the diagonal sampling matrix D_N(a) = diag(a(x_i)).A rescaling of the spatial domain supports the subsequent GLT analysis.
  • All-at-once system: The discretization construction and associated matrix formulation are adopted from prior detailed analyses, with further technical details omitted here.The paper uses the resulting formulation for the subsequent spectral and preconditioning analysis.
  • All-at-once system: Combining the temporal and spatial discretizations yields a dense all-at-once linear system expressed compactly with Kronecker products.The solution vector stacks the spatial solution vectors across all time levels, while B_M denotes the temporal discretization matrix.
  • All-at-once system: The temporal matrix B_M is lower triangular Toeplitz, reflecting the history dependence of the fractional time derivative.Its entries are organized through the L1 coefficients in the displayed matrix structure.

4. Analysis of the space-time matrix structures

The paper uses GLT theory to derive the asymptotic spectral description of the spatial, temporal, and full space-time matrix sequences. The analysis relies on Toeplitz and sampling structures, while identifying unresolved eigenvalue questions for variable-coefficient nonsymmetric matrices.

  • GLT framework: The GLT analysis proceeds from the spatial block to the temporal block and finally to the complete coefficient matrix sequence.This establishes the analysis order for the space-time discretization.
  • Spatial sequence: The spatially varying coefficient a(x) disrupts pure Toeplitz structure, so GLT symbols combine coefficient sampling with Toeplitz generating functions.This combination captures essential spectral features of the full coefficient matrix.
  • Open spectral issue: For variable coefficients, strong numerical agreement between eigenvalues and samples of a(x)f_α(θ) is observed, but a complete theoretical proof remains open.The unresolved issue concerns eigenvalue distribution for the non-Hermitian variable-coefficient spatial matrix.
  • Temporal sequence: The temporal generating function g_β belongs to the Wiener class, making it continuous and 2π-periodic and identifying B_M as its Toeplitz sequence.The result follows from convergence of the coefficient series for β ∈ (0,1).
  • Temporal sequence: All eigenvalues of the lower triangular temporal matrix B_M equal its diagonal coefficient ℓ_0 = b_0.This follows directly from the triangular structure.
  • Full space-time sequence: The full coefficient matrix symbol is obtained by combining the temporal symbol g_β(θ_2) with the spatial symbol γa(x)f_α(θ_1) through the Kronecker-sum structure.The derivation uses GLT tensor-product and algebra properties.

5. Algorithmic proposals and complexity analysis

The paper develops forward block-substitution and global solution strategies using circulant or ω-circulant approximations for the spatial and temporal components. Their GLT analysis supports favorable clustering, while numerical results show iteration stabilization and optimal complexity under bounded iteration counts.

  • Algorithmic proposals: Two solution strategies are considered: forward block substitution and a global solution approach.Both exploit the lower triangular block structure of the all-at-once matrix.
  • Technique 1: Forward block substitution solves M systems sequentially, each involving the same spatial matrix and a circulant-based preconditioner.The preconditioner uses diagonal entries of D_N(a) and a circulant approximation of the Grünwald matrix.
  • Complexity and numerical behavior: The block-substitution cost is 1/2 NM^2 + ♯it M O(N log N), where ♯it is the average number of preconditioned GMRES iterations.The global approach instead has FFT-based preconditioner cost ♯˜it O(MN log NM).
  • Technique 2: The global approach applies preconditioned GMRES directly to the all-at-once system using a circulant or ω-circulant approximation.The corresponding preconditioner is constructed as a structured approximation to the full space-time matrix.
  • Complexity and numerical behavior: Iteration counts stabilize independently of matrix size across the considered parameters, with somewhat larger constants when β is close to 2.For the global proposal, bounded iterations yield optimal O(MN log NM) arithmetic cost.
  • Preconditioning analysis: GLT analysis shows that replacing Toeplitz components by natural circulant or ω-circulant approximations yields singular-value clustering of the differences at zero.This property is established separately for the spatial and temporal components.
  • Preconditioning analysis: The preconditioned matrix associated with the block strategy is analyzed through GLT relations for general Riemann-integrable coefficients.The spatial sampling, Toeplitz symbols, and tensor-product structure are combined through GLT axioms.

6. Numerical Results

The numerical experiments evaluate preconditioned GMRES for forward-block and global solution approaches across constant and variable diffusion coefficients. Iteration counts stabilize independently of matrix size, supporting the scalability and arithmetic-cost claims for Technique 2.

  • Forward block solution: Tables 1–6 evaluate averaged GMRES iterations for forward block solutions with no preconditioner, circulant Pα,N, and ω-circulant Pω,α,N.The tests include a(x) = 1 and a(x) = x2 + 1.
  • Global solution: Tables 7–12 evaluate global-system GMRES iterations without preconditioning, with circulant Pα,β,NM, and with ω-circulant Pω,α,β,MN.The supplied tables include constant and variable diffusion cases.
  • Iteration behavior: The number of preconditioned GMRES iterations stabilizes to a constant independent of matrix size for all tested α, β, and a(x).The stabilized constants are somewhat more pronounced when β is close to 2.
  • Computational cost: Technique 2 has arithmetic cost growing in order as a bivariate FFT because its preconditioned GMRES iteration count remains mild and stable.The reported cost conclusion is tied to the observed optimality of preconditioned GMRES.

7. Conclusion

The paper studies structured all-at-once systems from variable-coefficient fractional evolution equations and analyzes them with GLT theory. It proposes a block lower triangular preconditioner whose numerical performance agrees with the theoretical spectral analysis.

  • Conclusion: The discretized equations produce large structured (d + 1)-level Toeplitz-like all-at-once systems from L1 time and finite-difference spatial approximations.The model includes weakly singular temporal kernels and Riemann–Liouville space fractional derivatives.
  • Conclusion: The proposed block lower triangular preconditioner simplifies the spatial operator’s upper triangular part while preserving the system’s main spectral properties.The preconditioned matrix sequence is well clustered in the singular-value sense.
  • Conclusion: Numerical experiments confirm effectiveness for constant and variable diffusion coefficients, reducing condition numbers and improving GMRES convergence.The improvements include fewer iterations and lower computational cost, consistent with the predicted spectral clustering.
Loading 2608.25796v1…