Alternating direction implicit time integrations for finite difference acoustic wave propagation: parallelization and convergence. (English) Zbl 1519.76217
Summary: This work studies the parallelization and empirical convergence of two finite difference acoustic wave propagation methods on 2-D rectangular grids, that use the same alternating direction implicit (ADI) time integration. This ADI integration is based on a second-order implicit Crank-Nicolson temporal discretization that is factored out by a Peaceman-Rachford decomposition of the time and space equation terms. In space, these methods highly diverge and apply different fourth-order accurate differentiation techniques. The first method uses compact finite differences (CFD) on nodal meshes that requires solving tridiagonal linear systems along each grid line, while the second one employs staggered-grid mimetic finite differences (MFD). For each method, we implement three parallel versions: (i) a multithreaded code in Octave, (ii) a C++ code that exploits OpenMP loop parallelization, and (iii) a CUDA kernel for a NVIDIA GTX 960 Maxwell card. In these implementations, the main source of parallelism is the simultaneous ADI updating of each wave field matrix, either column-wise or row-wise, according to the differentiation direction. In our numerical applications, the highest performances are displayed by the CFD and MFD CUDA codes that achieve speedups of 7.21x and 15.81x, respectively, relative to their C++ sequential counterparts with optimal compilation flags. Our test cases also allow to assess the numerical convergence and accuracy of both methods. In a problem with exact harmonic solution, both methods exhibit convergence rates close to 4 and the MDF accuracy is practically higher. Alternatively, both convergences decay to second order on smooth problems with severe gradients at boundaries, and the MDF rates degrade in highly-resolved grids leading to larger inaccuracies. This transition of empirical convergences agrees with the nominal truncation errors in space and time.
MSC:
| 76M20 | Finite difference methods applied to problems in fluid mechanics |
| 65M06 | Finite difference methods for initial value and initial-boundary value problems involving PDEs |
| 65M12 | Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs |
| 65Y05 | Parallel numerical computation |
| 76Q05 | Hydro- and aero-acoustics |
Software:
CUDAReferences:
| [1] | Bartolo, L. D.; Dors, C.; Mansur, W. J., A new family of finite-difference schemes to solve the heterogeneous acoustic wave equation, Geophysics, 77, 5, T187-T199 (2012) |
| [2] | Etgen., J. T.; O’Brien, M. J., Computational methods for large-scale 3D acoustic finite-difference modeling tutorial, Geophysics, 72, 5 (2007) |
| [3] | Graves, R. W., Simulating seismic wave propagation in 3D elastic media using staggered-grid finite differences, Bull Seismol Soc Am, 86, 4, 1091-1106 (1996) |
| [4] | Levander, A., Fourth-order finite-difference P-SV seismograms, Geophysics, 53, 1425-1436 (1988) |
| [5] | Qian, J.; Wu, S.; Cui, R., Accuracy of the staggered-grid finite-difference method of the acoustic wave equation for marine seismic reflection modeling, Chin J Oceanol Limnol, 31, 1, 169-177 (2013) |
| [6] | Rojas, O.; Otero, B.; Castillo, J. E.; Day, S. M., Low dispersive modeling of Rayleigh waves on partly staggered grids, Comput Geosci, 18, 1, 29-43 (2014) · Zbl 1395.65031 |
| [7] | Saenger, E. H.; Bohlen, T., Finite-difference modeling of viscoelastic and anisotropic wave propagation using the rotated staggered grid, Geophysics, 69, 583-591 (2004) |
| [8] | Saenger, E. H.; Gold, N.; Shapiro, S. A., Modeling the propagation of elastic waves using a modified finite-difference grid, Wave Motion, 31, 77-92 (2000) · Zbl 1074.74648 |
| [9] | Blanch, J. O.; Robertsson, J. O.A., A modified Lax-Wendroff correction for wave propagation in media described by Zener elements, Geophys J Int, 131, 2, 381-386 (1997) |
| [10] | Bohlen, T.; Wittkamp, F., Three-dimensional viscoelastic time-domain finite-difference seismic modelling using the staggered Adams-Bashforth time integrator, Geophys J Int, 204, 3, 1781-1788 (2016) |
| [11] | Sei, A.; Symes, W., Dispersion analysis of numerical wave propagation and its computational consequences, J Sci Comput, 10, 1-27 (1995) · Zbl 0840.76060 |
| [12] | Wicker, L. J.; Skamarock, W. C., Time-splitting methods for elastic models using forward time schemes, Mon Weather Rev, 130, 8, 2088-2097 (2002) |
| [13] | Zhang, W.; Zhang, Z.; Chen, X., Three-dimensional elastic wave numerical modelling in the presence of surface topography by a collocated-grid finite difference method on curvilinear grids, Geophys J Int, 190, 1, 358-378 (2012) |
| [14] | Peaceman, D. W.; Rachford, H. H., The numerical solution of parabolic and elliptic differential equations, J Soc Ind ApplMath, 3, 1, 28-41 (1955) · Zbl 0067.35801 |
| [15] | Ciment, M.; Leventhal, S. H., Higher order compact implicit schemes for the wave equation, Math Comput, 29, 132, 985-994 (1975) · Zbl 0309.35043 |
| [16] | Iyengar, S. R.; Mittal, R. C., High order difference schemes for the wave equation, Int J Numer Methods Eng, 12, 10, 1623-1628 (1978) · Zbl 0383.65056 |
| [17] | McKee, S., High accuracy ADI methods for hyperbolic equations with variable coefficients, IMA J Appl Math, 11, 1, 105-109 (1973) · Zbl 0259.65085 |
| [18] | Abdulkadir, Y., Comparison of finite difference schemes for the wave equation based on dispersion, J Appl Math Phys, 3, 1544-1562 (2015) |
| [19] | Deng, D.; Zhang, C., Application of a fourth-order compact ADI method to solve a two-dimensional linear hyperbolic equation, Int J Comput Math, 90, 2, 273-291 (2013) · Zbl 1278.65122 |
| [20] | Dongdong, H., An unconditionally stable spatial sixth-order CCD-ADI method for the two-dimensional linear telegraph equation, Numer Algorithms, 72, 4, 1103-1117 (2016) · Zbl 1350.65088 |
| [21] | Jinggang, Q., The new alternating direction implicit difference methods for the wave equations, J Comput Appl Math, 230, 213-223 (2009) · Zbl 1166.65044 |
| [22] | Kim, S.; Lim, H., High-order schemes for acoustic waveform simulation, Appl Numer Math, 57, 4, 402-414 (2007) · Zbl 1113.65087 |
| [23] | Liao, W., On the dispersion, stability and accuracy of a compact higher-order finite difference scheme for 3D acoustic wave equation, J Comput Appl Math, 270, 571-583 (2014) · Zbl 1321.65134 |
| [24] | Lele, S. K., Compact finite difference schemes with spectral-like resolution, J Comput Phys, 103, 16-42 (1992) · Zbl 0759.65006 |
| [25] | Michea, D.; Komatitisch, D., Accelerating a three-dimensional finite-difference wave propagation code using GPU graphics cards, Geophys J Int, 182, 1, 389-402 (2010) |
| [26] | Otero, B.; Francés, J.; Rodríguez, R.; Rojas, O.; Solano, F.; Guevara-Jordan, J., A performance analysis of a mimetic finite difference scheme for acoustic wave propagation on GPU platforms, Concurrency Comput, 29, 4, e3880 (2017) |
| [27] | Rubio, F.; Hanzich, M.; Farrés, A.; la Puente, J. D.; Cela, J. M., Finite-difference staggered grids in GPUS for anisotropic elastic wave propagation simulation, Comput Geosci, 70, C, 181-189 (2014) |
| [28] | Sudarmaji, S.; Sismanto, S.; Waluyo; Soedijono, B., Numerical modeling of 2D seismic wave propagation in fluid saturated porous media using graphics processing unit (GPU): study case of realistic simple structural hydrocarbon trap, AIP Conf Proc, 1755, 1, 100001 (2016) |
| [29] | Wang, Z.; Peng, S.; Liu, T., GPU accelerated 2-D staggered-grid finite difference seismic modelling, J Softw, 6, 8, 1554-1561 (2011) |
| [30] | Zhou, J.; Cui, Y.; Poyraz, E.; Choi, D. J.; Guest, C. C., Multi-GPU implementation of a 3D finite difference time domain earthquake code on heterogeneous supercomputers, Procedia Comput Sci, 18, 1255-1264 (2013) |
| [31] | Egloff, D., GPU in financial computing part III: ADI solvers on GPUs with application to stochastic volatility, WILMOTT Mag, 51-53 (2011) |
| [32] | Stefanski, T. P.; Drysdale, T. D., Acceleration of the 3D ADI-FDTD method using graphics processor units, 2009 IEEE MTT-S International microwave symposium digest (2009), IEEE |
| [33] | Wei, Z.; Jang, B.; Zhang, Y.; Jia, Y., Parallelizing alternating direction implicit solver on GPUs, Procedia Comput Sci, 18, 389-398 (2013) |
| [34] | Zhang, Y.; Jia, Y., Parallelization of implicit CCHE2D model using CUDA programming techniques, World environmental and water resources congress. Cincinnati, Ohio (2013) |
| [35] | Esfahanian, V.; Baghapour, B.; Torabzadeh, M.; Chizari, H., An efficient GPU implementation of cyclic reduction solver for high-order compressible viscous flow simulations, Comput Fluids, 92, 160-171 (2014) · Zbl 1391.76470 |
| [36] | Mandikas, V. G.; Mathioudakis, E. N., A parallel multigrid solver for incompressible flows on computing architectures with accelerators, J Supercomput, 73, 11, 4931-4956 (2017) |
| [37] | Srinath, A. T., A novel approach to evaluating compact finite differences and similar tridiagonal schemes on GPU-accelerated clusters (2015), Clemson University |
| [38] | Giles, M.; László, E.; Reguly, I.; Appleyard, J.; Demouth, J., GPU implementation of finite difference solvers, Proceedings of the 7th workshop on high performance computational finance, 1-8 (2014), IEEE Press: IEEE Press Piscataway, NJ, USA |
| [39] | Kim, H. S.; Wu, S.; w. Chang, L.; Hwu, W. W., A scalable tridiagonal solver for GPUs, 2011 International conference on parallel processing, 444-453 (2011) |
| [40] | Tutkun, B.; Edis, F. O., A GPU application for high-order compact finite difference scheme, Comput Fluids, 55, 29-35 (2012) · Zbl 1291.76232 |
| [41] | Dang, D. M.; Christara, C. C.; Jackson, K. R., A parallel implementation on GPUs of ADI finite difference methods for parabolic PDEs with applications in finance, Can Appl Math Q, 17, 4, 627-660 (2009) · Zbl 1229.91335 |
| [42] | Dang, D.-M.; Christara, C. C.; Jackson, K. R., Graphics processing unit pricing of exotic cross-currency interest rate derivatives with a foreign exchange volatility skew model, Concurrency Comput PractExp, 26, 9 (2010) |
| [43] | ISBN 9780123859631, 9780123859648 |
| [44] | Li-Wen, C.; Hwu, W. W., A guide for implementing tridiagonal solvers on GPUs, 29-44 (2014) · Zbl 1317.65076 |
| [45] | Córdova, L.; Rojas, O.; Otero, B.; Castillo, J. E., Compact finite difference modeling of 2-D acoustic wave propagation, J Comput Appl Math, 295, 83-91 (2016) · Zbl 1329.76226 |
| [46] | Castillo, J. E.; Grone, R. D., A matrix analysis approach to higher-order approximations for divergence and gradients satisfying a global conservation law, SIAM J Matrix Anal Appl, 25, 1, 128-142 (2003) · Zbl 1061.65018 |
| [47] | Castillo, J. E.; Hyman, J. M.; Shashkov, M.; Steinberg, S., Fourth- and sixth-order conservative finite difference approximations of the divergence and gradient, Appl Numer Math, 37, 1-2, 171-187 (2001) · Zbl 0978.65011 |
| [48] | Moya, F., Parallelization of finite difference methods: nodal and mimetic solutions of the wave equation (2016) |
| [49] | Cerjan, C.; Kosloff, D.; Kosloff, R.; Reshef, M., A nonreflecting boundary condition for discrete acoustic and elastic wave equations, Geophysics, 50, 4, 705-708 (1985) |
| [50] | Sochacki, J.; Kubichek, R.; George, J.; Fletcher, W. R.; Smithson, S., Absorbing boundary conditions and surface waves, Geophysics, 52, 1, 60-71 (1987) |
| [51] | Rojas, O., Modeling of rupture propagation under different friction laws using high-order mimetic operators (2009), Claremont Graduate University joint to San Diego State University: Claremont Graduate University joint to San Diego State University California, USA |
| [52] | Rojas, O.; Day, S. M.; Castillo, J. E.; Dalguer, L. A., Modelling of rupture propagation using high-order mimetic finite differences, Geophys J Int, 172, 2, 631-650 (2008) |
| [53] | Runyan, B., A novel higher order finite difference time domain method based on the Castillo-Grone mimetic curl operator with applications concerning the time-dependent Maxwell equations (2011), San Diego State University: San Diego State University San Diego, USA |
| [54] | Córdova, L., Diferencias finitas compactas nodales y centro distribuidas aplicadas a la simulacin de ondas acústicas (2017), Universidad Central de Venezuela |
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.
