alphaFeedback

WorksMathematics

Data-driven accelerated multigrid method for Riesz space fractional diffusion equations

AI contributions
Not recorded for this paper
View details

Abstract

The multigrid method is one of the most efficient iterative methods for solving large structured linear systems, and its efficiency stems from the complementarity between the smoother and the coarse grid correction. In this paper, we consider the block Toeplitz linear system obtained by discretizing time dependent Riesz space fractional diffusion equations, and employ the weighted Jacobi iterative method as a smoother. The weighted Jacobi smoother features a simple structure and low computational cost, yet its smoothing property is highly dependent on the relaxation parameter. We adopt Gaussian process regression to select the relaxation parameter to accelerate the convergence of the multigrid method. Numerical experiments confirm the theoretical analysis, which simultaneously verifies the effectiveness and superiority of the data-driven parameter selection strategy.

Introduction

Fractional differential equations are powerful mathematical tools that can accurately describe certain complex phenomena, such as pricing options [1, 17], control problems [10, 23], image processing [4, 2]. Consider a two-dimensional Riesz space fractional diffusion equation as follows:

{d(x,y,t)∂u(x,y,t)∂t−∂γ1u(x,y,t)∂∣x∣γ1−∂γ2u(x,y,t)∂∣y∣γ2=f(x,y,t),(x,y,t)∈Ω×(0,T),u(x,y,t)=0,(x,y,t)∈∂Ω×(0,T),u(x,y,0)=u0(x,y),(x,y)∈Ω‾.(1)\left\{ \begin{aligned} d(x,y,t)\frac{\partial u(x,y,t)}{\partial t} -\frac{\partial^{\gamma_1}u(x,y,t)}{\partial|x|^{\gamma_1}} -\frac{\partial^{\gamma_2}u(x,y,t)}{\partial|y|^{\gamma_2}} &= f(x,y,t), \quad(x,y,t)\in\Omega\times(0,T),\\ u(x,y,t)&=0, \quad(x,y,t)\in\partial\Omega\times(0,T),\\ u(x,y,0)&=u_0(x,y), \quad(x,y)\in\overline{\Omega}. \end{aligned} \right. \tag*{(1)}

where Ω=(xL,xR)×(yL,yR)\Omega=(x_L,x_R)\times(y_L,y_R), ∂Ω\partial\Omega denotes the boundary of Ω\Omega, f(x,y,t)f(x,y,t) is the source term, d(x,y,t)≥0d(x,y,t)\ge0 is the coefficient function. u0(x,y)u_0(x,y) is the initial condition, γ1,γ2∈(1,2)\gamma_1,\gamma_2\in(1,2). Specifically, Riesz fractional derivatives are defined as follows:

∂γ1u(x,y,t)∂∣x∣γ1=σγ1(xLDxγ1+xDxRγ1)u(x,y,t),\frac{\partial^{\gamma_1}u(x,y,t)}{\partial|x|^{\gamma_1}} =\sigma_{\gamma_1}\left({}_{x_L}D_x^{\gamma_1}+{}_xD_{x_R}^{\gamma_1}\right)u(x,y,t),
∂γ2u(x,y,t)∂∣y∣γ2=σγ2(yLDyγ2+yDyRγ2)u(x,y,t).\frac{\partial^{\gamma_2}u(x,y,t)}{\partial|y|^{\gamma_2}} =\sigma_{\gamma_2}\left({}_{y_L}D_y^{\gamma_2}+{}_yD_{y_R}^{\gamma_2}\right)u(x,y,t).

with σγl=−12cos⁡(πγl/2)>0\sigma_{\gamma_l}=-\frac{1}{2\cos(\pi\gamma_l/2)}>0 for l=1,2l=1,2. Owing to the nonlocality of fractional differential operators, it is difficult to obtain the analytical solutions of fractional differential equations, and thus developing efficient numerical methods to acquire their numerical solutions has become a research focus in this field.

Discretizing equation (1) on a uniform grid using the shifted Grünwald difference scheme in space and the backward Euler scheme in time yields a sequence of Toeplitz-like linear systems. Due to the nonlocality of fractional differential operators, the coefficient matrices are generally dense, which renders the discrete linear systems computationally expensive for general purpose solvers. For solving such linear systems, [5] proposed a class of diagonal–Toeplitz splitting (DTS) iteration methods, implemented by alternately solving shifted diagonal and shifted Toeplitz subsystems. Building upon the DTS framework, [16] used a natural τ\tau approximation of the symmetric Toeplitz component and proposed a sine-transform-based splitting preconditioner. More recently, [26] decomposed the coefficient matrix by extracting a scalar matrix, a diagonal compensation matrix, and a block τ\tau matrix. The sum of these matrices was then employed to construct a class of τ\tau-splitting iteration methods.

For certain structured matrices, the multigrid method exhibits excellent solution efficiency[24, 15, 6]. Under suitable conditions, this method enjoys mesh-independent convergence. This advantageous property has drawn the attention of many researchers to investigate the application of multigrid methods to fractional partial differential equations. For instance, [21] employed the two-grid method to solve the dense Toeplitz linear system obtained after discretizing the one-dimensional constant-coefficient fractional diffusion equation, and utilized fast Toeplitz matrix–vector multiplication to reduce the computational overhead. [9] proved the convergence of the multigrid method for two-dimensional space-fractional diffusion equations with constant diffusion coefficients. Based on the generalized locally Toeplitz (GLT) sequences theory, they further extended this result to the case of uniformly bounded and positive variable diffusion coefficients. Furthermore, numerous studies adopt the GLT theory to analyze the spectral properties of coefficient matrices and thereby design multigrid methods[2, 25, 3]. In addition, [7, 8] extended the symbol-based multigrid analysis for scalar Toeplitz matrices to block-circulant and block-Toeplitz systems generated by matrix-valued symbols, and derived sufficient conditions for the two-grid and V-cycle methods.

The multigrid method consists of a smoother and a coarse-grid correction that complement each other. The coarse-grid correction is responsible for eliminating the low-frequency components of the error. For Toeplitz-like matrices, coarse-grid correction using bilinear interpolation as the transfer operator is effective and general [20]. Correspondingly, the smoother should rapidly attenuate the high-frequency components of the error that are difficult for the coarse grid to represent, and it is usually implemented by classical iterative methods. The weighted Jacobi method is widely adopted due to its simplicity and low computational cost per iteration. With an appropriate relaxation parameter, this method exhibits favorable smoothing ability for high-frequency components of the error[30, 32]. Therefore, the proper choice of the relaxation parameter is the key to constructing an efficient smoother.

Previously, research on the selection of relaxation parameters for the weighted Jacobi smoother has mainly focused on classical elliptic partial differential equations[12, 13]. [3]extended this study to dense Toeplitz-type linear systems arising from the discretization of tempered fractional diffusion equations. They used the spectral information provided by the generating function of the coefficient matrix to expand the range of parameters that guarantee the smoothing property of the Jacobi smoother, and gave estimation formulas for suitable relaxation parameters. However, while their estimation formulas yield feasible relaxation parameters, the resulting parameter may not always match the numerically optimal choice for finite-dimensional linear systems.

In recent years, the integration of machine learning with traditional numerical methods has demonstrated great potential. Machine learning techniques can identify nonlinear relationships between problem characteristics and numerical algorithms from data that are difficult to characterize explicitly, thereby providing new approaches to the design of complex numerical algorithms and the automatic selection of their parameters. Moreover, once trained, machine learning models can typically make rapid predictions for new problems at a low computational cost. In the field of multigrid methods, [11, 33, 31] have applied machine learning to the design and optimization of smoothers. In this work, we adopt Gaussian Process Regression (GPR) to learn and select the relaxation parameters of the weighted Jacobi smoother, so as to improve the convergence speed of the multigrid method.

GPR is a Bayesian nonparametric learning method that places a Gaussian process prior on the unknown mapping from problem features to the desired relaxation parameter. Given a small set of training samples, the correlations among the samples are characterized by a covariance kernel, and conditioning the prior on the observed data yields a posterior predictive distribution for a new problem instance. Its mean can be used as the predicted relaxation parameter, while its variance provides a quantitative measure of prediction uncertainty. It can capture nonlinear parameter dependence without prescribing a fixed functional form, perform well with relatively small datasets, and, once trained, deliver predictions at a low online cost.

The paper is organized as follows. In Section 2,we discretize the original equations and analyze the basic spectral properties of the coefficient matrix. In Section 3, with the aid of the Ruge–Stuben two grid framework, we design and analyze the convergence of the two grid method. In Section 4, we introduce the principles of GPR and its procedure for predicting parameters. In Section 5, we present numerical experiments to demonstrate the effectiveness and superiority of the multigrid method and GPR for parameter prediction. In Section 6, we summarize the conclusions and future work.

Discretization and matrix properties

In this section, we will introduce the specific discrete schemes and analyze the properties of the coefficient matrices obtained from the discretization, which will help us design the multigrid method. Below, we review the left- and right-sided Riemann–Liouville fractional derivatives:

xLDxγ1u(x,y,t)=1Γ(2−γ1)d2dx2∫xLxu(ξ,y,t)(x−ξ)γ1−1 dξ,xDxRγ1u(x,y,t)=1Γ(2−γ1)d2dx2∫xxRu(ξ,y,t)(ξ−x)γ1−1 dξ,{}_{x_L}D_{x}^{\gamma_1}u(x,y,t)=\frac{1}{\Gamma(2-\gamma_1)}\frac{d^2}{dx^2}\int_{x_L}^{x}\frac{u(\xi,y,t)}{(x-\xi)^{\gamma_1-1}}\,d\xi,\qquad{}_{x}D_{x_R}^{\gamma_1}u(x,y,t)=\frac{1}{\Gamma(2-\gamma_1)}\frac{d^2}{dx^2}\int_{x}^{x_R}\frac{u(\xi,y,t)}{(\xi-x)^{\gamma_1-1}}\,d\xi,
yLDyγ2u(x,y,t)=1Γ(2−γ2)d2dy2∫yLyu(x,ξ,t)(y−ξ)γ2−1 dξ,yDyRγ2u(x,y,t)=1Γ(2−γ2)d2dy2∫yyRu(x,ξ,t)(ξ−y)γ2−1 dξ.{}_{y_L}D_{y}^{\gamma_2}u(x,y,t)=\frac{1}{\Gamma(2-\gamma_2)}\frac{d^2}{dy^2}\int_{y_L}^{y}\frac{u(x,\xi,t)}{(y-\xi)^{\gamma_2-1}}\,d\xi,\qquad{}_{y}D_{y_R}^{\gamma_2}u(x,y,t)=\frac{1}{\Gamma(2-\gamma_2)}\frac{d^2}{dy^2}\int_{y}^{y_R}\frac{u(x,\xi,t)}{(\xi-y)^{\gamma_2-1}}\,d\xi.

where Γ(⋅)\Gamma(\cdot) is the Gamma function. Let NN, MM be positive integers. Take the step sizes Δx=xR−xLN+1\Delta x=\frac{x_R-x_L}{N+1}, Δy=yR−yLN+1\Delta y=\frac{y_R-y_L}{N+1}, Δt=TM\Delta t=\frac{T}{M} to discretize the xx-direction, yy-direction and time, yielding

{xi∣xi=xL+iΔx,0≤i≤N+1},\left\{x_i\mid x_i=x_L+i\Delta x,0\le i\le N+1\right\},
{yj∣yj=yL+jΔy,0≤j≤N+1},\left\{y_j\mid y_j=y_L+j\Delta y,0\le j\le N+1\right\},
{tm∣tm=mΔt,0≤m≤M}.\left\{t_m\mid t_m=m\Delta t,0\le m\le M\right\}.

Define ui,j(m)=u(xi,yj,tm)u_{i,j}^{(m)}=u(x_i,y_j,t_m), fi,j(m)=f(xi,yj,tm)f_{i,j}^{(m)}=f(x_i,y_j,t_m), di,j(m)=d(xi,yj,tm)d_{i,j}^{(m)}=d(x_i,y_j,t_m). Using the shifted Grünwald formula[19, 18], we can obtain the approximation of the fractional derivative at the point (xi,yj,tm)(x_i,y_j,t_m):

xLDxγ1(xi,yj,tm)=1Δxγ1∑k=0i+1gk(γ1)ui−k+1,j(m)+O(Δx),{}_{x_L}D_{x}^{\gamma_1}(x_i,y_j,t_m)=\frac{1}{\Delta x^{\gamma_1}}\sum_{k=0}^{i+1}g_k^{(\gamma_1)}u_{i-k+1,j}^{(m)}+O(\Delta x),
xDxRγ1(xi,yj,tm)=1Δxγ1∑k=0N−i+2gk(γ1)ui+k−1,j(m)+O(Δx),{}_{x}D_{x_R}^{\gamma_1}(x_i,y_j,t_m)=\frac{1}{\Delta x^{\gamma_1}}\sum_{k=0}^{N-i+2}g_k^{(\gamma_1)}u_{i+k-1,j}^{(m)}+O(\Delta x),

and

yLDyγ2(xi,yj,tm)=1Δyγ2∑k=0j+1gk(γ2)ui,j−k+1(m)+O(Δy),{}_{y_L}D_{y}^{\gamma_2}(x_i,y_j,t_m)=\frac{1}{\Delta y^{\gamma_2}}\sum_{k=0}^{j+1}g_k^{(\gamma_2)}u_{i,j-k+1}^{(m)}+O(\Delta y),
yDyRγ2(xi,yj,tm)=1Δyγ2∑k=0N−j+2gk(γ2)ui,j+k−1(m)+O(Δy).{}_{y}D_{y_R}^{\gamma_2}(x_i,y_j,t_m)=\frac{1}{\Delta y^{\gamma_2}}\sum_{k=0}^{N-j+2}g_k^{(\gamma_2)}u_{i,j+k-1}^{(m)}+O(\Delta y).

where the coefficients gk(γ)g_k^{(\gamma)} are given by the following lemma:

Lemma 2.1. [16] For γ∈(1,2)\gamma\in(1,2), the following recurrence relation holds:

gk(γ)=(1−γ+1k)gk−1(γ)=(−1)kk!γ(γ−1)⋯(γ−k+1),k=1,2,⋯ .g_k^{(\gamma)}=\left(1-\frac{\gamma+1}{k}\right)g_{k-1}^{(\gamma)}=\frac{(-1)^k}{k!}\gamma(\gamma-1)\cdots(\gamma-k+1),\quad k=1,2,\cdots.

Moreover, we have

g0(γ)=1,g1(γ)=−γ<0,1>g2(γ)>g3(γ)>⋯>0,g_0^{(\gamma)}=1,\quad g_1^{(\gamma)}=-\gamma<0,\quad1>g_2^{(\gamma)}>g_3^{(\gamma)}>\cdots>0,

and

∑k=0∞gk(γ)=0,or equivalently,γ=∑k=0k≠1∞gk(γ).\sum_{k=0}^{\infty}g_k^{(\gamma)}=0,\quad\text{or equivalently,}\quad\gamma=\sum_{\substack{k=0\\k\ne1}}^{\infty}g_k^{(\gamma)}.

To facilitate the subsequent analysis, we introduce a matrix TNγ∈RN×NT_N^\gamma\in\mathbb{R}^{N\times N} associated with γ\gamma:

TNγ=−[2g1(γ)g0(γ)+g2(γ)g3(γ)⋯gN−1(γ)gN(γ)g0(γ)+g2(γ)2g1(γ)g0(γ)+g2(γ)⋱⋯gN−1(γ)g3(γ)g0(γ)+g2(γ)2g1(γ)⋱⋱⋮⋮⋱⋱⋱⋱g3(γ)gN−1(γ)⋯⋱⋱2g1(γ)g0(γ)+g2(γ)gN(γ)gN−1(γ)⋯g3(γ)g0(γ)+g2(γ)2g1(γ)].(2)T_N^\gamma=-\begin{bmatrix} 2g_1^{(\gamma)} & g_0^{(\gamma)}+g_2^{(\gamma)} & g_3^{(\gamma)} & \cdots& g_{N-1}^{(\gamma)} & g_N^{(\gamma)}\\ g_0^{(\gamma)}+g_2^{(\gamma)} & 2g_1^{(\gamma)} & g_0^{(\gamma)}+g_2^{(\gamma)} & \ddots& \cdots& g_{N-1}^{(\gamma)}\\ g_3^{(\gamma)} & g_0^{(\gamma)}+g_2^{(\gamma)} & 2g_1^{(\gamma)} & \ddots& \ddots& \vdots\\ \vdots& \ddots& \ddots& \ddots& \ddots& g_3^{(\gamma)}\\ g_{N-1}^{(\gamma)} & \cdots& \ddots& \ddots& 2g_1^{(\gamma)} & g_0^{(\gamma)}+g_2^{(\gamma)}\\ g_N^{(\gamma)} & g_{N-1}^{(\gamma)} & \cdots& g_3^{(\gamma)} & g_0^{(\gamma)}+g_2^{(\gamma)} & 2g_1^{(\gamma)} \end{bmatrix}. \tag*{(2)}

According to Lemma 2.1, TNγT_N^\gamma is a matrix that is strictly diagonally dominant, symmetric, and has all positive diagonal entries. Therefore, TNγT_N^\gamma is a symmetric positive definite matrix. Let

u(m)=[u1,1(m),u2,1(m),…,uN,1(m),u1,2(m),u2,2(m),…,uN,2(m),…,u1,N(m),u2,N(m),…,uN,N(m)]T,\mathbf{u}^{(m)}=[u_{1,1}^{(m)},u_{2,1}^{(m)},\ldots,u_{N,1}^{(m)},u_{1,2}^{(m)},u_{2,2}^{(m)},\ldots,u_{N,2}^{(m)},\ldots,u_{1,N}^{(m)},u_{2,N}^{(m)},\ldots,u_{N,N}^{(m)}]^{T},
f(m)=[f1,1(m),f2,1(m),…,fN,1(m),f1,2(m),f2,2(m),…,fN,2(m),…,f1,N(m),f2,N(m),…,fN,N(m)]T,\mathbf{f}^{(m)}=[f_{1,1}^{(m)},f_{2,1}^{(m)},\ldots,f_{N,1}^{(m)},f_{1,2}^{(m)},f_{2,2}^{(m)},\ldots,f_{N,2}^{(m)},\ldots,f_{1,N}^{(m)},f_{2,N}^{(m)},\ldots,f_{N,N}^{(m)}]^{T},
D(m)=diag⁡(d1,1(m),d2,1(m),…,dN,1(m),d1,2(m),d2,2(m),…,dN,2(m),…,d1,N(m),d2,N(m),…,dN,N(m)).D^{(m)}=\operatorname{diag}(d_{1,1}^{(m)},d_{2,1}^{(m)},\ldots,d_{N,1}^{(m)},d_{1,2}^{(m)},d_{2,2}^{(m)},\ldots,d_{N,2}^{(m)},\ldots,d_{1,N}^{(m)},d_{2,N}^{(m)},\ldots,d_{N,N}^{(m)}).

We discretize (1.1) in the spatial direction using the shifted Grunwald formula and in the temporal direction using the backward Euler scheme to obtain the implicit finite-difference scheme:

di,j(m)ui,j(m)−ui,j(m−1)Δt−σγ1Δxγ1(∑k=0i+1gk(γ1)ui−k+1,j(m)+∑k=0N−i+2gk(γ1)ui+k−1,j(m))−σγ2Δyγ2(∑k=0j+1gk(γ2)ui,j−k+1(m)+∑k=0N−j+2gk(γ2)ui,j+k−1(m))=fi,j(m).d_{i,j}^{(m)}\frac{u_{i,j}^{(m)}-u_{i,j}^{(m-1)}}{\Delta t} -\frac{\sigma_{\gamma_1}}{\Delta x^{\gamma_1}}\left(\sum_{k=0}^{i+1}g_k^{(\gamma_1)}u_{i-k+1,j}^{(m)}+\sum_{k=0}^{N-i+2}g_k^{(\gamma_1)}u_{i+k-1,j}^{(m)}\right) -\frac{\sigma_{\gamma_2}}{\Delta y^{\gamma_2}}\left(\sum_{k=0}^{j+1}g_k^{(\gamma_2)}u_{i,j-k+1}^{(m)}+\sum_{k=0}^{N-j+2}g_k^{(\gamma_2)}u_{i,j+k-1}^{(m)}\right)=f_{i,j}^{(m)}.

Furthermore, we have

D(m)u(m)−u(m−1)Δt+(σγ1Δxγ1IN⊗TNγ1+σγ2Δyγ2TNγ2⊗IN)u(m)=f(m).D^{(m)}\frac{\mathbf{u}^{(m)}-\mathbf{u}^{(m-1)}}{\Delta t}+\left(\frac{\sigma_{\gamma_1}}{\Delta x^{\gamma_1}}I_N\otimes T_N^{\gamma_1}+\frac{\sigma_{\gamma_2}}{\Delta y^{\gamma_2}}T_N^{\gamma_2}\otimes I_N\right)\mathbf{u}^{(m)}=\mathbf{f}^{(m)}.

Let η1=σγ1ΔtΔxγ1\eta_1=\sigma_{\gamma_1}\frac{\Delta t}{\Delta x^{\gamma_1}}, η2=σγ2ΔtΔyγ2\eta_2=\sigma_{\gamma_2}\frac{\Delta t}{\Delta y^{\gamma_2}}. Consequently, we obtain

(D(m)+η1IN⊗TNγ1+η2TNγ2⊗IN)u(m)=Δtf(m)+D(m)u(m−1).(3)\left(D^{(m)}+\eta_1I_N\otimes T_N^{\gamma_1}+\eta_2T_N^{\gamma_2}\otimes I_N\right)\mathbf{u}^{(m)}=\Delta t\mathbf{f}^{(m)}+D^{(m)}\mathbf{u}^{(m-1)}. \tag*{(3)}

Dividing both sides of (2.2) by η1\eta_1, we have

(1η1D(m)+IN⊗TNγ1+η2η1TNγ2⊗IN)u(m)=1η1Δtf(m)+1η1D(m)u(m−1).\left(\frac{1}{\eta_1}D^{(m)}+I_N\otimes T_N^{\gamma_1}+\frac{\eta_2}{\eta_1}T_N^{\gamma_2}\otimes I_N\right)\mathbf{u}^{(m)}=\frac{1}{\eta_1}\Delta t\mathbf{f}^{(m)}+\frac{1}{\eta_1}D^{(m)}\mathbf{u}^{(m-1)}.

Define

AN(m)=1η1D(m)+IN⊗TNγ1+η2η1TNγ2⊗IN,A_N^{(m)}=\frac{1}{\eta_1}D^{(m)}+I_N\otimes T_N^{\gamma_1}+\frac{\eta_2}{\eta_1}T_N^{\gamma_2}\otimes I_N,
b(m)=1η1Δtf(m)+1η1D(m)u(m−1).(4)\mathbf{b}^{(m)}=\frac{1}{\eta_1}\Delta t\mathbf{f}^{(m)}+\frac{1}{\eta_1}D^{(m)}\mathbf{u}^{(m-1)}. \tag*{(4)}

Then (2.2) is equivalent to

AN(m)u(m)=b(m),1≤m≤M.(5)A_N^{(m)}\mathbf{u}^{(m)}=\mathbf{b}^{(m)},\qquad1\leq m\leq M. \tag*{(5)}

After fixing the partition number NN, discretizing (1.1) yields a set of matrices {AN(m)}\{A_N^{(m)}\}. When the coefficient d(x,y,t)=0d(x,y,t)=0, D(m)D^{(m)} degenerates to the zero matrix, and in this case, AN(m)A_N^{(m)} is independent of the time level mm and is denoted by ANA_N. The matrix ANA_N is symmetric positive definite and strictly diagonally dominant, and it is a Block-Toeplitz-Toeplitz-Block (BTTB) matrix.

BTTB matrices belong to the class of multilevel Toeplitz matrices, and their spectral information is closely related to the generating function of the corresponding BTTB matrix sequence. Let us now recall the definitions of Toeplitz matrix sequences and BTTB matrix sequences.

Definition 2.1.[20] Let f(θ)∈L1([−π,π])f(\theta)\in L^1([-\pi,\pi]) and let {fk}\{f_k\} be the Fourier coefficients defined as

fk:=12π∫[−π,π]f(θ)e−ikθ dθ.f_k:=\frac{1}{2\pi}\int_{[-\pi,\pi]}f(\theta)e^{-ik\theta}\,d\theta.

where i2=−1i^2=-1. Then the Toeplitz matrix of order nn associated with f(θ)f(\theta) is

Tn(f)=[fi−j]i,j=1n.T_n(f)=[f_{i-j}]_{i,j=1}^n.

The function f(θ)f(\theta) is called the generating function of the matrix sequence {Tn(f)}n∈N\{T_n(f)\}_{n\in\mathbb{N}}.

Definition 2.2.[20] Let f(θ1,θ2)∈L1([−π,π]2)f(\theta_1,\theta_2)\in L^1([-\pi,\pi]^2) and let {f[k1,k2]}\{f_{[k_1,k_2]}\} be the Fourier coefficients defined as

f[k1,k2]=14π2∫−ππ∫−ππf(θ1,θ2)e−i(k1θ1+k2θ2) dθ1 dθ2.f_{[k_1,k_2]}=\frac{1}{4\pi^2}\int_{-\pi}^{\pi}\int_{-\pi}^{\pi}f(\theta_1,\theta_2)e^{-i(k_1\theta_1+k_2\theta_2)}\,d\theta_1\,d\theta_2.

Then the Block-Toeplitz-Toeplitz-Blocks matrix of order n=n1n2n=n_1n_2 associated with f(θ1,θ2)f(\theta_1,\theta_2) is

Tn(2)(f)=[[f[i1−j1,i2−j2]]i2,j2=1n2]i1,j1=1n1.T_n^{(2)}(f)=\left[\left[f_{[i_1-j_1,i_2-j_2]}\right]_{i_2,j_2=1}^{n_2}\right]_{i_1,j_1=1}^{n_1}.

Accordingly, f(θ1,θ2)f(\theta_1,\theta_2) is called the generating function of matrix sequence {Tn(2)(f)}n∈N\{T_n^{(2)}(f)\}_{n\in\mathbb{N}}. Moreover, Tn(2)(f)T_n^{(2)}(f) also admits the following representation:

Tn(2)(f)=∑∣k1∣<n1∑∣k2∣<n2f[k1,k2]Jn1[k1]⊗Jn2[k2].(6)T_n^{(2)}(f)=\sum_{|k_1|<n_1}\sum_{|k_2|<n_2}f_{[k_1,k_2]}J_{n_1}^{[k_1]}\otimes J_{n_2}^{[k_2]}. \tag*{(6)}

where Jn[k]J_n^{[k]} is the matrix of order nn whose (i,j)(i,j) entry equals 1 if i−j=ki-j=k and zero otherwise.

In order to obtain the generating function of {AN}N∈N\{A_N\}_{N\in\mathbb{N}}, we first give the following lemma.

Lemma 2.2. [22, 9] Let γ∈(1,2)\gamma\in(1,2). The generating function of {TNγ}N∈N\{T_N^\gamma\}_{N\in\mathbb{N}} in (2.1) is real-valued and even, and its specific form is as follows:

fγ(θ)=−2γ+1(sin⁡∣θ∣2)γcos⁡(∣θ∣(1−γ2)+γπ2).(7)f_\gamma(\theta)=-2^{\gamma+1}\left(\sin\frac{|\theta|}{2}\right)^\gamma\cos\left(|\theta|\left(1-\frac{\gamma}{2}\right)+\frac{\gamma\pi}{2}\right). \tag*{(7)}

Proof. It is noted that the generating function of {TNγ}N∈N\{T_N^\gamma\}_{N\in\mathbb{N}} is

fγ(θ)=∑k=−∞∞fkeikθ,f_\gamma(\theta)=\sum_{k=-\infty}^{\infty}f_k e^{ik\theta},

where the coefficients are given by

f0=−2g1(γ),f1=f−1=−g0(γ)−g2(γ),fk=f−k=−gk+1(γ),k≥2.f_0=-2g_1^{(\gamma)},\qquad f_1=f_{-1}=-g_0^{(\gamma)}-g_2^{(\gamma)},\qquad f_k=f_{-k}=-g_{k+1}^{(\gamma)},\quad k\geq2.

Furthermore, we obtain that

∑k=−∞∞fkeikθ=−∑k=−1∞gk+1(γ)eikθ−∑k=−1∞gk+1(γ)e−ikθ.\sum_{k=-\infty}^{\infty}f_k e^{ik\theta} =-\sum_{k=-1}^{\infty}g_{k+1}^{(\gamma)}e^{ik\theta} -\sum_{k=-1}^{\infty}g_{k+1}^{(\gamma)}e^{-ik\theta}.

By virtue of the results in [9], we have

−∑k=−1∞gk+1(γ)eikθ=−e−iθ(1−eiθ)γ,-\sum_{k=-1}^{\infty}g_{k+1}^{(\gamma)}e^{ik\theta} =-e^{-i\theta}(1-e^{i\theta})^\gamma,

and

−∑k=−1∞gk+1(γ)e−ikθ=−eiθ(1−e−iθ)γ.-\sum_{k=-1}^{\infty}g_{k+1}^{(\gamma)}e^{-ik\theta} =-e^{i\theta}(1-e^{-i\theta})^\gamma.

Owing to

1−eiθ={2∣sin⁡θ2∣ei2(θ−π),0≤θ≤π,2∣sin⁡θ2∣ei2(θ+π),−π≤θ<0,and1−e−iθ={2∣sin⁡θ2∣e−i2(θ−π),0≤θ≤π,2∣sin⁡θ2∣e−i2(θ+π),−π≤θ<0.1-e^{i\theta}= \begin{cases} 2\left|\sin\frac{\theta}{2}\right|e^{\frac{i}{2}(\theta-\pi)}, & 0\leq\theta\leq\pi,\\ 2\left|\sin\frac{\theta}{2}\right|e^{\frac{i}{2}(\theta+\pi)}, & -\pi\leq\theta<0, \end{cases} \qquad\text{and}\qquad 1-e^{-i\theta}= \begin{cases} 2\left|\sin\frac{\theta}{2}\right|e^{-\frac{i}{2}(\theta-\pi)}, & 0\leq\theta\leq\pi,\\ 2\left|\sin\frac{\theta}{2}\right|e^{-\frac{i}{2}(\theta+\pi)}, & -\pi\leq\theta<0. \end{cases}

When 0≤θ≤π0\leq\theta\leq\pi,

fγ(θ)=−e−iθ(1−eiθ)γ−eiθ(1−e−iθ)γ=−e−iθ2γ∣sin⁡γθ2∣eiγ2(θ−π)−eiθ2γ∣sin⁡γθ2∣e−iγ2(θ−π)=−2γ∣sin⁡γθ2∣(ei(θ(γ2−1)−γπ2)+ei(−θ(γ2−1)+γπ2))=−2γ+1∣sin⁡γθ2∣cos⁡(θ(1−γ2)+γπ2).\begin{aligned} f_\gamma(\theta) &=-e^{-i\theta}(1-e^{i\theta})^\gamma-e^{i\theta}(1-e^{-i\theta})^\gamma\\ &=-e^{-i\theta}2^\gamma\left|\sin^\gamma\frac{\theta}{2}\right|e^{\frac{i\gamma}{2}(\theta-\pi)} -e^{i\theta}2^\gamma\left|\sin^\gamma\frac{\theta}{2}\right|e^{-\frac{i\gamma}{2}(\theta-\pi)}\\ &=-2^\gamma\left|\sin^\gamma\frac{\theta}{2}\right| \left(e^{i\left(\theta\left(\frac{\gamma}{2}-1\right)-\frac{\gamma\pi}{2}\right)} +e^{i\left(-\theta\left(\frac{\gamma}{2}-1\right)+\frac{\gamma\pi}{2}\right)}\right)\\ &=-2^{\gamma+1}\left|\sin^\gamma\frac{\theta}{2}\right| \cos\left(\theta\left(1-\frac{\gamma}{2}\right)+\frac{\gamma\pi}{2}\right). \end{aligned}

When −π<θ≤0-\pi<\theta\leq0,

fγ(θ)=−2γ∣sin⁡γθ2∣(ei(θ(γ2−1)+γπ2)+ei(−θ(γ2−1)−γπ2))=−2γ+1∣sin⁡γθ2∣cos⁡(−θ(1−γ2)+γπ2).\begin{aligned} f_\gamma(\theta) &=-2^\gamma\left|\sin^\gamma\frac{\theta}{2}\right| \left(e^{i\left(\theta\left(\frac{\gamma}{2}-1\right)+\frac{\gamma\pi}{2}\right)} +e^{i\left(-\theta\left(\frac{\gamma}{2}-1\right)-\frac{\gamma\pi}{2}\right)}\right)\\ &=-2^{\gamma+1}\left|\sin^\gamma\frac{\theta}{2}\right| \cos\left(-\theta\left(1-\frac{\gamma}{2}\right)+\frac{\gamma\pi}{2}\right). \end{aligned}

::: Combining the two gives (7). The Proof is completed.

With the above preparations, we obtain the generating function of the BTTB matrix sequence {AN}N∈N\{A_N\}_{N\in\mathbb{N}}.

Theorem 2.1. Let γ1,γ2∈(1,2)\gamma_1,\gamma_2\in(1,2). Then ANA_N is the BTTB matrix given by AN=Tn(2)(fγ1,γ2)A_N=T_n^{(2)}(f_{\gamma_1,\gamma_2}) with

fγ1,γ2(θ1,θ2)=fγ1(θ1)+η2η1fγ2(θ2),(8)f_{\gamma_1,\gamma_2}(\theta_1,\theta_2)=f_{\gamma_1}(\theta_1)+\frac{\eta_2}{\eta_1}f_{\gamma_2}(\theta_2), \tag*{(8)}

where η1=σγ1ΔtΔxγ1\eta_1=\sigma_{\gamma_1}\frac{\Delta t}{\Delta x^{\gamma_1}}, η2=σγ2ΔtΔyγ2\eta_2=\sigma_{\gamma_2}\frac{\Delta t}{\Delta y^{\gamma_2}}, and fγ(θ)f_\gamma(\theta) is defined in (7).

Proof. By the definition of ANA_N, we have

AN=IN⊗Tγ1+η2η1Tγ2⊗IN.A_N=I_N\otimes T_{\gamma_1}+\frac{\eta_2}{\eta_1}T_{\gamma_2}\otimes I_N.

where

IN⊗Tγ1=TN(1)⊗TN(fγ1)=Tn(2)(f~γ1),I_N\otimes T_{\gamma_1}=T_N(1)\otimes T_N(f_{\gamma_1})=T_n^{(2)}(\widetilde{f}_{\gamma_1}),
Tγ2⊗IN=TN(fγ2)⊗TN(1)=Tn(2)(f~γ2).T_{\gamma_2}\otimes I_N=T_N(f_{\gamma_2})\otimes T_N(1)=T_n^{(2)}(\widetilde{f}_{\gamma_2}).

Moreover, the Fourier coefficients of f~γ1\widetilde{f}_{\gamma_1} and f~γ2\widetilde{f}_{\gamma_2} are given by

(f~γ1)[k1,k2]={(fγ1)k1,k2=0,0,k2≠0,and(f~γ2)[k1,k2]={(fγ2)k2,k1=0,0,k1≠0.\left(\widetilde{f}_{\gamma_1}\right)_{[k_1,k_2]}= \begin{cases} (f_{\gamma_1})_{k_1}, & k_2=0,\\ 0, & k_2\ne0, \end{cases} \qquad\text{and}\qquad \left(\widetilde{f}_{\gamma_2}\right)_{[k_1,k_2]}= \begin{cases} (f_{\gamma_2})_{k_2}, & k_1=0,\\ 0, & k_1\ne0. \end{cases}

Hence, f~γ1(θ1,θ2)=fγ1(θ1)\widetilde{f}_{\gamma_1}(\theta_1,\theta_2)=f_{\gamma_1}(\theta_1) and f~γ2(θ1,θ2)=fγ2(θ2)\widetilde{f}_{\gamma_2}(\theta_1,\theta_2)=f_{\gamma_2}(\theta_2). Therefore, the generating function of {AN}N∈N\{A_N\}_{N\in\mathbb{N}} is

fγ1,γ2(θ1,θ2)=fγ1(θ1)+η2η1fγ2(θ2).f_{\gamma_1,\gamma_2}(\theta_1,\theta_2)=f_{\gamma_1}(\theta_1)+\frac{\eta_2}{\eta_1}f_{\gamma_2}(\theta_2).

The proof is completed.

Remark 2.1. If a bivariate function f(θ1,θ2)f(\theta_1,\theta_2) satisfies f(θ1,θ2)=f(∣θ1∣,∣θ2∣)f(\theta_1,\theta_2)=f(\lvert\theta_1\rvert,\lvert\theta_2\rvert), then f(θ1,θ2)f(\theta_1,\theta_2) is called an even function. It is easy to verify that fγ1,γ2(θ1,θ2)f_{\gamma_1,\gamma_2}(\theta_1,\theta_2) is a bivariate continuous real-valued even function.

For a real-valued continuous even function f(θ1,θ2)f(\theta_1,\theta_2), the associated BTTB matrix Tn(2)(f)T_n^{(2)}(f) is real symmetric. To characterize the spectrum of the matrices generated by fγ1,γ2(θ1,θ2)f_{\gamma_1,\gamma_2}(\theta_1,\theta_2), we recall the following standard result, which bounds the eigenvalues in terms of the minimum and maximum of the generating function:

Lemma 2.3. [28] Let f(θ1,θ2)∈C1([−π,π]2)f(\theta_1,\theta_2)\in C^1([-\pi,\pi]^2) be a real-valued even function, with its maximum and minimum denoted by fmax⁡f_{\max} and fmin⁡f_{\min}, respectively. Then Tn(2)(f)T_n^{(2)}(f) is a real symmetric matrix, and its eigenvalues are bounded by the range of f(θ1,θ2)f(\theta_1,\theta_2) in the sense that

fmin⁡≤λmin⁡(Tn(2)(f))≤λmax⁡(Tn(2)(f))≤fmax⁡.(9)f_{\min}\le\lambda_{\min}\left(T_n^{(2)}(f)\right)\le\lambda_{\max}\left(T_n^{(2)}(f)\right)\le f_{\max}. \tag*{(9)}

Two Grid method

The Galerkin multigrid method belongs to the class of classical multigrid methods and is primarily applicable to symmetric positive definite linear systems Au=bAu=b. Its simplest form is the two grid method (TGM), which consists of a smoother and a coarse-grid correction. Multi-level schemes such as the V-cycle are realized by recursively cycling the TGM. The specific procedure of the TGM is shown in Table 1. In this paper, we choose the weighted Jacobi as the smoother, whose update formula is

1) Pre-smoothing: Apply j1j_1 iterations of GG to the system Au=bAu=b to obtain u(j1)u^{(j_1)}
2) Compute the residual: r=b−Au(j1)r=b-Au^{(j_1)}
3) Restriction: bH=IhHrb_H=I_h^H r
4) Coarse grid equation solving: Solve the system AHe^=bHA_H\widehat{e}=b_H exactly to obtain e^\widehat{e}
5) Update solution u^=u(j1)+IHhe^\widehat{u}=u^{(j_1)}+I_H^h\widehat{e}
6) Post-smoothing: Starting from u^\widehat{u}, perform j2j_2 iterations using GG

