×

Preconditioned Legendre spectral Galerkin methods for the non-separable elliptic equation. (English) Zbl 1486.65272

Summary: 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 method based on the incomplete LU factorization technique with no fill-in, denoted by ILU(0). The ILU(0) factorization of \(M\in{\mathbb{R}}^{(N-1)^d\times (N-1)^d}\) can be computed using \({\mathcal{O}}(T^{2d} N^d)\) operations, and the number of nonzeros in the factorization factors is of \({\mathcal{O}}(T^d N^d)\), \(d=1,2,3\). A conclusion of the algorithm is to fast solve the resulting system from the Legendre Galerkin spectral method for Poisson equations with Dirichlet boundary conditions, which has a complexity of \({\mathcal{O}}(N^d)\). 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 \({\mathcal{O}}(N^d (\log_2 N)^2)\). In view that \(T\) is independent of \(N\) in one dimension and is set to be of order \({\mathcal{O}}(\log_2 N)\) in two and three dimensions, the PCG method has a \({\mathcal{O}}(N^d (\log_2 N)^{2d})\) quasi-optimal complexity for a \(d\) dimensional domain with \((N-1)^d\) unknows, \(d=1,2,3\). In addition, a fast direct solver for the three-dimensional Poisson equation is developed, which is of \({\mathcal{O}}(N^3 (\log_2 N)^2)\) and improves the existing results on the computational complexity. Numerical examples are given to demonstrate the efficiency of proposed preconditioners and the algorithm for fast matrix-vector multiplications.

MSC:

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

Software:

