FOURIER NEURAL SOLVER FOR LARGE SPARSE LINEAR ALGEBRAIC SYSTEMS Chen Cui1 Kai Jiang1 Yun Liu1and Shi Shuy1

2025-04-27 0 0 6.92MB 15 页 10玖币

侵权投诉

FOURIER NEURAL SOLVER FOR LARGE SPARSE LINEAR

ALGEBRAIC SYSTEMS

Chen Cui1, Kai Jiang∗1, Yun Liu1and Shi Shu†1

1Hunan Key Laboratory for Computation and Simulation in Science and Engineering, Key Laboratory of Intelligent

Computing and Information Processing of Ministry of Education, School of Mathematics and Computational Science,

Xiangtan University, Xiangtan, Hunan, China, 411105.

October 11, 2022

ABSTRACT

Large sparse linear algebraic systems can be found in a variety of scientiﬁc and engineering ﬁelds,

and many scientists strive to solve them in an efﬁcient and robust manner. In this paper, we propose

an interpretable neural solver, the Fourier Neural Solver (FNS), to address them. FNS is based on

deep learning and Fast Fourier transform. Because the error between the iterative solution and the

ground truth involves a wide range of frequency modes, FNS combines a stationary iterative method

and frequency space correction to eliminate different components of the error. Local Fourier analysis

reveals that the FNS can pick up on the error components in frequency space that are challenging

to eliminate with stationary methods. Numerical experiments on the anisotropy diffusion equation,

convection-diffusion equation, and Helmholtz equation show that FNS is more efﬁcient and more

robust than the state-of-the-art neural solver.

Keywords

Fourier neural solver; Fast Fourier Transform; local Fourier analysis; convection-diffusion-reaction equation.

1 Introduction

Large sparse linear algebraic systems are ubiquitous in scientiﬁc and engineering computation, such as discretization of

partial differential equations (PDE) and linearization of nonlinear problems. Designing efﬁcient, robust, and adaptive

numerical methods for solving them is a long-term challenge. Iterative methods are an effective way to resolve this

issue. They can be classiﬁed into single-level and multi-level methods. There are two types of single-level methods:

stationary and non-stationary methods [

]. Due to the sluggish convergence, stationary methods such as weighted

Jacobi, Gauss-Seidel, successive over relaxation methods [

] are frequently utilized as smoothers in multi-level methods

or as preconditioners. Non-stationary methods typically refer to Krylov subspace methods, such as conjugate gradient

(CG), generalized minimal residual (GMRES) methods [

], whose convergence rate will be inﬂuenced heavily by

some factors like initial value. Multi-level methods mainly include geometric multigrid (GMG) method [

] and

algebraic multigrid (AMG) method [

]. They are both composed of many factors, such as smoother and coarse

grid correction, which heavily affect convergence. Finding these factors for a concrete problem is an art that demands

extensive analysis, innovation, and trial.

In recent years, the technique of automatically picking parameters for Krylov and multi-level methods or constructing a

learnable iterative scheme based on deep learning has attracted a lot of interest. For second-order elliptic equations with

smooth coefﬁcients, many neural solvers have achieved satisfactory results. Hsieh et al. [

] utilized a convolutional

neural network (CNN) to accelerate the convergence of Jacobi method. Luna et al. [

] accelerated the convergence of

GMRES with a learned initial value. Signiﬁcant efforts are also made in the development of multigrid solvers, such as

learning smoother, transfer operator [

] and coarse-ﬁne splitting [

]. For anisotropy elliptic equations, Huang

∗kaijiang@xtu.edu.cn

†shushi@xtu.edu.cn

arXiv:2210.03881v1 [math.NA] 8 Oct 2022

Fourier Neural Solver for large sparse linear algebraic systems

et al. [

] exploited a CNN to design a more sensible smoother. Results showed that the magnitude of the learned

smoother is dispersed along the anisotropic direction. Wang et al. [

] introduced a learning-based local weighted least

square method for the AMG interpolation operator, and applied it to random diffusion equations and one-dimensional