Table 1. Two Grid method

u(j+1)=Gu(j)+ωdiag⁡(A)−1b,u^{(j+1)} = G u^{(j)} + \omega\operatorname{diag}(A)^{-1}b,

where u(j)u^{(j)} is the iteration vector at the jj-th step, and

G=In−ωdiag⁡(A)−1A.(10)G = I_n - \omega\operatorname{diag}(A)^{-1}A. \tag*{(10)}

The coarse grid correction is obtained by combining the restriction operator IhHI_h^H and the prolongation operator IHhI_H^h, where IhHI_h^H is a rectangular matrix with full row rank. Specifically, we take

IhH=P⊗P,(11)I_h^H = P \otimes P, \tag*{(11)}

where

P=[121121⋱⋱⋱121]∈R[N2]×N.P = \begin{bmatrix} 1 & 2 & 1 \\ & 1 & 2 & 1 \\ & \ddots& \ddots& \ddots\\ && 1 & 2 & 1 \end{bmatrix} \in\mathbb{R}^{[\frac{N}{2}]\times N}.

The prolongation operator is defined by

IHh=(IhH)T=PT⊗PT,(12)I_H^h = (I_h^H)^T = P^T \otimes P^T, \tag*{(12)}

which defines a Galerkin coarse matrix AH=IhHAIHhA_H = I_h^H A I_H^h.

