A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method. (English) Zbl 1297.65169
Summary: A numerical method for variable coefficient elliptic problems on two-dimensional domains is presented. The method is based on high-order spectral approximations and is designed for problems with smooth solutions. The resulting system of linear equations is solved using a direct solver with \(O(N^{1.5})\) complexity for the pre-computation and \(O(N\log N)\) complexity for the solve. The fact that the solver is direct is a principal feature of the scheme, and makes it particularly well suited to solving problems for which iterative solvers struggle; in particular for problems with highly oscillatory solutions. Numerical examples demonstrate that the scheme is fast and highly accurate. For instance, using a discretization with 12 points per wavelength, a Helmholtz problem on a domain of size \(100\times 100\) wavelengths was solved to ten correct digits. The computation was executed on a standard laptop; it involved 1.6 M degrees of freedom and required 100 s for the pre-computation, and 0.3 s for the actual solve.
MSC:
| 65N35 | Spectral, collocation and related methods for boundary value problems involving PDEs |
| 35J05 | Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation |
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
Keywords:
collocation method; Helmholtz equation; spectral method; direct solver; fast direct solver; numerical examplesReferences:
| [1] | Ainsworth, M.; Wajid, H. A., Dispersive and dissipative behavior of the spectral element method, SIAM Journal on Numerical Analysis, 47, 5, 3910-3937 (2009) · Zbl 1204.65137 |
| [2] | Ballard, G.; Demmel, J.; Holtz, O.; Schwartz, O., Minimizing communication in numerical linear algebra, SIAM Journal on Matrix Analysis and Applications, 32, 3, 866-901 (2011) · Zbl 1246.68128 |
| [5] | Duan, Ran; Rokhlin, Vladimir, High-order quadratures for the solution of scattering problems in two dimensions, J. Comput. Physics, 228, 6, 2152-2174 (2009) · Zbl 1161.65358 |
| [7] | Ethridge, F.; Greengard, L., A new fast-multipole accelerated poisson solver in two dimensions, SIAM Journal on Scientific Computing, 23, 3, 741-760 (2001) · Zbl 1002.65131 |
| [8] | George, A., Nested dissection of a regular finite element mesh, SIAM J. on Numerical Analysis, 10, 345-363 (1973) · Zbl 0259.65087 |
| [10] | Gillman, Adrianna; Young, Patrick; Martinsson, Per-Gunnar, A direct solver \(o(n)\) complexity for integral equations on one-dimensional domains, Frontiers of Mathematics in China, 7, 217-247, 10.1007/s11464-012-0188- (2012) · Zbl 1262.65198 |
| [11] | Graham, I. G.; Sloan, I. H., Fully discrete spectral boundary integral methods for helmholtz problems on smooth closed surfaces in \(\&z.drule;\) mathbbrˆ3, Numerische Mathematik, 92, 2, 289-323 (2002) · Zbl 1018.65139 |
| [12] | Grasedyck, Lars; Hackbusch, Wolfgang, Construction and arithmetics of \(H\)-matrices, Computing, 70, 4, 295-334 (2003) · Zbl 1030.65033 |
| [13] | Greengard, Leslie; Gueyffier, Denis; Martinsson, Per-Gunnar; Rokhlin, Vladimir, Fast direct solvers for integral equations in complex three-dimensional domains, Acta Numer., 18, 243-275 (2009) · Zbl 1176.65141 |
| [14] | Haldenwang, P.; Labrosse, G.; Abboudi, S.; Deville, M., Chebyshev 3-d spectral and 2-d pseudospectral solvers for the helmholtz equation, Journal of Computational Physics, 55, 1, 115-128 (1984) · Zbl 0544.65071 |
| [15] | Haney, M.; Snieder, R.; Ampuero, J.-P.; Hofmann, R., Spectral element modeling of fault-plane reflections arising from fluid pressure distributions, Geophys. J. Int., 170, 2, 933-951 (2007) |
| [16] | Hesthaven, J. S.; Dinesen, P. G.; Lynov, J. P., Spectral collocation time-domain modeling of diffractive optical elements, Journal of Computational Physics, 155, 2, 287-306 (1999) · Zbl 0956.78020 |
| [17] | Ho, K. L.; Greengard, L., A fast direct solver for structured linear systems by recursive skeletonization, SIAM Journal on Scientific Computing, 34, 5, 2507-2532 (2012) · Zbl 1259.65062 |
| [18] | Hoffman, A. J.; Martin, M. S.; Rose, D. J., Complexity bounds for regular finite difference and finite element grids, SIAM J. Numer. Anal., 10, 364-369 (1973) · Zbl 0261.65026 |
| [19] | Kopriva, D. A., A staggered-grid multidomain spectral method for the compressible navierstokes equations, Journal of Computational Physics, 143, 1, 125-158 (1998) · Zbl 0921.76121 |
| [20] | Kwan, Y. Y.; Shen, J., An efficient direct parallel spectral-element solver for separable elliptic problems, Journal of Computational Physics, 225, 2, 1721-1735 (2007) · Zbl 1123.65116 |
| [23] | Martinsson, P. G.; Rokhlin, V., A fast direct solver for boundary integral equations in two dimensions, J. Comp. Phys., 205, 1, 1-23 (2005) · Zbl 1078.65112 |
| [24] | Mehdizadeh, O. Z.; Paraschivoiu, M., Investigation of a two-dimensional spectral element method for helmholtz equation, Journal of Computational Physics, 189, 1, 111-129 (2003) · Zbl 1024.65112 |
| [25] | Melenk, J. M.; Sauter, S., Convergence analysis for finite element discretizations of the helmholtz equation with dirichlet-to-neumann boundary conditions, Math. Comp, 79, 272, 1871-1914 (2010) · Zbl 1205.65301 |
| [26] | Patera, A. T., A spectral element method for fluid dynamics: Laminar flow in a channel expansion, Journal of Computational Physics, 54, 3, 468-488 (1984) · Zbl 0535.76035 |
| [27] | Pfeiffer, H. P.; Kidder, L. E.; Scheel, M. A.; Teukolsky, S. A., A multidomain spectral method for solving elliptic equations, Computer physics communications, 152, 3, 253-273 (2003) · Zbl 1196.65179 |
| [29] | Pozrikides, C., Finite and spectral element methods (2005), Taylor & Francis · Zbl 1078.65109 |
| [30] | Schmitz, P. G.; Ying, L., A fast direct solver for elliptic problems on general meshes in 2d, Journal of Computational Physics, 231, 4, 1314-1338 (2012) · Zbl 1408.65022 |
| [31] | Shen, J.; Wang, L. L., Spectral approximation of the helmholtz equation with high wave numbers, SIAM journal on numerical analysis, 43, 2, 623-644 (2005) · Zbl 1091.65119 |
| [32] | Shen, J.; Wang, L. L., Analysis of a spectral-galerkin approximation to the helmholtz equation in exterior domains, SIAM Journal on Numerical Analysis, 45, 5, 1954-1978 (2007) · Zbl 1154.65082 |
| [33] | Starr, Page; Rokhlin, Vladimir; II, On the numerical solution of two-point boundary value problems., Comm. Pure Appl. Math., 47, 8, 1117-1159 (1994) · Zbl 0805.65080 |
| [34] | Trefethen, L. N., Spectral methods in matlab (2000), SIAM: SIAM Philadelphia · Zbl 0953.68643 |
| [36] | Xia, Jianlin; Chandrasekaran, Shivkumar; Gu, Ming; Li, Xiaoye S., Fast algorithms for hierarchically semiseparable matrices, Numerical Linear Algebra with Applications, 17, 6, 953-976 (2010) · Zbl 1240.65087 |
| [37] | Yang, B.; Hesthaven, J. S., Multidomain pseudospectral computation of maxwell’s equations in 3-d general curvilinear coordinates, Applied Numerical Mathematics, 33, 14, 281-289 (2000) · Zbl 0973.78006 |
| [38] | Zhu, C.; Qin, G.; Zhang, J., Implicit chebyshev spectral element method for acoustics wave equations, Finite Elements in Analysis and Design, 47, 2, 184-194 (2011) |
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.