NFFT3; NFFT
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Auteri, F.; Quartapelle, L., Galerkin-Legendre spectral method for the 3D Helmholtz equation, J. Comput. Phys., 161, 454-483 (2000) · Zbl 0959.65130
[2] Canuto, C.; Quarteroni, A., Preconditioner minimal residual methods for Chebyshev spectral calculations, J. Comput. Phys., 60, 315-337 (1985) · Zbl 0615.65118
[3] Canuto, C.; Hussaini, MY; Quarteroni, A.; Zang, TA, Spectral Methods: Fundamentals in Single Domains (2006), Berlin, Heidelberg: Springer-Verlag, Berlin, Heidelberg · Zbl 1093.76002
[4] Canuto, C.; Hussaini, MY; Quarteroni, A.; Zang, TA, Spectral Methods in Fluid Dynamics (1987), Berlin: Springer-Verlag, Berlin · Zbl 0717.76004
[5] Coutsias, E., Hagstrom, T., Hesthaven, J.S., Torres, D.: Integration preconditioners for differential operators in spectral \(\tau \)-methods. In: Proceedings of the Third International Conference on Spectral and High Order Methods, Houston, TX, pp. 21-38. (1996)
[6] Carlitz, L., The product of two ultraspherical polynomials, Proc. Glasgow Math. Assoc., 5, 76-79 (1961) · Zbl 0102.05601
[7] Concus, P.; Golub, GH, Use of fast direct methods for the efficient numerical solution of nonseparable elliptic equations, SIAM J. Numer. Anal., 10, 1103-1120 (1973) · Zbl 0245.65043
[8] Deville, MO; Mund, EH, Chebyshev pseudospectral solution of second-order elliptic equations with finite element preconditioning, J. Comput. Phys., 60, 517-533 (1985) · Zbl 0585.65073
[9] Deville, MO; Mund, EH, Finite-element preconditioning for pseudospectral solutions of elliptic problems, SIAM J. Sci. Stat. Comput., 11, 311-342 (1990) · Zbl 0701.65075
[10] Fenn, M.; Potts, D., Fast summation based on fast trigonometric transforms at non-equispaced nodes, Numer. Linear Algebra Appl., 12, 161-169 (2005) · Zbl 1164.65380
[11] Fang, Z.; Shen, J.; Sun, H., Preconditioning techniques in Chebyshev collocation method for elliptic equations, Inter. J. Numer. Anal. Model., 15, 277-287 (2018) · Zbl 1408.35025
[12] Gottlieb, D., Orszag, S.A.: Numerical Analysis of Spectral Methods: Theory and Applications. In: CBMS-NSF Regional Conference Series in Mathematics, 26, SIAM, Philadelphia (1977) · Zbl 0412.65058
[13] Hesthaven, J., Integration preconditioning of pseudospectral operators. I. Basic linear operators, SIAM J. Numer. Anal., 35, 1571-1593 (1998) · Zbl 0912.65067
[14] Hale, N.; Townsend, A., A fast, simple, and stable Chebyshev-Legendre transform using an asymptotic formula, SIAM J. Sci. Comput., 36, A148-A167 (2014) · Zbl 1290.65018
[15] Hale, N.; Townsend, A., A fast FFT-based discrete Legendre transform, IMA J. Numer. Anal., 36, 1670-1684 (2016) · Zbl 1433.65342
[16] Iserles, A., A fast and simple algorithm for the computation of Legendre coefficients, Numer. Math., 117, 529-553 (2011) · Zbl 1211.33001
[17] Kim, SD; Parter, SV, Preconditioning Chebyshev spectral collocation method for elliptic partial differential equations, SIAM J. Numer. Anal., 33, 2375-2400 (1996) · Zbl 0861.65095
[18] Kim, SD; Parter, SV, Preconditioning Chebyshev spectral collocation by finite difference operators, SIAM J. Numer. Anal., 34, 939-958 (1997) · Zbl 0874.65088
[19] Keiner, J.; Kunis, S.; Potts, D., Using NFFT 3-a software library for various nonequispaced fast Fourier transforms, ACM Trans. Math. Softw., 36, 1-30 (2009) · Zbl 1364.65303
[20] Kunis, S., Nonequispaced fast Fourier transforms without oversampling, PAMM, 8, 10977-10978 (2008) · Zbl 1395.94225
[21] Potts, D.: Fast algorithms for discrete polynomial transforms on arbitrary grids. Linear Algebra Appl. 366, 353-370 (2003). (Special issue on structured matrices: analysis, algorithms and applications (Cortona, 2000)) · Zbl 1026.65137
[22] Shen, J., Efficient spectral-Galerkin methods III: polar and cylindrical geometries, SIAM J. Sci. Comput., 18, 1583-1604 (1997) · Zbl 0890.65117
[23] Shen, J.: Efficient Chebyshev-Legendre Galerkin methods for elliptic problems. In: Ilin, A.V., Scott, R. (eds.) Proceedings of the ICOSAHOM’95, Houston J. Math., pp. 233-240. (1996)
[24] Shen, J.; Wang, YW; Xia, JL, Fast structured direct spectral methods for differential equations with variable coefficients, SIAM J. Sci. Comput., 38, A28-A54 (2016) · Zbl 1330.65124
[25] Shen, J.; Tang, T., Spectral and High-Order Methods with Applications (2006), Beijing: Science Press of China, Beijing · Zbl 1234.65005
[26] Shen, J.; Tang, T.; Wang, LL, Spectral Methods: Algorithms, Analysis and Applications (2011), Berlin: Springer, Berlin · Zbl 1227.65117
[27] Shen, J.; Wang, F.; Xu, J., A finite element multigrid preconditioner for chebyshev collocation methods, Appl. Numer. Math., 33, 471-477 (2000) · Zbl 0964.65133
[28] Shen, J., On fast direct Poisson solver, inf-sup constant and iterative Stokes solver by Legendre Galerkin method, J. Comput. Phys., 116, 184-188 (1995) · Zbl 0822.65083
[29] Shen, J., Efficient spectral-Galerkin method I. Direct solvers for second- and fourth-order equations using Legendre polynomials, SIAM J. Sci. Comput., 15, 1489-1505 (1994) · Zbl 0811.65097
[30] Swarztrauber, PN, A direct method for the discrete solution of separable elliptic equations, SIAM J. Numer. Anal., 11, 1136-1150 (1974) · Zbl 0292.65054
[31] Saad, Y.: Iterative Methods for Sparse Linear Systems, 3rd edn. PWS Pub Co., (2000)
[32] Tygert, M., Recurrence relations and fast algorithms, Appl. Comput. Harmon. Anal., 28, 121-128 (2010) · Zbl 1182.65195
[33] Trefethen, LN; Trummer, MR, An instability phenomenon in spectral methods, SIAM J. Numer. Anal., 24, 1008-1023 (1987) · Zbl 0636.65124
[34] Wang, LL; Samson, MD; Zhao, X., A well-conditioned collocation method using a pseudospectral integration matrix, SIAM J. Sci. Comput., 36, A907-A929 (2014) · Zbl 1297.65086
[35] Wang, H.; Xiang, S., On the convergence rates of Legendre approximation, Math. Comput., 81, 861-877 (2011) · Zbl 1242.41016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.