Take j1=0j_1=0, j2=1j_2=1. In this setting, the iteration matrix of the TGM is given as follows:

ETG=G(In−IHh(IhHAIHh)−1IhHA).(13)E_{TG}=G\left(I_n-I_H^h\left(I_h^H A I_H^h\right)^{-1}I_h^H A\right). \tag*{(13)}

ETGE_{TG} is also referred to as the two grid error propagation operator. To characterize its convergence, we introduce the following inner product and the corresponding induced energy norm.

Definition 3.1. Let ⟨u,v⟩\langle u,v\rangle be the standard Euclidean inner product, and let A=(aij)∈Rn×nA=(a_{ij})\in\mathbb{R}^{n\times n} be a symmetric positive definite matrix. Define

⟨u,v⟩0,A=⟨diag⁡(A)u,v⟩,⟨u,v⟩1,A=⟨Au,v⟩,⟨u,v⟩2,A=⟨(diag⁡(A))−1Au,Av⟩.(14)\langle u,v\rangle_{0,A}=\langle\operatorname{diag}(A)u,v\rangle,\quad\langle u,v\rangle_{1,A}=\langle Au,v\rangle,\quad\langle u,v\rangle_{2,A}=\langle(\operatorname{diag}(A))^{-1}Au,Av\rangle. \tag*{(14)}