small wavenumber Helmholtz equations. Fanaskov [

] learned the smoother and transfer operator of GMG in a

neural network form. When the anisotropic strength is mild (within two orders of magnitude), previously mentioned

works exhibit a considerable acceleration. Chen et al. [

] proposed the Meta-MgNet to learn a basis vector of Krylov

subspace as the smoother of GMG for strong anisotropic cases. However, the convergence rate is still sensitive to the

anisotropic strength. For convection-diffusion equations, Katrutsa et al. [

] learned the weighted Jacobi smoother and

transfer operator of GMG, which has a positive effect on the upwind discretazation system and also applied to solve a

one-dimensional Helmholtz equation. For second-order elliptic equations with random diffusion coefﬁcients, Greenfeld

et al. [

] employed a residual network to construct the prolongation operator of AMG for uniform grids. Luz et al. [

]

extended it to non-uniform grids using graph neural networks, which outperforms classical AMG methods. For jumping

coefﬁcient problems, Antonietti et al. [

] presented a neural network to forecast the strong connection parameter to

speed up AMG and used it as a preconditioner for CG. For Helmholtz equation, Stanziola et al. [

] constructed a

fully learnable neural solver, the helmnet, which is built on U-net and recurrent neural network [

]. Azulay et al. [

]

developed a preconditioner based on U-net and shift-Laplacian MG [

] and applied the ﬂexible GMRES [

] to solve

the discrete system. For solid and ﬂuid mechanics equations, there are also some neural solvers on associated discrete

systems, such as but not limited to, learning initial values [

], constructing preconditioners [

], learning search

directions of CG [31], learning parameters of GMG [32, 33].

In this paper, we propose the Fourier Neural Solver (FNS), a deep learning and Fast Fourier Transform (FFT) [

]

based neural solver. FNS is made up of two modules: the stationary method and the frequency space correction. Since

stationary methods like weighted Jacobi method are difﬁcult to get rid of low-frequency error, FNS uses FFT and CNN

to learn these modes in the frequency space. Local Fourier analysis (LFA) [

] reveals that FNS can pick up on the

error components in frequency space that are challenging to eradicate by stationary methods. Therefore, FNS builds a

complementary relationship by stationary method and CNN to eliminate error. With the help of FFT, the single-step

iteration of FNS has a

O(Nlog2N)

computational complexity. All matrix-vector products are implemented using

convolution, which is both storage-efﬁcient and straightforward to parallelize. We investigate the effectiveness and

robustness of FNS on three types of convection-diffusion-reaction equations. For anisotropic equations, numerical

experiments show that FNS can reduce the number of iterations by nearly

times compared to the state-of-the-art

Meta-MgNet when the anisotropic strength is relatively strong. For the non-symmetric systems arising from the

convection-diffusion equations discretized by central difference method, FNS can converge while MG and CG methods

diverge. And FNS is faster than other algorithms such GMRES and BiCGSTAB(

) [

]. For the indeﬁnite systems

arising from the Helmholtz equations, FNS outperforms GMRES and BiCGSTAB at medium wavenumbers. In this

paper, we apply FNS to above three PDE systems. However, the principles employed by FNS indicate that FNS has the

potential to be useful for a broad range of sparse linear algebraic systems.

The rest of this paper is organized as follows. Section 2 proposes a general form of linear convection-diffusion-reaction

equation and describes the motivation for designing FNS. Section 3 presents the FNS algorithm. Section 4 examines

the performance of FNS to anisotropy, convection-diffusion, and Helmholtz equations. Finally, Section 5 draws the

conclusions and future work.

2 Motivation

We consider the general linear convection-diffusion-reaction equation with Dirichlet boundary condition

−ε∇ · (α(x)∇u) + ∇ · (β(x)u) + γu =f(x)in Ω

u(x) = g(x)on ∂Ω(2.1)

where

Ω⊆Rd

is an open and bounded domain.

α(x)

is the

d×d−

order diffusion coefﬁcient matrix.

β(x)

is the

d×1velocity ﬁeld that the quantity is moving with. γis the reaction coefﬁcient. fis the source term.

