Deflation-accelerated preconditioning of the Poisson-Neumann Schur problem on long domains with a high-order discontinuous element-based collocation method. (English) Zbl 1349.65621
Summary: A combination of block-Jacobi and deflation preconditioning is used to solve a high-order discontinuous element-based collocation discretization of the Schur complement of the Poisson-Neumann system as arises in the operator splitting of the incompressible Navier-Stokes equations. The preconditioners and deflation vectors are chosen to mitigate the effects of ill-conditioning due to highly-elongated domains typical of simulations of strongly non-hydrostatic environmental flows, and to achieve Generalized Minimum RESidual method (GMRES) convergence independent of the size of the number of elements in the long direction. The ill-posedness of the Poisson-Neumann system manifests as an inconsistency of the Schur complement problem, but it is shown that this can be accounted for with appropriate projections out of the null space of the Schur complement matrix without affecting the accuracy of the solution. The block-Jacobi preconditioner is shown to yield GMRES convergence independent of the polynomial order and only weakly dependent on the number of elements within a subdomain in the decomposition. The combined deflation and block-Jacobi preconditioning is compared with two-level non-overlapping block-Jacobi preconditioning of the Schur problem, and while both methods achieve convergence independent of the grid size, deflation is shown to require half as many GMRES iterations and \(25\%\) less wall-clock time for a variety of grid sizes and domain aspect ratios. The deflation methods shown to be effective for the two-dimensional Poisson-Neumann problem are extensible to the three-dimensional problem assuming a Fourier discretization in the third dimension. A Fourier discretization results in a two-dimensional Helmholtz problem for each Fourier component that is solved using deflated block-Jacobi preconditioning on its Schur complement. Here again deflation is shown to be superior to two-level non-overlapping block-Jacobi preconditioning, requiring about half as many GMRES iterations and \(15\%\) less time.
MSC:
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
| 65F08 | Preconditioners for iterative methods |
| 65N22 | Numerical solution of discretized equations for boundary value problems involving PDEs |
| 65N35 | Spectral, collocation and related methods for boundary value problems involving PDEs |
| 76D05 | Navier-Stokes equations for incompressible viscous fluids |
| 76M10 | Finite element methods applied to problems in fluid mechanics |
Keywords:
Poisson equation; spectral element; deflation; preconditioning; Schur complement; domain decompositionSoftware:
ParMETISReferences:
| [1] | Abdilghanie, A. M.; Diamessis, P. J., The internal gravity wave field emitted by a stably stratified turbulent wake, J. Fluid Mech., 720, 104-139 (2013) · Zbl 1284.76119 |
| [2] | Antonietti, P. F.; Ayuso, B., Schwarz domain decomposition preconditioners for discontinuous Galerkin approximations of elliptic problems: non-overlapping case, ESAIM: Math. Model. Numer. Anal., 41, 1 (2007) · Zbl 1129.65080 |
| [3] | Antonietti, P. F.; Houston, P., A class of domain decomposition preconditioners for hp-discontinuous Galerkin finite element methods, J. Sci. Comput., 46, 124-149 (2010) · Zbl 1230.65123 |
| [4] | Beuchler, S., Multigrid solver for the inner problem in decomposition methods for p-FEM, SIAM J. Numer. Anal., 40, 3, 928-944 (2002) · Zbl 1030.65125 |
| [5] | Bialecki, B.; Karageorghis, A., A nonoverlapping domain decomposition method for Legendre spectral collocation problems, J. Sci. Comput., 32, 2, 373-409 (2007) · Zbl 1134.65086 |
| [6] | Bjorck, A., Solving linear least squares problems by Gram-Schmidt Orthogonalization, BIT Numer. Math., 7, 1-21 (1967) · Zbl 0183.17802 |
| [7] | Brenner, S. C., Two-level additive Schwarz preconditioners for nonconforming finite element methods, Math. Comput., 65, 215, 897-922 (1996) · Zbl 0859.65124 |
| [8] | Brenner, S. C., The condition number of the Schur complement in domain decomposition, Numer. Math., 83, 187-203 (1999) · Zbl 0936.65141 |
| [9] | Brix, K.; Campos Pinto, M.; Canuto, C.; Dahmen, W., Multilevel preconditioning of discontinuous Galerkin spectral element methods. Part I: geometrically conforming meshes, IMA J. Numer. Anal., 35, 1487-1532 (2015) · Zbl 1353.65119 |
| [10] | Brown, P. N.; Walker, H. F., GMRES on (nearly) singular systems, SIAM J. Matrix Anal. Appl., 18, 1, 37-51 (1997) · Zbl 0876.65019 |
| [11] | Canuto, C.; Pavarino, L. F.; Pieri, A. B., BDDC preconditioners for continuous and discontinuous Galerkin methods using spectral/hp elements with variable local polynomial degree, IMA J. Numer. Anal., 34, 879-903 (2013) · Zbl 1297.65150 |
| [12] | Carvalho, L. M.; Giraud, L.; Le Tallec, P., Algebraic two-level preconditioners for the Schur complement method, SIAM J. Sci. Comput., 22, 1987-2005 (2001) · Zbl 0990.65134 |
| [13] | Costa, B.; Don, W. S., On the computation of high order pseudospectral derivatives, Appl. Numer. Math., 33, 151-159 (2000) · Zbl 0964.65020 |
| [14] | Couzy, W.; Deville, M. O., A fast Schur complement method for the spectral element discretization of the incompressible Navier-Stokes equations, J. Comput. Phys., 116, 135-142 (1995) · Zbl 0832.76068 |
| [15] | Cros, J.-M., A preconditioner for the Schur complement domain decomposition method, (14th International Conference on Domain Decomposition Methods (2002)), 373-380 |
| [16] | Diamessis, P. J.; Domaradzki, J. A.; Hesthaven, J. S., A spectral multidomain penalty method model for the simulation of high Reynolds number localized incompressible stratified turbulence, J. Comput. Phys., 202, 298-322 (2005) · Zbl 1061.76054 |
| [17] | Diamessis, P. J.; Redekopp, L. G., Numerical investigation of solitary internal wave-induced global instability in shallow water benthic boundary layers, J. Phys. Oceanogr., 36, 784-812 (2006) |
| [18] | Diamessis, P. J.; Spedding, G. R.; Domaradzki, J. A., Similarity scaling and vorticity structure in high-Reynolds-number stably stratified turbulent wakes, J. Fluid Mech., 671, 52-95 (2011) · Zbl 1225.76167 |
| [19] | Erlangga, Y. A.; Nabben, R., Deflation and balancing preconditioners for Krylov subspace methods applied to nonsymmetric matrices, SIAM J. Matrix Anal. Appl., 30, 684-699 (2008) · Zbl 1163.65014 |
| [20] | Escobar-Vargas, J.; Diamessis, P.; Sakai, T., A spectral quadrilateral multidomain penalty method model for high Reynolds number incompressible stratified flows, Int. J. Numer. Methods Fluids, 75, 403-425 (March 2014) · Zbl 1455.65167 |
| [21] | Farhat, C.; Lesoinne, M.; Letallec, P.; Pierson, K.; Rixen, D., FETI-DP: a dual-primal unified FETI method part I: a faster alternative to the two-level FETI method, Int. J. Numer. Methods Eng., 50, 1523-1544 (2001) · Zbl 1008.74076 |
| [22] | Farhat, C.; Tezaur, R.; Toivanen, J., A domain decomposition method for discontinuous Galerkin discretizations of Helmholtz problems with plane waves and Lagrange multipliers, Int. J. Numer. Methods Eng., 78, 1513-1531 (2009) · Zbl 1171.76417 |
| [23] | Feng, X.; Karakashian, O. A., Two-level additive Schwarz methods for a discontinuous Galerkin approximation of second order elliptic problems, SIAM J. Numer. Anal., 39, 1343-1365 (2001) · Zbl 1007.65104 |
| [24] | Fischer, P., An overlapping Schwarz method for spectral element solution of the incompressible Navier-Stokes equations, J. Comput. Phys., 1-35 (1997) |
| [25] | Fischer, P. F.; Lottes, J. W., Hybrid Schwarz-multigrid method for the spectral element method: extensions to Navier-Stokes, (Domain Decomposition Methods in Science and Engineering (2005), Springer: Springer Berlin, Heidelberg), Ch. 1, p. 16 · Zbl 1067.65123 |
| [26] | Gaul, A.; Gutknecht, M.; Liesen, J.; Nabben, R., A framework for deflated and augmented Krylov subspace methods, SIAM J. Matrix Anal. Appl., 34, 495-518 (2013) · Zbl 1273.65049 |
| [27] | Geyer, W. R.; Ralston, D. K.; Hole, W., The Dynamics of Strongly Stratified Estuaries, vol. 2 (2011), Elsevier Inc. |
| [28] | Ghysels, P.; Ashby, T. J.; Meerbergen, K.; Vanroose, W., Hiding global communication latency in the GMRES algorithm on massively parallel machines, SIAM J. Sci. Comput., 35, C48-C71 (2013) · Zbl 1273.65050 |
| [29] | Greenbaum, A.; Pták, V.; Strakoš, Z. K., Any nonincreasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl., 17, 3, 465-469 (1996) · Zbl 0857.65029 |
| [30] | Hager, W. W., Updating the inverse of a matrix, SIAM Rev., 31, 2, 221-239 (1989) · Zbl 0671.65018 |
| [31] | Hesthaven, J. S., A stable penalty method for the compressible Navier-Stokes equations: II. One-dimensional domain decomposition schemes, SIAM J. Sci. Comput., 18, 3, 658-685 (1997) · Zbl 0882.76061 |
| [32] | Hesthaven, J. S., A stable penalty method for the compressible Navier-Stokes equations: III. Multidimensional domain decomposition schemes, SIAM J. Sci. Comput., 20, 1, 62-93 (1998) · Zbl 0957.76059 |
| [33] | Hesthaven, J. S.; Gottlieb, S.; Gottlieb, D., Spectral Methods for Time-Dependent Problems (2007), Cambridge University Press · Zbl 1111.65093 |
| [34] | Hofmann, M.; Kontoghiorghes, E. J., Pipeline Givens sequences for computing the QR decomposition on a EREW PRAM, Parallel Comput., 32, 222-230 (2006) |
| [35] | Kanschat, G., Preconditioning methods for local discontinuous Galerkin discretizations, SIAM J. Sci. Comput., 25, 815-831 (2003) · Zbl 1048.65110 |
| [36] | Karniadakis, G. E., Spectral element simulations of laminar and turbulent flows in complex geometries, Appl. Numer. Math., 6, 85-105 (1989) · Zbl 0678.76050 |
| [37] | Karniadakis, G. E.; Israeli, M.; Orszag, S. A., High-order splitting methods for the incompressible Navier-Stokes equations, J. Comput. Phys., 97, 414-443 (1991) · Zbl 0738.76050 |
| [38] | Karypis, G., ParMETIS - parallel graph partitioning and fill-reducing matrix ordering (2013) |
| [39] | Li, J.; Widlund, O., BDDC algorithms for incompressible Stokes equations, SIAM J. Numer. Anal., 44, 2432-2455 (2006) · Zbl 1233.76077 |
| [40] | Lien, R.-C.; D’Asaro, E. A.; Henyey, F.; Chang, M.-H.; Tang, T.-Y.; Yang, Y.-J., Trapped core formation within a shoaling nonlinear internal wave, J. Phys. Oceanogr., 42, 511-525 (2004) |
| [41] | Manna, M.; Vacca, A.; Deville, M. O., Preconditioned spectral multi-domain discretization of the incompressible Navier-Stokes equations, J. Comput. Phys., 201, 204-223 (2004) · Zbl 1195.76261 |
| [42] | Meurant, G.; Duintjer Tebbens, J., The role eigenvalues play in forming GMRES residual norms with non-normal matrices, Numer. Algorithms, 143-165 (2014) · Zbl 1312.65050 |
| [43] | Nabben, R.; Vuik, C., A comparison of deflation and coarse grid correction applied to porous media flow, SIAM J. Numer. Anal., 42, 4, 1631-1647 (2004) · Zbl 1146.76658 |
| [44] | Nicolaides, R. A., Deflation of conjugate gradients with applications to boundary value problems, SIAM J. Numer. Anal., 24, 2, 355-365 (1987) · Zbl 0624.65028 |
| [45] | Olson, L. N.; Hesthaven, J. S.; Wilcox, L. C., Developments in overlapping Schwarz preconditioning of high-order nodal discontinuous Galerkin discretizations, (Domain Decomposition Methods in Science and Engineering XVI. Domain Decomposition Methods in Science and Engineering XVI, November 2004 (2004)), 1-8 |
| [46] | Pasquetti, R.; Rapetti, F.; Pavarino, L.; Zampieri, E., Neumann-Neumann-Schur complement methods for Fekete spectral elements, J. Eng. Math., 56, 323-335 (2006) · Zbl 1110.65113 |
| [47] | Pavarino, L. F.; Warburton, T., Overlapping Schwarz methods for unstructured spectral elements, J. Comput. Phys., 160, 298-317 (2000) · Zbl 0957.65104 |
| [48] | Pozrikidis, C., A note on the regularization of the discrete Poisson-Neumann problem, J. Comput. Phys., 172, 917-923 (2001) · Zbl 1034.76043 |
| [49] | Saad, Y., Iterative Methods for Sparse Linear Systems, vol. 3 (2003), Society for Industrial and Applied Mathematics · Zbl 1031.65046 |
| [50] | Santilli, E.; Scotti, A., An efficient method for solving highly anisotropic elliptic equations, J. Comput. Phys., 230, 23, 8342-8359 (2011) · Zbl 1241.65088 |
| [51] | Santilli, E.; Scotti, A., The stratified ocean model with adaptive refinement, J. Comput. Phys., 291, 60-81 (2015) · Zbl 1349.86027 |
| [52] | Scotti, A.; Mitran, S., An approximated method for the solution of elliptic problems in thin domains: application to nonlinear internal waves, Ocean Model., 25, 144-153 (2008) |
| [53] | Tang, J.; Vuik, K., Acceleration of preconditioned Krylov solvers for bubbly flow problems, (Parallel Processing and Applied Mathematics, vol. 7203 (2012)), 286-296 |
| [54] | Tang, J. M.; MacLachlan, S. P.; Nabben, R.; Vuik, C., A comparison of two-level preconditioners based on multigrid and deflation, SIAM J. Matrix Anal. Appl., 31, 1715-1739 (2010) · Zbl 1205.65143 |
| [55] | Tang, J. M.; Nabben, R.; Vuik, C.; Erlangga, Y. A., Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods, J. Sci. Comput., 39, 340-370 (2009) · Zbl 1203.65073 |
| [56] | Toselli, A.; Widlund, O., Domain Decomposition Methods - Algorithms and Theory (2004), Springer |
| [57] | Vitousek, S.; Fringer, O. B., Physical vs. numerical dispersion in nonhydrostatic ocean modeling, Ocean Model., 40, 1, 72-86 (2011) |
| [58] | Vitousek, S.; Fringer, O. B., A nonhydrostatic, isopycnal-coordinate ocean model for internal waves, Ocean Model., 83, 118-144 (2014) |
| [59] | Vuik, C.; Nabben, R.; Tang, J., Deflation acceleration for domain decomposition preconditioners, (Proceedings of the 8th European Multigrid Conference on Multigrid, Multilevel and Multiscale Methods, vol. 29291 (2006)), 1-10 |
| [60] | Walker, H. F., Implementation of the GMRES method using householder transformations, SIAM J. Sci. Stat. Comput., 9, 1, 152-163 (1988) · Zbl 0698.65021 |
| [61] | Watanabe, T.; Riley, J. J.; Kops, S. M.D. B.; Diamessis, P. J.; Zhou, Q., Turbulent/non-turbulent interfaces in wakes in stably-stratified fluids, J. Fluid Mech. (2015), submitted for publication · Zbl 1422.76091 |
| [62] | Yamazaki, I.; Li, X. S., On techniques to improve robustness and scalability of the Schur complement method, (Proceedings of the 9th International VECPAR Conference, vol. 2 (2010)) |
| [63] | Yamazaki, I.; Li, X. S.; Ng, E. G., Preconditioning Schur complement systems of highly-indefinite linear systems for a parallel hybrid solver, Numer. Math., 3, 352-366 (2010) · Zbl 1240.65103 |
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.