The corresponding energy norms are

∥u∥0,A=⟨u,u⟩0,A,∥u∥1,A=⟨u,u⟩1,A,∥u∥2,A=⟨u,u⟩2,A.(15)\lVert u\rVert_{0,A}=\sqrt{\langle u,u\rangle_{0,A}},\quad\lVert u\rVert_{1,A}=\sqrt{\langle u,u\rangle_{1,A}},\quad\lVert u\rVert_{2,A}=\sqrt{\langle u,u\rangle_{2,A}}. \tag*{(15)}

For the TGM, Ruge and Stüben established the following analytical framework, which reduces the overall convergence analysis of the method to the separate examination and characterization of the properties of the smoother and prolongation operators.

Lemma 3.1. [24] Let A=(aij)∈Rn×nA=(a_{ij})\in\mathbb{R}^{n\times n} be a symmetric positive definite matrix, and let GG be the smoother for the TGM. Suppose the prolongation operator IHh∈Rn×ncI_{H}^{h}\in\mathbb{R}^{n\times n_c} (nc<nn_c<n) is a column-full-rank matrix. If

(1): There exists a constant α>0\alpha>0 such that

∥Geh∥1,A2≤∥eh∥1,A2−α∥eh∥2,A2,∀eh∈Rn.(16)\lVert G e^{h}\rVert_{1,A}^{2}\leq\lVert e^{h}\rVert_{1,A}^{2}-\alpha\lVert e^{h}\rVert_{2,A}^{2},\quad\forall e^{h}\in\mathbb{R}^{n}. \tag*{(16)}

(Smoothing property)

(2): There exists a constant β>0\beta>0 such that

min⁡eH∈Rnc∥eh−IHheH∥0,A2≤β∥eh∥1,A2,∀eh∈Rn.(17)\min_{e^{H}\in\mathbb{R}^{n_c}}\lVert e^{h}-I_{H}^{h}e^{H}\rVert_{0,A}^{2}\leq\beta\lVert e^{h}\rVert_{1,A}^{2},\quad\forall e^{h}\in\mathbb{R}^{n}. \tag*{(17)}

(Approximation property)

Then β≥α\beta\geq\alpha and spectral radius of ETGE_{TG} satisfies

ρ(ETG)≤∥ETG∥1,A≤1−αβ<1.\rho(E_{TG})\leq\lVert E_{TG}\rVert_{1,A}\leq\sqrt{1-\frac{\alpha}{\beta}}<1.

Ruge and Stüben also rigorously discussed the range of the relaxation parameter ω\omega when the smoother GG is taken as the weighted Jacobi iteration method, in order to guarantee the smoothing property, namely the following lemma:

Lemma 3.2. [24] Let A=(aij)∈Rn×nA=(a_{ij})\in\mathbb{R}^{n\times n} be a symmetric positive definite matrix, and let

G=In−ωdiag⁡(A)−1A.G=I_n-\omega\operatorname{diag}(A)^{-1}A.

If the relaxation parameter ω\omega satisfies

ω∈(0,2ρ(diag⁡(A)−1A)),\omega\in\left(0,\frac{2}{\rho(\operatorname{diag}(A)^{-1}A)}\right),

then there exists a constant α>0\alpha>0 such that inequality (16) in Lemma 3.1 holds.

We first establish a TGM analysis for ANA_N, verifying that it satisfies both the smoothing property and the approximation property. Building upon this, by utilizing the perturbation property of positive diagonal matrices, we further derive the TGM analysis for AN(m)A_N^{(m)}.

Theorem 3.1. Let AN=Tn(2)(fγ1,γ2(θ1,θ2))A_N=T_n^{(2)}(f_{\gamma_1,\gamma_2}(\theta_1,\theta_2)), where fγ1,γ2(θ1,θ2)f_{\gamma_1,\gamma_2}(\theta_1,\theta_2) is given by (8). Let G=In−ω(diag⁡(AN))−1ANG=I_n-\omega\left(\operatorname{diag}(A_N)\right)^{-1}A_N. If ω\omega satisfies 0<ω<2a0∥fγ1,γ2∥∞0<\omega<\frac{2a_0}{\lVert f_{\gamma_1,\gamma_2}\rVert_\infty}, where a0=−2g1(γ1)−2γ2η1g1(γ2)a_0=-2g_1^{(\gamma_1)}-\frac{2\gamma_2}{\eta_1}g_1^{(\gamma_2)}, then there exists a constant α\alpha satisfying (16) in Lemma 3.1.

