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

DOI10.1007/S10915-021-01755-XzbMATH Open1486.65272arXiv2004.13961OpenAlexW3023666136MaRDI QIDQ2113655FDOQ2113655

Authors: Yanyan Li 

Publication date: 14 March 2022

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

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.

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

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

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)

Cites Work

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

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

Uses Software

• NFFT
• NFFT3

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)