×

zbMATH — the first resource for mathematics

Factorizing the factorization – a spectral-element solver for elliptic equations with linear operation count. (English) Zbl 1380.65373
Summary: The paper proposes a novel factorization technique for static condensation of a spectral-element discretization matrix that yields a linear operation count of just \(13N\) multiplications for the residual evaluation, where \(N\) is the total number of unknowns. In comparison to previous work, it saves a factor larger than 3 and outpaces unfactored variants for all polynomial degrees. Using the new technique as a building block for a preconditioned conjugate gradient method yields linear scaling of the runtime with \(N\) which is demonstrated for polynomial degrees from 2 to 32. This makes the spectral-element method cost effective even for low polynomial degrees. Moreover, the dependence of the iterative solution on the element aspect ratio is addressed, showing only a slight increase in the number of iterations for aspect ratios up to 128. Hence, the solver is very robust for practical applications.

MSC:
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65N35 Spectral, collocation and related methods for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
Software:
BLAS
PDF BibTeX Cite
Full Text: DOI
References:
[1] Gottlieb, D.; Orszag, S. A., Numerical analysis of spectral methods: theory and applications, CBMS-NSF Regional Conference Series in Applied Mathematics, (1977), Society for Industrial and Applied Mathematics Philadelphia · Zbl 0412.65058
[2] Canuto, C.; Hussaini, M.; Quarteroni, A.; Zang, T. A., Spectral methods. fundamentals in single domains, (2006), Springer Berlin/Heidelberg · Zbl 1093.76002
[3] Patera, A. T., A spectral element method for fluid dynamics: laminar flow in a channel expansion, J. Comput. Phys., 54, 3, 468-488, (1984) · Zbl 0535.76035
[4] Couzy, W.; Deville, M., A fast Schur complement method for the spectral element discretization of the incompressible Navier-Stokes equations, J. Comput. Phys., 116, 1, 135-142, (1995) · Zbl 0832.76068
[5] Yakovlev, S.; Moxey, D.; Kirby, R. M.; Sherwin, S. J., To CG or to HDG: a comparative study in 3d, J. Sci. Comput., 67, 1, 192-220, (2015) · Zbl 1339.65225
[6] Kwan, Y.-Y.; Shen, J., An efficient direct parallel spectral-element solver for separable elliptic problems, J. Comput. Phys., 225, 2, 1721-1735, (2007) · Zbl 1123.65116
[7] Haupt, L.; Stiller, J.; Nagel, W. E., A fast spectral element solver combining static condensation and multigrid techniques, J. Comput. Phys., 255, 384-395, (2013) · Zbl 1349.65645
[8] Hartmann, R.; Lukáčová-Medvid’ová, M.; Prill, F., Efficient preconditioning for the discontinuous Galerkin finite element method by low-order elements, Appl. Numer. Math., 59, 8, 1737-1753, (2009) · Zbl 1171.65078
[9] Huismann, I.; Stiller, J.; Fröhlich, J., Fast static condensation for the Helmholtz equation in a spectral-element discretization, (Parallel Processing and Applied Mathematics, (2016), Springer International Publishing Cham), 371-380
[10] Huismann, I.; Haupt, L.; Stiller, J.; Fröhlich, J., Sum factorization of the static condensed Helmholtz equation in a three-dimensional spectral element discretization, PAMM, 14, 1, 969-970, (2014)
[11] Beck, A. D.; Bolemann, T.; Flad, D.; Frank, H.; Gassner, G. J.; Hindenlang, F.; Munz, C.-D., High-order discontinuous Galerkin spectral element methods for transitional and turbulent flow simulations, Int. J. Numer. Methods Fluids, 76, 8, 522-548, (2014)
[12] Lombard, J.-E. W.; Moxey, D.; Sherwin, S. J.; Hoessler, J. F.A.; Dhandapani, S.; Taylor, M. J., Implicit large-eddy simulation of a wingtip vortex, AIAA J., 54, 2, 506-518, (2016)
[13] Lynch, R. E.; Rice, J. R.; Thomas, D. H., Direct solution of partial difference equations by tensor product methods, Numer. Math., 6, 1, 185-199, (1964) · Zbl 0126.12703
[14] Deville, M. O.; Fischer, P. F.; Mund, E. H., High-order methods for incompressible fluid flow, (2002), Cambridge University Press Cambridge · Zbl 1007.76001
[15] Karniadakis, G. E.; Sherwin, S. J., Spectral/hp element methods for computational fluid dynamics, (2005), Oxford University Press Oxford · Zbl 1116.76002
[16] Hirsch, C., Numerical computation of internal & external flows: fundamentals of numerical discretization, (1988), John Wiley & Sons, Inc. New York · Zbl 0662.76001
[17] Dongarra, J. J.; Croz, J. D.; Hammarling, S.; Duff, I. S., A set of level 3 basic linear algebra subprograms, ACM Trans. Math. Softw., 16, 1, 1-17, (1990) · Zbl 0900.65115
[18] Merzari, E.; Pointer, W.; Fischer, P., Numerical simulation and proper orthogonal decomposition of the flow in a counter-flow T-junction, J. Fluids Eng., 135, 9, (2013)
[19] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 6, 409-436, (1952) · Zbl 0048.09901
[20] Shewchuk, J. R., An introduction to the conjugate gradient method without the agonizing pain, (1994), Tech. Rep., Pittsburgh
[21] Manna, M.; Vacca, A.; Deville, M. O., Preconditioned spectral multi-domain discretization of the incompressible Navier-Stokes equations, J. Comput. Phys., 201, 1, 204-223, (2004) · Zbl 1195.76261
[22] Trottenberg, U.; Oosterlee, C.; Schüller, A., Multigrid, (2000), Academic Press Cambridge
[23] Bornemann, F. A.; Deuflhard, P., The cascadic multigrid method for elliptic problems, Numer. Math., 75, 2, 135-152, (1996) · Zbl 0873.65107
[24] Pflaum, C., A multigrid conjugate gradient method, Appl. Numer. Math., 58, 12, 1803-1817, (2008) · Zbl 1156.65034
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.