Proof. Since all diagonal entries of ANA_N are a0a_0, we have

2λmax⁡(diag⁡(AN)−1AN)=2a0λmax⁡(AN).\frac{2}{\lambda_{\max}\left(\operatorname{diag}(A_N)^{-1}A_N\right)} =\frac{2a_0}{\lambda_{\max}(A_N)}.

By Lemma 2.3, we obtain

2a0∥fγ1,γ2∥∞≤2a0λmax⁡(AN).\frac{2a_0}{\lVert f_{\gamma_1,\gamma_2}\rVert_\infty} \leq\frac{2a_0}{\lambda_{\max}(A_N)}.

Thus, from Lemma 3.2, a sufficient condition for ω\omega is

ω∈(0,2a0∥fγ1,γ2∥∞).\omega\in\left(0,\frac{2a_0}{\lVert f_{\gamma_1,\gamma_2}\rVert_\infty}\right).

The Proof is completed.

The approximation properties of prolongation operators were studied in [28]. In particular, sufficient conditions were established under which a BTTB matrix generated by a nonnegative even function ensures that the IHhI_H^h defined by (3.2) satisfies (3.8). More precisely, the following lemma holds.

Lemma 3.3. [28] If the nonnegative even function f(θ1,θ2)∈C1[−π,π]2f(\theta_1,\theta_2) \in C^1[-\pi,\pi]^2 satisfies:

min⁡(θ1,θ2)∈[−π,π]2f(θ1,θ2)2−cos⁡θ1−cos⁡θ2>0.\min_{(\theta_1,\theta_2)\in[-\pi,\pi]^2}\frac{f(\theta_1,\theta_2)}{2-\cos\theta_1-\cos\theta_2}>0.

then the BTTB matrix Tn(2)(f)T_n^{(2)}(f) generated by ff satisfies the following property: there exists a constant β\beta such that (3.8) holds, where the prolongation operator IHhI_H^h is defined by (3.3).

Theorem 3.2. Let AN=Tn(2)(fγ1,γ2(θ1,θ2))A_N=T_n^{(2)}(f_{\gamma_1,\gamma_2}(\theta_1,\theta_2)), where fγ1,γ2(θ1,θ2)f_{\gamma_1,\gamma_2}(\theta_1,\theta_2) is given by (2.7). Let IHhI_H^h be defined as in (3.3). Then there exists a constant β\beta satisfying (3.8) in Lemma 3.1.

Proof. Set

η=η2η1>0.\eta=\frac{\eta_2}{\eta_1}>0.

Define

ϕγ(θ)=∣θ∣(1−γ2)+γπ2.\phi_\gamma(\theta)=|\theta|\left(1-\frac{\gamma}{2}\right)+\frac{\gamma\pi}{2}.

Since ∣θ∣∈[0,π]|\theta|\in[0,\pi] and γ∈(1,2)\gamma\in(1,2), we have

−cos⁡(ϕγ(θ))≥−cos⁡(γπ2)-\cos(\phi_\gamma(\theta))\ge-\cos\left(\frac{\gamma\pi}{2}\right)

and

(sin⁡∣θ∣2)γ≥sin⁡2∣θ∣2=1−cos⁡θ2.\left(\sin\frac{|\theta|}{2}\right)^\gamma\ge\sin^2\frac{|\theta|}{2}=\frac{1-\cos\theta}{2}.

Then

fγ(θ)=−2γ+1(sin⁡∣θ∣2)γcos⁡(ϕγ(θ))≥−2γcos⁡(γπ2)(1−cos⁡θ).\begin{aligned} f_\gamma(\theta)&=-2^{\gamma+1}\left(\sin\frac{|\theta|}{2}\right)^\gamma\cos(\phi_\gamma(\theta))\\ &\ge-2^\gamma\cos\left(\frac{\gamma\pi}{2}\right)(1-\cos\theta). \end{aligned}

Consequently, for every (θ1,θ2)≠(0,0)(\theta_1,\theta_2)\ne(0,0),

fγ1,γ2(θ1,θ2)=fγ1(θ1)+ηfγ2(θ2)≥−2γ1(cos⁡γ1π2)(1−cos⁡θ1)−η2γ2(cos⁡γ2π2)(1−cos⁡θ2)≥min⁡{−2γ1(cos⁡γ1π2),−η2γ2(cos⁡γ2π2)}(2−cos⁡θ1−cos⁡θ2).\begin{aligned} f_{\gamma_1,\gamma_2}(\theta_1,\theta_2) &=f_{\gamma_1}(\theta_1)+\eta f_{\gamma_2}(\theta_2)\\ &\ge-2^{\gamma_1}\left(\cos\frac{\gamma_1\pi}{2}\right)(1-\cos\theta_1)-\eta2^{\gamma_2}\left(\cos\frac{\gamma_2\pi}{2}\right)(1-\cos\theta_2)\\ &\ge\min\left\{-2^{\gamma_1}\left(\cos\frac{\gamma_1\pi}{2}\right),-\eta2^{\gamma_2}\left(\cos\frac{\gamma_2\pi}{2}\right)\right\}(2-\cos\theta_1-\cos\theta_2). \end{aligned}

Hence,

fγ1,γ2(θ1,θ2)2−cos⁡θ1−cos⁡θ2≥min⁡{−2γ1(cos⁡γ1π2),−η2γ2(cos⁡γ2π2)}>0.\frac{f_{\gamma_1,\gamma_2}(\theta_1,\theta_2)}{2-\cos\theta_1-\cos\theta_2}\ge\min\left\{-2^{\gamma_1}\left(\cos\frac{\gamma_1\pi}{2}\right),-\eta2^{\gamma_2}\left(\cos\frac{\gamma_2\pi}{2}\right)\right\}>0.

Therefore,

min⁡(θ1,θ2)∈[−π,π]2(θ1,θ2)≠(0,0)fγ1,γ2(θ1,θ2)2−cos⁡θ1−cos⁡θ2>0.\min_{\substack{(\theta_1,\theta_2)\in[-\pi,\pi]^2\\(\theta_1,\theta_2)\ne(0,0)}}\frac{f_{\gamma_1,\gamma_2}(\theta_1,\theta_2)}{2-\cos\theta_1-\cos\theta_2}>0.

Owing to

lim⁡θ→0fγ(θ)−2cos⁡(θ2)∣θ∣=1\lim_{\theta\to0} \frac{f_\gamma(\theta)}{-2\cos\left(\frac{\theta}{2}\right)|\theta|}=1

and

lim⁡(θ1,θ2)→(0,0)θ12+θ222−cos⁡θ1−cos⁡θ2=2.\lim_{(\theta_1,\theta_2)\to(0,0)}\frac{\theta_1^2+\theta_2^2}{2-\cos\theta_1-\cos\theta_2}=2.

Then

lim⁡(θ1,θ2)→(0,0)fγ1,γ2(θ1,θ2)2−cos⁡θ1−cos⁡θ2=+∞.\lim_{(\theta_1,\theta_2)\to(0,0)}\frac{f_{\gamma_1,\gamma_2}(\theta_1,\theta_2)}{2-\cos\theta_1-\cos\theta_2}=+\infty.

Thus, the quotient cannot attain its infimum near the origin. Since it is continuous away from the origin, its infimum is attained on a compact subset of [−π,π]2∖{(0,0)}[-\pi,\pi]^2 \setminus\{(0,0)\}. Therefore, the infimum may equivalently be written as a minimum.

The Proof is completed.

Several properties obtained by applying positive diagonal matrix perturbations are presented below. If AA and BB are symmetric positive definite matrices, the notation A≤BA \le B means that B−AB-A is a nonnegative definite matrix.

Lemma 3.4. Let A=(aij)∈Rn×nA=(a_{ij})\in\mathbb{R}^{n\times n} be a symmetric positive definite matrix, and let B=A+DB=A+D, where DD is a nonnegative diagonal matrix. Then

ρ(diag⁡(B)−1B)≤ρ(diag⁡(A)−1A).(18)\rho\left(\operatorname{diag}(B)^{-1}B\right)\leq\rho\left(\operatorname{diag}(A)^{-1}A\right). \tag*{(18)}

Proof. We denote D0=diag⁡(A)D_0=\operatorname{diag}(A). Let

l=ρ(D0−1A)=λmax⁡(D0−12AD0−12).l=\rho(D_0^{-1}A)=\lambda_{\max}\left(D_0^{-\frac{1}{2}}AD_0^{-\frac{1}{2}}\right).

Since tr⁡(D0−12AD0−12)=n\operatorname{tr}\left(D_0^{-\frac{1}{2}}AD_0^{-\frac{1}{2}}\right)=n, we have l≥1l\geq1 and

D0−12AD0−12≤lIn,D_0^{-\frac{1}{2}}AD_0^{-\frac{1}{2}}\leq lI_n,

i.e.,

A≤lD0.(19)A\leq lD_0. \tag*{(19)}

Since D≥0D\geq0 and l≥1l\geq1, we have

D≤lD.(20)D\leq lD. \tag*{(20)}

Adding (19) and (20), we obtain

A+D≤l(D0+D).(21)A+D\leq l(D_0+D). \tag*{(21)}

Applying the congruence transformation induced by (D+D0)−12(D+D_0)^{-\frac{1}{2}} to both sides of the above inequality yields

(D+D0)−12(A+D)(D+D0)−12≤lIn.(D+D_0)^{-\frac{1}{2}}(A+D)(D+D_0)^{-\frac{1}{2}}\leq lI_n.

Taking the maximum eigenvalue on both sides of the above matrix inequality yields (18).

The proof is complete.

Lemma 3.5. Let A=(aij)∈Rn×nA=(a_{ij})\in\mathbb{R}^{n\times n} be a symmetric positive definite matrix, and there exists a constant β>0\beta>0 such that for any eh∈Rne^h\in\mathbb{R}^n,

min⁡eH∈Rnc∥eh−IHheH∥0,A2≤β∥eh∥1,A2.\min_{e^H\in\mathbb{R}^{n_c}}\left\|e^h-I_H^h e^H\right\|_{0,A}^2\leq\beta\left\|e^h\right\|_{1,A}^2.

Define B=A+DB=A+D, where D=(dij)∈Rn×nD=(d_{ij})\in\mathbb{R}^{n\times n} is a nonnegative diagonal matrix. Then for any eh∈Rne^h\in\mathbb{R}^n, we have

min⁡eH∈Rnc∥eh−IHheH∥0,B2≤β(1+dmax⁡amin⁡)∥eh∥1,B2.\min_{e^H\in\mathbb{R}^{n_c}}\left\|e^h-I_H^h e^H\right\|_{0,B}^2\leq\beta\left(1+\frac{d_{\max}}{a_{\min}}\right)\left\|e^h\right\|_{1,B}^2.

where dmax⁡=max⁡{d11,…,dnn}d_{\max}=\max\{d_{11},\ldots,d_{nn}\} and amin⁡=min⁡{a11,…,ann}a_{\min}=\min\{a_{11},\ldots,a_{nn}\}.

Proof. For any eh∈Rne^h\in\mathbb{R}^n and eH∈Rnce^H\in\mathbb{R}^{n_c}, we have

∥eh−IHheH∥0,B2=∥eh−IHheH∥0,A2+∥eh−IHheH∥0,D2≤(1+dmax⁡amin⁡)∥eh−IHheH∥0,A2.\left\|e^h-I_H^h e^H\right\|_{0,B}^2=\left\|e^h-I_H^h e^H\right\|_{0,A}^2+\left\|e^h-I_H^h e^H\right\|_{0,D}^2 \leq\left(1+\frac{d_{\max}}{a_{\min}}\right)\left\|e^h-I_H^h e^H\right\|_{0,A}^2.