We can obtain a linear algebraic system once we discretize Eq.

(4.1)

by ﬁnite element method (FEM) or ﬁnite difference

method (FDM)

Au =f,(2.2)

where A∈RN×N,f∈RNand Nis the spatial discrete degrees of freedom.

Classical stationary iterative methods, such as Gauss-Seidel and weighted Jacobi methods, have the generic form

uk+1 =uk+Bf−Auk,(2.3)

Fourier Neural Solver for large sparse linear algebraic systems

where

is an easily computed operator such as the inverse of diagonal matrix (Jacobi method), the inverse of lower

triangle matrix (Gauss-Seidel method). However, the convergence rate of such methods is relatively low. As an example,

we utilize the weighted Jacobi method to solve a special case of Eq. (2.1) and use LFA to analyze the reason.

Taking

ε= 1,α(x) = 1 0

0 1 

β(x) = 0

0

and

γ= 0

, Eq.

(2.1)

becomes the Poisson equation. With a linear

FEM discretization and in stencil notation, the resulting discrete operator reads

"−1

−1 4 −1

−1#.(2.4)

In weighted Jacobi method,

B=ωI/4

, where

ω∈(0,1]

and

is the identity matrix. Eq.

(2.3)

can be written in the

pointwise form

uk+1

ij =uk

ij +ω

4fij −(4uk

ij −uk

i−1,j −uk

i+1,j −uk

i,j−1−uk

i,j+1).(2.5)

Let uij be the true solution, and deﬁne error ek

ij =uij −uk

ij . Then we have

ek+1

ij =ek

ij −ω

4(4ek

ij −ek

i−1,j −ek

i+1,j −ek

i,j−1−ek

i,j+1).(2.6)

Expanding error in a Fourier series

ij =Pp1,p2vkei2π(p1xi+p2yj)

, substituting the general term

vkei2π(p1xi+p2yj)

p1, p2∈[−N/2, N/2) into Eq. (2.6), we have

vk+1 =vk1−ω

44−e−i2πp1h−ei2πp1h−e−i2πp2h−e−i2πp2h

=vk1−ω

4(4 −2 cos (2πp1h)−2 cos (2πp2h)).

The convergence factor of weighted Jacobi method (also known as smoother factor in MG framework [7]) is

µloc := 

vk+1

vk

=1−ω+ω

2(cos (2πp1h) + cos (2πp2h)).(2.7)

(a) Distribution of convergence factor µloc (b) High and low-frequency regions

Figure 1: (a) The distribution of convergence factor

µloc

of weighted Jacobi method (

ω= 2/3

) in solving linear system

arised by Poisson equation; (b) Low-frequency (white) and high-frequency (gray) regions.

Figure 1(a) shows the distribution of convergence factor

µloc

of weighted Jacobi (

ω= 2/3

) in solving linear system for

Poisson equation. For a better understanding, let

θ1= 2πp1h

θ2= 2πp2h

θ= (θ1, θ2)∈[−π, π)2

. Deﬁne the high

and low-frequency regions

Tlow := h−π

2,π

22,

Thigh := [−π, π)2\h−π

2,π

22,

(2.8)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

FOURIERNEURALSOLVERFORLARGESPARSELINEARALGEBRAICSYSTEMSChenCui1,KaiJiang1,YunLiu1andShiShuy11HunanKeyLaboratoryforComputationandSimulationinScienceandEngineering,KeyLaboratoryofIntelligentComputingandInformationProcessingofMinistryofEducation,SchoolofMathematicsandComputationalScience,XiangtanUnive...

展开>> 收起<<

FOURIER NEURAL SOLVER FOR LARGE SPARSE LINEAR ALGEBRAIC SYSTEMS Chen Cui1 Kai Jiang1 Yun Liu1and Shi Shuy1.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

FOURIER NEURAL SOLVER FOR LARGE SPARSE LINEAR ALGEBRAIC SYSTEMS Chen Cui1 Kai Jiang1 Yun Liu1and Shi Shuy1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: