×

CADD: a seamless solution to the domain decomposition problem of subdomain boundaries and cross-points. (English) Zbl 1524.65921

Summary: The solution of wave problems using Domain Decomposition (DD) requires that the subdomain boundaries should be virtually non-existent, so that waves are not affected by the boundaries. This is a primary problem in DD, and it intensifies in the case of cross-points at which three or more subdomains meet. This topic has received a lot of attention in recent years, with special treatment of cross-points. This paper explains and demonstrates that this problem does not exist in Component-Averaged Domain Decomposition (CADD). CADD is implemented here with the authors’ CARP-CG algorithm, but it is shown that other implementations are also possible. The reason for the non-existence of this problem in CARP-CG is that in some superspace of the problem space, CARP-CG is mathematically equivalent to the CG acceleration of the Kaczmarz algorithm with cyclic relaxation parameters, applied to a single linear system. Due to its advantages, CARP-CG was adopted by some geophysics researchers as the solver of the Helmholtz and the elastic wave equations for full waveform inversion (FWI).

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation

Software:

CARP-CG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berenger, J.-P., A perfectly matched layer for the absorption of electromagnetic waves, J. Comput. Phys., 114, 185-200 (1994) · Zbl 0814.65129
[2] Berenger, J.-P., Three-dimensional perfectly matched layer for the absorption of electromagnetic waves, J. Comput. Phys., 127, 363-379 (1996) · Zbl 0862.65080
[3] Boubendir, Y.; Bendali, A.; Fares, M. B., Coupling of a non-overlapping domain decomposition method for a nodal finite element method with a boundary element method, Internat. J. Numer. Methods Engrg., 73, 11, 1624-1650 (2008) · Zbl 1175.78026
[4] Engquist, B.; Ying, L., Sweeping preconditioner for the Helmholtz equation: moving perfectly matched layers, Multiscale Model. Simul., 9, 2, 686-710 (2011) · Zbl 1228.65234
[5] Gander, M. J.; Kwok, F., Optimized Schwarz methods at cross points, SIAM J. Sci. Comput., 34, 4, A1849-A1879 (2012) · Zbl 1254.65126
[6] Loisel, S., Condition number estimates for the nonoverlapping optimized Schwarz method and the 2-Lagrange multiplier method for general domains and cross points, SIAM J. Numer. Anal., 51, 6, 3062-3083 (2013) · Zbl 1287.35003
[7] Stolk, C. C., A rapidly converging domain decomposition method for the Helmholtz equation, J. Comput. Phys., 241, 240-252 (2013) · Zbl 1349.65426
[8] Stolk, C. C., An improved sweeping domain decomposition preconditioner for the Helmholtz equation, Adv. Comput. Math., 43, 45-76 (2017) · Zbl 1367.65188
[9] Gordon, D.; Gordon, R., Component-averaged row projections: A robust, block-parallel scheme for sparse linear systems, SIAM J. Sci. Comput., 27, 1092-1117 (2005) · Zbl 1093.65033
[10] Gordon, D.; Gordon, R., CARP-CG: a robust and efficient parallel solver for linear systems, applied to strongly convection-dominated PDEs, Parallel Comput., 36, 9, 495-515 (2010) · Zbl 1195.65062
[11] Kaczmarz, S., Angenäherte Auflösung von Systemen linearer Gleichungen, Bull. Acad. Pol. Sci. Lett. A, 35, 355-357 (1937) · JFM 63.0524.02
[12] Gordon, D.; Gordon, R., Row scaling as a preconditioner for some nonsymmetric linear systems with discontinuous coefficients, J. Comput. Appl. Math., 234, 12, 3480-3495 (2010) · Zbl 1196.65066
[13] Björck, Å.; Elfving, T., Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations, BIT, 19, 145-163 (1979) · Zbl 0409.65022
[14] Gordon, D.; Gordon, R., Solution methods for linear systems with large off-diagonal elements and discontinuous coefficients, CMES Comput. Model. Eng. Sci., 53, 1, 23-45 (2009) · Zbl 1231.65065
[15] Gordon, D.; Gordon, R., Parallel solution of high frequency Helmholtz equations using high order finite difference schemes, Appl. Math. Comput., 218, 21, 10737-10754 (2012) · Zbl 1257.65057
[16] Eggermont, P. P.B.; Herman, G. T.; Lent, A., Iterative algorithms for large partitioned linear systems, with applications to image reconstruction, Linear Algebra Appl., 40, 37-67 (1981) · Zbl 0466.65021
[17] Gordon, R.; Bender, R.; Herman, G. T., Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography, J. Theoret. Biol., 29, 3, 471-481 (1970)
[18] Herman, G. T., Fundamentals of Computerized Tomography: Image Reconstruction from Projections (2009), Springer · Zbl 1280.92002
[19] van Leeuwen, T.; Gordon, D.; Gordon, R.; Herrmann, F., Preconditioning the Helmholtz equation via row projections, (Proc. 74th EAGE Conference, Copenhagen, Denmark (2012), EAGE), 60-65
[20] van Leeuwen, T.; Herrmann, F. J., 3D frequency-domain seismic inversion with controlled sloppiness, SIAM J. Sci. Comput., 36, 5, S192-S217 (2014) · Zbl 1305.86008
[21] Bayliss, A.; Goldstein, C. I.; Turkel, E., On accuracy conditions for the numerical computation of waves, J. Comput. Phys., 59, 396-404 (1985) · Zbl 0647.65072
[22] Babus̆ka, I. M.; Sauter, S. A., Is the pollution effect of the FEM avoidable for the Helmholtz equation considering high wave numbers?, SIAM Rev., 42, 451-484 (2000) · Zbl 0956.65095
[23] Turkel, E.; Gordon, D.; Gordon, R.; Tsynkov, S., Compact 2D and 3D sixth order schemes for the Helmholtz equation with variable wave number, J. Comput. Phys., 232, 1, 272-287 (2013) · Zbl 1291.65273
[24] Gordon, D.; Gordon, R.; Turkel, E., Compact high order schemes with gradient-direction derivatives for absorbing boundary conditions, J. Comput. Phys., 297, 9, 295-315 (2015) · Zbl 1349.65556
[25] Li, Y.; Métivier, L.; Brossier, R.; Han, B.; Virieux, J., 2D and 3D frequency-domain elastic wave modeling in complex media with a parallel iterative solver, Geophysics, 80, 3, T101-T118 (2015)
[26] Li, Y.; Han, B.; Métivier, L.; Brossier, R., Optimal fourth-order staggered-grid finite-difference scheme for 3D frequency-domain viscoelastic wave modeling, J. Comput. Phys., 321, 1055-1078 (2016) · Zbl 1349.74361
[27] Galgon, M.; Krämer, L.; Thies, J.; Basermann, A.; Lang, B., On the parallel iterative solution of linear systems arising in the FEAST algorithm for computing inner eigenvalues, Parallel Comput., 49, 153-163 (2015)
[28] Thies, J.; Galgon, M.; Shahzad, F.; Alvermann, A.; Kreutzer, M.; Pieper, A.; Röhrig-Zöllner, M.; Basermann, A.; Fehske, H.; Hager, G.; Lang, B.; Wellein, G., Towards an exascale enabled sparse solver repository, (Bungartz, H. J.; Neumann, P.; Nagel, W., Software for Exascale Computing - SPPEXA 2013-2015. Software for Exascale Computing - SPPEXA 2013-2015, Lecture Notes in Computational Science and Engineering, vol. 113 (2016), Springer: Springer Cham, Switzerland), 73-89
[29] Sommerfeld, A., Partial Differential Equations in Physics (1964), Academic Press: Academic Press New York
[30] Bayliss, A.; Gunzburger, M.; Turkel, E., Boundary conditions for the numerical solution of elliptic equations in exterior regions, SIAM J. Appl. Math., 42, 430-451 (1982) · Zbl 0479.65056
[31] Gordon, D., The Cimmino-Kaczmarz equivalence and related results, Appl. Anal. Optim., 2, 2, 253-270 (2018) · Zbl 1485.15005
[32] Cimmino, G., Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari, (La Ricerca Scientifica XVI. La Ricerca Scientifica XVI, Series II, Anno IX, vol. 1 (1938)), 326-333 · JFM 64.1244.02
[33] Censor, Y.; Gordon, D.; Gordon, R., Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems, Parallel Comput., 27, 6, 777-808 (2001) · Zbl 0972.68189
[34] Censor, Y.; Gordon, D.; Gordon, R., BICAV: A block-iterative parallel algorithm for sparse systems with pixel-dependent weighting, IEEE Trans. Med. Imaging, 20, 10, 1050-1060 (2001)
[35] Censor, Y.; Elfving, T.; Herman, G. T., Averaging strings of sequential iterations for convex feasibility problems, (Butnariu, D.; Censor, Y.; Reich, S., Inherently Parallel Algorithms in Feasibility and Optimization and their Applications. Inherently Parallel Algorithms in Feasibility and Optimization and their Applications, Studies in Computational Mathematics, vol. 8 (2001), Elsevier: Elsevier Amsterdam), 101-113 · Zbl 1160.65320
[36] Elble, J.; Sahinidis, N.; Vouzis, P., GPU computing with Kaczmarz’s and other iterative algorithms, Parallel Comput., 36, 215-231 (2010) · Zbl 1204.68260
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.