Now, suppose that for a fixed eh∈Rne^h\in\mathbb{R}^n, eH(h)e^H(h) is chosen such that

min⁡eH∈Rnc∥eh−IHheH∥0,A2=∥eh−IHheH(h)∥0,A2.\min_{e^H\in\mathbb{R}^{n_c}}\left\|e^h-I_H^h e^H\right\|_{0,A}^2=\left\|e^h-I_H^h e^H(h)\right\|_{0,A}^2.

Then, for any eh∈Rne^h\in\mathbb{R}^n

min⁡eH∈Rnc∥eh−IHheH∥0,B2≤∥eh−IHheH(h)∥0,B2≤(1+dmax⁡amin⁡)∥eh−IHheH(h)∥0,A2≤(1+dmax⁡amin⁡)β∥eh∥1,A2≤(1+dmax⁡amin⁡)β∥eh∥1,B2.\begin{aligned} \min_{e^H\in\mathbb{R}^{n_c}}\left\|e^h-I_H^h e^H\right\|_{0,B}^2 &\leq\left\|e^h-I_H^h e^H(h)\right\|_{0,B}^2\\ &\leq\left(1+\frac{d_{\max}}{a_{\min}}\right)\left\|e^h-I_H^h e^H(h)\right\|_{0,A}^2\\ &\leq\left(1+\frac{d_{\max}}{a_{\min}}\right)\beta\left\|e^h\right\|_{1,A}^2\\ &\leq\left(1+\frac{d_{\max}}{a_{\min}}\right)\beta\left\|e^h\right\|_{1,B}^2. \end{aligned}

The proof is completed.

The convergence of the TGM for ANA_N has been analyzed previously. For the case d(x,y,t)≥0d(x,y,t)\geq0, although AN(m)A_N^{(m)} may no longer be a BTTB matrix, the coefficient matrix at each time level can be expressed as AN(m)=AN+1η1D(m)A_N^{(m)}=A_N+\frac{1}{\eta_1}D^{(m)}, and it follows from Lemma 3.4 that

Corollary 3.1. Let AN(m)A_N^{(m)} be given by (5). If the coefficient function d(x,y,t)d(x,y,t) is nonnegative and uniformly bounded, then there exists a constant α\alpha independent of the time mm such that the weighted Jacobi smoother GG satisfies (16).

Proof. Since 1η1D(m)\frac{1}{\eta_1}D^{(m)} is nonnegative for any 1≤m≤M1\leq m\leq M. By Lemma 3.4, we have

ρ(diag⁡(AN(m))−1AN(m))≤ρ(diag⁡(AN)−1AN).\rho\left(\operatorname{diag}\left(A_N^{(m)}\right)^{-1}A_N^{(m)}\right)\leq\rho\left(\operatorname{diag}\left(A_N\right)^{-1}A_N\right).

Moreover,

0<2a0∥fγ1,γ2∥∞≤2ρ(diag⁡(AN)−1AN)≤2ρ(diag⁡(AN(m))−1AN(m)),0<\frac{2a_0}{\left\|f_{\gamma_1,\gamma_2}\right\|_\infty}\leq\frac{2}{\rho\left(\operatorname{diag}\left(A_N\right)^{-1}A_N\right)}\leq\frac{2}{\rho\left(\operatorname{diag}\left(A_N^{(m)}\right)^{-1}A_N^{(m)}\right)},

and 2a0∥fγ1,γ2∥∞\frac{2a_0}{\left\|f_{\gamma_1,\gamma_2}\right\|_\infty} is independent of the time level mm, there always exists an α\alpha independent of mm such that (16) holds. The Proof is completed.

Corollary 3.2. Under the conditions of Corollary 3.1, there exists a constant β\beta independent of the time mm such that the prolongation operator defined by (11) satisfies (17).

Proof. By Theorem 3.2, there exists a positive constant β0\beta_0, such that

min⁡eH∈Rnc∥eh−IHheH∥0,AN2≤β0∥eh∥1,AN2,∀eh∈Rn.\min_{e^H\in\mathbb{R}^{n_c}}\left\|e^h-I_H^h e^H\right\|_{0,A_N}^2\leq\beta_0\left\|e^h\right\|_{1,A_N}^2,\quad\forall e^h\in\mathbb{R}^n.

By the uniform boundedness of d(x,y,t)d(x,y,t), there exists a positive constant d^\hat{d} such that

d(x,y,t)≤d^for all (x,y,t)∈Ω×(0,T).d(x,y,t)\leq\hat{d}\quad\text{for all }(x,y,t)\in\Omega\times(0,T).

It follows from Lemma 3.5 that

min⁡eH∈Rnc∥eh−IHheH∥0,AN(m)2≤β0(1+d^η1a0)∥eh∥1,AN(m)2,∀eh∈Rn.\min_{e^H\in\mathbb{R}^{n_c}}\left\|e^h-I_H^h e^H\right\|_{0,A_N^{(m)}}^2\leq\beta_0\left(1+\frac{\hat{d}}{\eta_1a_0}\right)\left\|e^h\right\|_{1,A_N^{(m)}}^2,\quad\forall e^h\in\mathbb{R}^n.

Let β=β0(1+d^η1a0)\beta=\beta_0\left(1+\frac{\hat{d}}{\eta_1a_0}\right). Then β\beta does not depend on the time instant mm. The proof is completed.

Theorem 3.3. Let AN(m)A_N^{(m)} be given by (5). If the coefficient function d(x,y,t)d(x,y,t) is nonnegative and uniformly bounded, GG is the weighted Jacobi method with ω∈(0,2a0∥fγ1,γ2∥∞)\omega\in\left(0,\frac{2a_0}{\left\|f_{\gamma_1,\gamma_2}\right\|_\infty}\right), and IHhI_H^h is as in (11), then the TGM method converges.

Corollary 3.3. Under the conditions of Theorem 3.3, ω∈(0,1]\omega\in(0,1] serves as a sufficient condition for the convergence of the TGM with weighted Jacobi as the smoother when solving (5).

Proof. We only need to prove that

2a0∥fγ1,γ2∥∞>1\frac{2a_0}{\left\|f_{\gamma_1,\gamma_2}\right\|_\infty}>1

for any (γ1,γ2)∈(1,2)(\gamma_1,\gamma_2)\in(1,2). A direct calculation gives

2a0∥fγ1,γ2∥∞=−4g1(γ1)−4η2η1g1(γ2)∥fγ1(θ1)+η2η1fγ2(θ2)∥∞=4γ1+4η2η1γ22γ1+1+η2η12γ2+1>1.\frac{2a_0}{\left\|f_{\gamma_1,\gamma_2}\right\|_\infty} =\frac{-4g_1^{(\gamma_1)}-4\frac{\eta_2}{\eta_1}g_1^{(\gamma_2)}}{\left\|f_{\gamma_1}(\theta_1)+\frac{\eta_2}{\eta_1}f_{\gamma_2}(\theta_2)\right\|_\infty} =\frac{4\gamma_1+4\frac{\eta_2}{\eta_1}\gamma_2}{2^{\gamma_1+1}+\frac{\eta_2}{\eta_1}2^{\gamma_2+1}}>1.

The Proof is completed.

The above corollary indicates that regardless of how the conditions of equation (1) vary, as long as the relaxation parameter ω∈(0,1]\omega\in(0,1], the TGM is always convergent, which provides a conservative but safe interval for parameter selection. Furthermore, the surface of 2a0∥fγ1,γ2∥∞\frac{2a_0}{\left\|f_{\gamma_1,\gamma_2}\right\|_\infty} corresponding to different values of (γ1,γ2)(\gamma_1,\gamma_2) when N=64N=64 is shown in Figure 1. It can be observed that the surface representing the values of 2a0∥fγ1,γ2∥∞\frac{2a_0}{\left\|f_{\gamma_1,\gamma_2}\right\|_\infty} lies strictly above the light blue plane, and 2a0∥fγ1,γ2∥∞\frac{2a_0}{\left\|f_{\gamma_1,\gamma_2}\right\|_\infty} achieves an approximate maximum value of 1.0615 when (γ1,γ2)=(1.445,1.445)(\gamma_1,\gamma_2)=(1.445,1.445). In the following, we use an example to show that the choice of ω\omega will significantly affect the iteration efficiency of the TGM.

The range of $\frac{2a_0}{\lVert f_{\gamma_1,\gamma_2}\rVert_\infty}$ when $N=64$

Figure 1. The range of 2a0∥fγ1,γ2∥∞\frac{2a_0}{\lVert f_{\gamma_1,\gamma_2}\rVert_\infty} when N=64N=64.

Example 3.1. Consider a two-dimensional Riesz space fractional diffusion equation with T=1T=1 and Ω=(0,1)2\Omega=(0,1)^2. The exact solution is taken as

u=e−t(x−x2)2(y−y2)2,u=e^{-t}(x-x^2)^2(y-y^2)^2,

and the source term ff is derived from the exact solution. Take γ1=1.1\gamma_1=1.1, γ2=1.7\gamma_2=1.7, N=64N=64, M=4M=4, and consider the linear system at the first time level. We apply the TGM to solve the linear system obtained from discretization, terminate the iteration when

∥Au−b∥∞∥b∥∞<10−7,\frac{\lVert Au-b\rVert_\infty}{\lVert b\rVert_\infty}<10^{-7},

and count the number of cycles. Specifically,

(1): The d(x,y,t)=0d(x,y,t)=0: We set ω=0.0001\omega=0.0001 as the initial value and traverse to ω=1.1\omega=1.1 with a step size of 0.0001. Denoting one TGM iteration as one cycle, we record the cycle counts required to reach the stopping tolerance for different values of ω\omega, and plot the corresponding iteration curve, namely Figure 2a. A direct calculation gives

The relationship between $\omega$ and the cycle counts; the iterative behavior near $\omega = 1.0417$

Figure 2. (a) The relationship between ω\omega and the cycle counts \quad (b) The iterative behavior near ω=1.0417\omega= 1.0417

Figure 2: The iteration curves of the TGM for d(x,y,t)=0d(x,y,t)=0.

2a0∥fγ1,γ2∥∞≈1.0417,\frac{2a_0}{\lVert f_{\gamma_1,\gamma_2}\rVert_\infty}\approx1.0417,

which is marked by a red line in Figure 2a.

As can be seen from Figure 2a, the choice of the relaxation parameter ω\omega significantly affects the iteration efficiency of the TGM. For example, when ω=0.9335\omega=0.9335, the required number of cycles is the smallest, only 25; whereas in other regions, the corresponding cycle counts increase markedly, even exceeding 100. In addition, all values of ω\omega to the left of the red line ensure the convergence of the TGM, which verifies the effectiveness of Theorem 3.1.

Figure 2b shows the steep growth phenomenon near ω=1.0417\omega=1.0417: when ω=1.04\omega=1.04, the number of cycles required to reach the convergence tolerance is 795; when ω=1.0417\omega=1.0417, the required number of cycles increases sharply to 3043; and when ω=1.042\omega=1.042, the TGM still fails to converge after more than 5000 iterations. These phenomena indicate that the choice of ω\omega has a great influence on both the convergence and the convergence speed of the TGM, so selecting an appropriate ω\omega is necessary for accelerating convergence.

