Preconditioned Legendre spectral Galerkin methods for the non-separable elliptic equation

DOI10.1007/S10915-021-01755-XMaRDI QIDQ2113655zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 14 March 2022

Published in Journal of Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.13961

zbMATH Keywords

preconditioned conjugate gradient methodspectral methodincomplete LU factorizationdense and ill-conditioned matrixnon-separable elliptic equation

Mathematics Subject Classification ID

Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22) Spectral, collocation and related methods for boundary value problems involving PDEs (65N35) Special integral transforms (Legendre, Hilbert, etc.) (44A15)

Abstract: The Legendre spectral Galerkin method of self-adjoint second order elliptic equations usually results in a linear system with a dense and ill-conditioned coefficient matrix. In this paper, the linear system is solved by a preconditioned conjugate gradient (PCG) method where the preconditioner $M$ is constructed by approximating the variable coefficients with a ($T$+1)-term Legendre series in each direction to a desired accuracy. A feature of the proposed PCG method is that the iteration step increases slightly with the size of the resulting matrix when reaching a certain approximation accuracy. The efficiency of the method lies in that the system with the preconditioner $M$ is approximately solved by a one-step iterative method based on the ILU(0) factorization. The ILU(0) factorization of $Minmathbb{R}^{(N-1{)}^{d}imes(N-1{)}^d}$ can be computed using $mathcalO(T^{2d}{N}^d)$ operations, and the number of nonzeros in the factorization factors is of $mathcalO(T^d{N}^d)$, $d=1,2,3$. To further speed up the PCG method, an algorithm is developed for fast matrix-vector multiplications by the resulting matrix of Legendre-Galerkin spectral discretization, without the need to explicitly form it. The complexity of the fast matrix-vector multiplications is of $mathcalO(N^d(logN{)}^2)$. As a result, the PCG method has a $mathcalO(N^d(logN{)}^2)$ total complexity for a $d$ dimensional domain with $(N-1{)}^d$ unknows, $d=1,2,3$. Numerical examples are given to demonstrate the efficiency of proposed preconditioners and the algorithm for fast matrix-vector multiplications.

Recommendations

• Efficient Spectral-Galerkin Method I. Direct Solvers of Second- and Fourth-Order Equations Using Legendre Polynomials
• Preconditioning Legendre spectral collocation methods for elliptic problems. I: Finite difference operators
• Preconditioned conjugate residual methods for the solution of spectral equations
• Fast Poisson solvers for spectral methods
• Finite Element Preconditioning for Legendre Spectral Collocation Approximations to Elliptic Equations and Systems

Cites work

• scientific article; zbMATH DE number 49939 (Why is no real title available?)
• scientific article; zbMATH DE number 3640828 (Why is no real title available?)
• A direct Method for the Discrete Solution of Separable Elliptic Equations
• A fast FFT-based discrete Legendre transform
• A fast and simple algorithm for the computation of Legendre coefficients
• A fast, simple, and stable Chebyshev-Legendre transform using an asymptotic formula
• A finite element multigrid preconditioner for Chebyshev-collocation methods
• A well-conditioned collocation method using a pseudospectral integration matrix
• An Instability Phenomenon in Spectral Methods
• Chebyshev pseudospectral solution of second-order elliptic equations with finite element preconditioning
• Efficient Spectral-Galerkin Method I. Direct Solvers of Second- and Fourth-Order Equations Using Legendre Polynomials
• Efficient Spectral-Galerkin Methods III: Polar and Cylindrical Geometries
• Fast algorithms for discrete polynomial transforms on arbitrary grids
• Fast structured direct spectral methods for differential equations with variable coefficients. I. The one-dimensional case
• Fast summation based on fast trigonometric transforms at non‐equispaced nodes
• Finite-Element Preconditioning for Pseudospectral Solutions of Elliptic Problems
• Galerkin-Legendre spectral method for the 3D Helmholtz equation
• Integration Preconditioning of Pseudospectral Operators. I. Basic Linear Operators
• Nonequispaced fast Fourier transforms without oversampling
• On fast direct Poisson solver, inf-sup constant and iterative Stokes solver by Legendre-Galerkin method
• On the convergence rates of Legendre approximation
• Preconditioned minimal residual methods for Chebyshev spectral calculations
• Preconditioning Chebyshev Spectral Collocation Method for Elliptic Partial Differential Equations
• Preconditioning Chebyshev Spectral Collocation by Finite-Difference Operators
• Preconditioning techniques in Chebyshev collocation method for elliptic equations
• Recurrence relations and fast algorithms
• Spectral Methods
• Spectral and high-order methods with applications.
• Spectral methods. Algorithms, analysis and applications.
• The product of two ultraspherical polynomials
• Use of Fast Direct Methods for the Efficient Numerical Solution of Nonseparable Elliptic Equations
• Using NFFT 3 -- a software library for various nonequispaced fast Fourier transforms

Cited in

(6)

• A Legendre spectral quadrature Galerkin method for the Cauchy-Navier equations of elasticity with variable coefficients
• Efficient pseudospectral Legendre preconditioner for minimum time orbit problem
• Preconditioning Legendre spectral collocation methods for elliptic problems. I: Finite difference operators
• A Legendre spectral Galerkin method for the biharmonic Dirichlet problem
• PRECONDITIONED SPECTRAL COLLOCATION METHOD ON CURVED ELEMENT DOMAINS USING THE GORDON-HALL TRANSFORMATION
• A factorization of the spectral Galerkin system for parameterized matrix equations: derivation and applications

Describes a project that uses

Uses Software

• NFFT3
• NFFT

This page was built for publication: Preconditioned Legendre spectral Galerkin methods for the non-separable elliptic equation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2113655)