(2): d(x,y,t)=(1+x)7(1+y)7d(x,y,t)=(1+x)^7(1+y)^7: Similar to the results obtained in (1), Figure 3a shows a sweep of the number of cycles required to reach convergence accuracy under different values of ω\omega. It can be seen that the number of iterations is minimized at ω=0.9231\omega=0.9231, requiring only 14 cycles. In Figure 2b, the parameters to the right of ω=1.0417\omega=1.0417 basically make the number of iterations required by TGM exceed 5000, whereas in Figure 3b, the parameters to the left of ω=1.0513\omega=1.0513 all allow TGM to converge. It can be seen that the boundary parameter that ensures the smoothing property is shifted noticeably to the right, which verifies the validity of Corollary 3.1. In addition, when ω=1.0512\omega= 1.0512, the required number of cycles is 1298, while when ω=1.0513\omega= 1.0513, the iteration still fails to converge after more than 5000 steps. This steep growth phenomenon is far more pronounced than in the case of d(x,y,t)=0d(x,y,t)=0, reflecting that the parameter variation is more complicated when d(x,y,t)≥0d(x,y,t) \ge0.

The relationship between $\omega$ and the cycle counts; the iterative behavior near $\omega = 1.0417$

Figure 3. (a) The relationship between ω\omega and the cycle counts \quad (b) The iterative behavior near ω=1.0417\omega= 1.0417

Figure 3: The iteration curves of the TGM for d(x,y,t)=(1+x)7(1+y)7d(x,y,t)=(1+x)^7(1+y)^7.

Data-driven acceleration strategy

As the discretization number NN increases, the discretization of the partial differential equation yields a family of matrices. When solving with parameterized iterative methods, there exists an optimal parameter for each problem size, which can be obtained via fine step grid search and corresponds to the minimal computational cost. As NN continues to grow, properties such as the matrix spectrum change, and these optimal parameters usually fluctuate. Such fluctuations generally exhibit nonlinear characteristics and cannot be characterized by rigorous mathematical expressions, determining them via exact eigenvalue computations incurs a high computational cost[29].

Gaussian process regression (GPR) provides an effective data-driven strategy for learning such parameters: it uses kernel functions to model the varying relationship between problem sizes and quasi-optimal parameters, and predicts near-optimal parameters at a low computational cost. Assume that we have a training set containing dd data:

D={(Ni,ωi)∣i=1,2,…,d}=:{N,ω},\mathcal{D}=\{(N_i,\omega_i)|i=1,2,\ldots,d\}=:\{\mathbf{N},\boldsymbol{\omega}\},

where the pair (Ni,ωi)(N_i,\omega_i) denotes the NiN_i-th mesh partition number and the corresponding optimal relaxation parameter. The goal of Gaussian process regression is to establish a mapping between the input set N\mathbf{N} and the output set ω\boldsymbol{\omega}, represented as F(N):R→R\mathcal{F}(\mathbf{N}):\mathbb{R}\to\mathbb{R}, and to forecast the potential output value ω~∗=F(N∗)\tilde{\omega}_*=\mathcal{F}(N_*) at a new test point N∗N_*. In practical linear regression scenarios, we model the observed value ω\omega as the result of a latent function F(N)\mathcal{F}(\mathbf{N}) perturbed by additive noise ξ\xi, i.e.,

ω=F(N)+ξ.(22)\omega=\mathcal{F}(\mathbf{N})+\xi. \tag*{(22)}

Suppose that ξ\xi follows a Gaussian distribution with a zero mean and variance σ2\sigma^2, that is ξ∼N(0,σ2)\xi\sim\mathcal{N}(0,\sigma^2). The common range for σ\sigma is [10−6,10−2][10^{-6},10^{-2}]. For this investigation, we have set σ=10−4\sigma=10^{-4}. Without loss of generality, assume true function F(N)\mathcal{F}(\mathbf{N}) follows a zero mean Gaussian process:

[F(N1)⋮F(Nd)]∼N([0⋮0],[κ(N1,N1)⋯κ(N1,Nd)⋮⋱⋮κ(Nd,N1)⋯κ(Nd,Nd)]),\begin{bmatrix} \mathcal{F}(N_1)\\ \vdots\\ \mathcal{F}(N_d) \end{bmatrix} \sim\mathcal{N}\left( \begin{bmatrix} 0\\ \vdots\\ 0 \end{bmatrix}, \begin{bmatrix} \kappa(N_1,N_1)&\cdots&\kappa(N_1,N_d)\\ \vdots&\ddots&\vdots\\ \kappa(N_d,N_1)&\cdots&\kappa(N_d,N_d) \end{bmatrix} \right),

where κ(Ni,Nj)\kappa(N_i,N_j) defines the covariance between the function values corresponding to the input points NiN_i and NjN_j. The kernel function plays a pivotal role in GPR, as it is responsible for generating the covariance matrix that quantifies the similarity between any two input variables. The closer the distance between inputs, the higher the correlation between their corresponding output variables. Hence, it is essential to select or construct kernel functions that meet the specific demands of the problem at hand. In this paper, we consider the Gaussian kernel function, which is given by

κ(Ni,Nj)=δF2exp⁡(−∥Ni−Nj∥222δL2),\kappa(N_i,N_j)=\delta_{\mathcal{F}}^2\exp\left(-\frac{\lVert N_i-N_j\rVert_2^2}{2\delta_{\mathcal{L}}^2}\right),

where δF\delta_{\mathcal{F}}, δL\delta_{\mathcal{L}} are hyperparameters,and the specific calculation of the hyperparameters is given in [14]. Define K(N,N)=(κ(Ni,Nj))∈Rd×dK(\mathbf{N},\mathbf{N})=(\kappa(N_i,N_j))\in\mathbb{R}^{d\times d}. Then, we can express the prior distribution of the observed values ω\boldsymbol{\omega} as

ω∼N(0,K(N,N)+δ2Id).(23)\boldsymbol{\omega}\sim\mathcal{N}\left(0,K(\mathbf{N},\mathbf{N})+\delta^2 I_d\right). \tag*{(23)}

The joint prior distribution of the observed value ω\boldsymbol{\omega} and the predicted value ω∗\omega_* is given by

\begin{bmatrix} \boldsymbol{\omega}\\ \omega_* \end{bmatrix} \sim\mathcal{N}\left( \begin{bmatrix} 0\\ 0 \end{bmatrix}, \begin{bmatrix} K(\mathbf{N},\mathbf{N})+\delta^2 I_d&K(\mathbf{N},N_*)\\ K(N_*,\mathbf{N})&K(N_*,N_*) \end{bmatrix} \right). \tag*{(24)}\end{bmatrix}

Then the conditional expectation and variance of F(n)\mathcal{F}(n) is given by

E[F(N)∣ω]=K(N∗,N)[K(N,N)+δ2Id]−1ω,(25)\mathbb{E}[\mathcal{F}(N)|\boldsymbol{\omega}]=K(N_*,\mathbf{N})\left[K(\mathbf{N},\mathbf{N})+\delta^2 I_d\right]^{-1}\boldsymbol{\omega}, \tag*{(25)}
Var[F(N)∣ω]=K(N∗,N∗)−K(N∗,N)[K(N,N)+δ2Id]−1K(N,N∗).(26)\mathop{\mathrm{Var}}[\mathcal{F}(N)|\boldsymbol{\omega}]=K(N_*,N_*)-K(N_*,\mathbf{N})\left[K(\mathbf{N},\mathbf{N})+\delta^2 I_d\right]^{-1}K(\mathbf{N},N_*). \tag*{(26)}

For the output ω∗\omega_* in the test set, we use the mean of the Gaussian regression as its estimate, i.e. ω^∗=E[F(N)∣ω]\widehat{\omega}_*=\mathbb{E}[\mathcal{F}(N)|\boldsymbol{\omega}].

Numerical experiments

In Section 3, we discuss the convergence of the TGM. The TGM contains only one coarse level. When the size of the original matrix is too large, the order of the coarse matrix obtained by projection may still be high, and it remains difficult to solve the coarse-grid equation exactly. A natural approach to resolve this difficulty is to recursively apply the TGM on this coarse level to generate coarser levels successively, until the order of the coarsest level is sufficiently small. Except for the coarsest level, each of the remaining grid levels performs only one such recursive procedure, which yields the V-cycle of the multigrid method[24, 27, 32].

V-cycle sketch map

Figure 4. V-cycle sketch map

In this section, we present several numerical experiments to demonstrate the computational efficiency of the multigrid method and verify the acceleration effect of using GPR-predicted parameters on the multigrid solver. Specifically, we set the order of the matrix on the coarsest level of the multigrid method to be no more than 1000. Except for the coarsest level, one weighted Jacobi iteration is applied for pre-smoothing and post-smoothing on all remaining grid levels, and the same input relaxation parameter is used for all weighted Jacobi iterations. In the experiments, we consider three test cases for comparison: the multigrid method with ω=1\omega= 1 as the relaxation parameter, the multigrid method using GPR-predicted values as the relaxation parameter, and the unpreconditioned conjugate gradient method.

The training strategy of GPR is as follows: starting from N=5N = 5 with a step size of 5 up to N=50N = 50, we construct a training set consisting of 10 samples. For each problem size, the quasi-optimal parameter ω\omega is obtained via grid search over the interval [0.001,1][0.001, 1] with a step size of 0.001. For all algorithms, the zero vector is used as the initial iterate, with the stopping criterion

RRES=∥Au−b∥∞∥b∥∞≤10−7.\mathrm{RRES} = \frac{\lVert Au - b \rVert_{\infty}}{\lVert b \rVert_{\infty}} \leq10^{-7}.

All experiments are carried out using MATLAB (version R2025b) on a laptop equipped with an Intel Core i5-9300H CPU (4 cores, 2.40 GHz) and 8 GB of memory.

Example 5.1. Consider the two-dimensional Riesz space fractional diffusion equation (1) defined on the domain (0,1)×(0,1)×(0,1)(0, 1) \times(0, 1) \times(0, 1). The exact solution is given by u(x,y,t)=2(t3+0.01)xy(1−x)(1−y)u(x, y, t) = 2(t^3 + 0.01)xy(1 - x)(1 - y), and the initial condition is u0(x,y)=0.02xy(1−x)(1−y)u_0(x, y) = 0.02xy(1 - x)(1 - y). We take d(x,y,t)=ln⁡(1+x)(y+1)2d(x, y, t) = \ln(1 + x)(y + 1)^2. The source term ff is derived from the exact solution.

It can be seen that the GPR parameter selection strategy is significantly superior to the Default strategy in most cases. For example, in Table 2 for (γ1,γ2)=(1.4,1.4)(\gamma_1,\gamma_2)=(1.4,1.4) and N=512N=512, Default requires 18 iterations and 20.7812 s, whereas GPR requires only 14 iterations and 15.3594 s; in Table 2 for (γ1,γ2)=(1.8,1.8)(\gamma_1,\gamma_2)=(1.8,1.8) and N=512N=512, Default requires 18 iterations and 20.4062 s, whereas GPR requires only 14 iterations and 15.9375 s. As NN increases, the iteration counts of GPR remain basically in the range of 13–31, exhibiting a favorable mesh-independent convergence trend; although the iteration counts of Default decrease with increasing NN in some test cases, they are still overall higher than those of GPR. The iteration counts and CPU times of CG grow fastest with NN; at N=512N=512, CG usually requires hundreds of iterations and hundreds of seconds of CPU time, which is far higher than those of the two multigrid methods. For a few parameter combinations, the CPU times of Default and GPR are already relatively close. However, over all test cases, the relaxation parameters predicted by GPR can effectively reduce both the iteration counts and the computing time.

(γ1,γ2)(\gamma_1,\gamma_2)MethodIndexN=64N=64N=128N=128N=256N=256N=512N=512
(1.4,1.4)(1.4,1.4)DefaultIT27211918
CPU0.17101.07813.796920.7812
GPRIT13141414
CPU0.06250.35962.187515.3594
CGIT97161278447
CPU0.29692.312532.7656440.1875
(1.5,1.6)(1.5,1.6)DefaultIT30242017
CPU0.26561.15623.578121.0781
GPRIT16171819
CPU0.10940.51562.821221.6406
CGIT111199345585
CPU0.18752.594042.6407552.3438
(1.7,1.9)(1.7,1.9)DefaultIT72604433
CPU0.39062.04697.265639.1406
GPRIT23263031
CPU0.09380.81254.397537.4217
CGIT1553035671072
CPU0.28123.796967.34381067.7187

Table 2. Example 5.1

Example 5.2. Consider the two-dimensional Riesz space fractional diffusion equation (1) defined on the domain (0,1)×(0,1)×(0,1)(0,1)\times(0,1)\times(0,1). The exact solution is given by u(x,y,t)=e−2tsin⁡(πx)sin⁡(πy)u(x,y,t)=e^{-2t}\sin(\pi x)\sin(\pi y), and the initial condition is u0(x,y)=sin⁡(πx)sin⁡(πy)u_0(x,y)=\sin(\pi x)\sin(\pi y). We take d(x,y,t)=10−6d(x,y,t)=10^{-6}. The source term ff is derived from the exact solution.

(γ1,γ2)(\gamma_1,\gamma_2)MethodIndexN=64N=64N=128N=128N=256N=256N=512N=512
(1.2,1.2)(1.2,1.2)DefaultIT39292221
CPU0.18751.28124.046923.8595
GPRIT13141414
CPU0.07810.53122.890617.0781
CGIT71117189302
CPU0.20311.390622.8125397.6406
(1.5,1.5)(1.5,1.5)DefaultIT30241716
CPU0.32811.06253.218818.4712
GPRIT13131314
CPU0.14060.31252.421916.5000
CGIT72125215369
CPU0.14061.546924.6250419.6719
(1.8,1.8)(1.8,1.8)DefaultIT59493418
CPU0.29701.75006.093820.4062
GPRIT14141414
CPU0.07810.39062.703115.9375
CGIT83161302568
CPU0.20312.140636.0000688.1875

Table 3. Example 5.2

It can be seen that the GPR parameter selection strategy is overall significantly superior to Default. For example, for (γ1,γ2)=(1.2,1.2)(\gamma_1,\gamma_2)=(1.2,1.2) and N=512N=512, Default requires 21 iterations and 23.8595 s, whereas GPR requires only 14 iterations and 17.0781 s; for (γ1,γ2)=(1.8,1.8)(\gamma_1,\gamma_2)=(1.8,1.8) and N=512N=512, Default requires 18 iterations and 20.4062 s, whereas GPR requires only 14 iterations and 15.9375 s. As NN increases, the iteration counts of GPR remain basically stable at 13–14, exhibiting a favorable mesh-independent convergence trend; although the iteration counts of Default also decrease with increasing NN, they are still overall higher than those of GPR, and the gap is particularly evident at N=64N=64 and N=128N=128. The iteration counts and CPU times of CG grow fastest with NN; at N=512N=512, CG usually requires hundreds of iterations and hundreds of seconds of CPU time. For instance, for (γ1,γ2)=(1.8,1.8)(\gamma_1,\gamma_2)=(1.8,1.8), CG requires 568 iterations and 688.1875 s, which is far higher than those of the two multigrid methods. For a few parameter combinations (such as (γ1,γ2)=(1.5,1.5)(\gamma_1,\gamma_2)=(1.5,1.5) and N=512N=512), the CPU times of Default and GPR are already relatively close, but GPR is still no worse than Default. Over all test cases, the relaxation parameters predicted by GPR can effectively reduce both the iteration counts and the computing time, further verifying the effectiveness and superiority of the data-driven parameter selection strategy for accelerating the multigrid method.

Conclusion

In this paper, the weighted Jacobi method is adopted as the smoother in a multigrid method for solving the two-dimensional Riesz space fractional diffusion equation. To address the problem of relaxation parameter selection, a GPR-based parameter selection strategy is proposed. Numerical experiments verify the correctness of the relevant theory and confirm the high computational efficiency of this data-driven algorithm. Moreover, the combination of neural networks and traditional numerical methods has become increasingly important in recent years. In fact, neural networks exhibit spectral bias, which makes them naturally complementary to multigrid methods. As a result, a growing number of researchers have combined the two and obtained many important results. Nevertheless, reliable mathematical explanations for these works remain lacking. In our subsequent work, we will provide corresponding analysis and design more efficient and robust algorithms.

Data availability: No data was used for the research described in the article.

Acknowledgements: The authors are thankful to the editors and the anonymous referees for their valuable comments to improve the paper.

Funding: This work was supported by the National Natural Science Foundation of China (12671450), the National Key Research and Development Program of China (2023YFB3001604), and the Graduate Research Innovation Project of Xiangtan University (XDCX2026Y276).

References

  1. [1]Agrawal OP (2004) A general formulation and solution scheme for fractional optimal control problems. Nonlinear Dyn 38:323–337DOI
  2. [2]Ahmad D, Donatelli M, Mazza M, Serra-Capizzano S, Trotti K (2024) A note on the convergence of multigrid methods for the Riesz-space equation and an application to image deblurring. Mathematics 12(12):1916
  3. [3]Ahmad D, Donatelli M, Mazza M, Serra-Capizzano S, Trotti K (2025) A smoothing analysis for multigrid methods applied to tempered fractional problems. Linear Multilinear Algebra 73(9):1862–1885
  4. [4]Bai J, Feng XC (2007) Fractional-order anisotropic diffusion for image denoising. IEEE Trans Image Process 16:2492–2502pubmed.ncbi.nlm.nih.gov/17926931
  5. [5]Bai Z-Z, Lu K-Y, Pan J-Y (2017) Diagonal and Toeplitz splitting iteration methods for diagonal-plus-Toeplitz linear systems from spatial fractional diffusion equations. Numer Linear Algebra Appl 24(4):e2093DOI
  6. [6]Benedusi P, Ferrari P, Causemann M, Serra-Capizzano S (2026) Dense cell-by-cell systems of PDEs: approximation, spectral analysis, and preconditioning. BIT Numer Math 66(3):53
  7. [7]Bolten M, Donatelli M, Ferrari P, Furci I (2022) A symbol-based analysis for multigrid methods for block-circulant and block-Toeplitz systems. SIAM J Matrix Anal Appl 43(1):405–438arxiv.org/abs/2101.06434
  8. [8]Bolten M, Donatelli M, Ferrari P, Furci I (2025) Analysis on aggregation and block smoothers in multigrid methods for block Toeplitz linear systems. SIAM J Matrix Anal Appl 46(2):1416–1443arxiv.org/abs/2403.02139
  9. [9]Donatelli M, Mazza M, Serra-Capizzano S (2016) Spectral analysis and structure preserving preconditioners for fractional diffusion equations. J Comput Phys 307:262–279DOI
  10. [10]Du N, Wang H, Liu W (2016) A fast gradient projection method for a constrained fractional optimal control. J Sci Comput 68(1):1–20DOI
  11. [11]Huang R, Li R, Xi Y (2023) Learning optimal multigrid smoothers via neural networks. SIAM J Sci Comput 45(3):S199–S225arxiv.org/abs/2102.12071
  12. [12]Hocking LR, Greif C (2021) Optimal complex relaxation parameters in multigrid for complex-shifted linear systems. SIAM J Matrix Anal Appl 42(2):475–502DOI
  13. [13]He Y, MacLachlan S (2020) Two-level Fourier analysis of multigrid for higher-order finite-element discretizations of the Laplacian. Numer Linear Algebra Appl 27(3):e2285
  14. [14]Jiang K, Su X, Zhang J (2022) A general alternating-direction implicit framework with Gaussian process regression parameter prediction for large sparse linear systems. SIAM J Sci Comput 44(4):A1960–A1988
  15. [15]Lin X-L, Ng MK, Sun H-W (2017) A multigrid method for linear systems arising from time-dependent two-dimensional space-fractional diffusion equations. J Comput Phys 336:69–86
  16. [16]Lu X, Fang Z-W, Sun H-W (2021) Splitting preconditioning based on sine transform for time-dependent Riesz space fractional diffusion equations. J Appl Math Comput 66:673–700
  17. [17]Meerschaert MM, Scalas E (2006) Coupled continuous time random walks in finance. Physica A 370(1):114–118
  18. [18]Meerschaert MM, Scheffler H-P, Tadjeran C (2006) Finite difference methods for two-dimensional fractional dispersion equation. J Comput Phys 211(1):249–261
  19. [19]Meerschaert MM, Tadjeran C (2004) Finite difference approximations for fractional advection–dispersion flow equations. J Comput Appl Math 172(1):65–77
  20. [20]Moghaderi H, Dehghan M, Donatelli M, Mazza M (2017) Spectral analysis and multigrid preconditioners for two-dimensional space-fractional diffusion equations. J Comput Phys 350:992–1011
  21. [21]Pang HK, Sun HW (2012) Multigrid method for fractional diffusion equations. J Comput Phys 231(2):693–703
  22. [22]Pang HK, Sun HW (2016) Fast numerical contour integral method for fractional diffusion equations. J Sci Comput 66(1):41–66
  23. [23]Pougkakiotis S, Pearson JW, Leveque S, Gondzio J (2020) Fast solution methods for convex quadratic optimization of fractional differential equations. SIAM J Matrix Anal Appl 41(3):1443–1476
  24. [24]Ruge JW, Stüben K (1987) Algebraic multigrid. In: McCormick SF (ed) Multigrid methods. SIAM, Philadelphia, pp 73–130
  25. [25]Serra-Capizzano S, Sormani RL, Tablino-Possio C (2024) Two-dimensional semi-linear Riesz space fractional diffusion equations in convex domains: GLT spectral analysis and multigrid solvers. In: Lirkov I, Margenov S (eds) Large-scale scientific computations. Lecture notes in computer science, vol 14073. Springer, Cham, pp 52–60
  26. [26]She Z-H, Wen Y-Q, Qiu Y-F, Gu X-M (2024) Unconditionally convergent τ splitting iterative methods for variable coefficient Riesz space fractional diffusion equations. Appl Math Lett 158:109252
  27. [27]Stüben K (2001) A review of algebraic multigrid. In: Brezinski C, Wuytack L (eds) Numerical analysis: historical developments in the 20th century. Elsevier, Amsterdam, pp 331–359
  28. [28]Sun HW, Jin XQ, Chang QS (2001) Convergence of the multigrid method of ill-conditioned block Toeplitz systems. BIT Numer Math 41(1):179–190
  29. [29]Sun T, Zhang J (2026) Error analysis of parameter prediction via Gaussian process regression and its application to weighted Jacobi iteration. Comput Appl Math 45(8):339
  30. [30]Trottenberg U, Oosterlee CW, Schuller A (2001) Multigrid. Academic Press, San Diego
  31. [31]Xing Y, Liu Y, Xue T, Lu L (2026) GMT: a geometric multigrid transformer solver for microstructure homogenization. ACM Trans Graph 45(4):1–15
  32. [32]Xu J, Zikatanov L (2017) Algebraic multigrid methods. Acta Numer 26:591–721arxiv.org/abs/1611.01917
  33. [33]Zhang E, Kahana A, Kopaničáková A, Turkel E, Ranade R, Pathak J, Karniadakis GE (2024) Blending neural operators and relaxation methods in PDE numerical solvers. Nat Mach Intell 6(11):1303–1313arxiv.org/abs/2208.13273

Paper details

vlnc:W_bapqj6uc
v1 · latestHistory (1)

published · Fresh — added to the Hub within the last 30 days

added ·

Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Mathematics

Not recorded for this paper · View statement →

Looking for related papers…
Contents