Efficient implementation of nonlinear compact schemes on massively parallel platforms. (English) Zbl 1320.65115

Summary: Weighted nonlinear compact schemes are ideal for simulating compressible, turbulent flows because of their nonoscillatory nature and high spectral resolution. However, they require the solution to banded systems of equations at each time-integration step or stage. We focus on tridiagonal compact schemes in this paper. We propose an efficient implementation of such schemes on massively parallel computing platforms through an iterative substructuring algorithm to solve the tridiagonal system of equations. The key features of our implementation are that it does not introduce any parallelization-based approximations or errors and it involves minimal neighbor-to-neighbor communications. We demonstrate the performance and scalability of our approach on the IBM Blue Gene/Q platform and show that the compact schemes are efficient and have performance comparable to that of standard noncompact finite-difference methods on large numbers of processors (\(\sim 500,000\)) and small subdomain sizes (four points per dimension per processor).


65M06 Finite difference methods for initial value and initial-boundary value problems involving PDEs
65Y05 Parallel numerical computation
76M20 Finite difference methods applied to problems in fluid mechanics
76N99 Compressible fluids and gas dynamics
Full Text: DOI Link


[5] N. A. Adams, {\it Direct numerical simulation of turbulent compression ramp flow}, Theoret. Comput. Fluid Dynam., 12 (1998), pp. 109-129. · Zbl 0931.76033
[6] N. A. Adams and K. Shariff, {\it A high-resolution hybrid compact-ENO scheme for shock-turbulence interaction problems}, J. Comput. Phys., 127 (1996), pp. 27-51. · Zbl 0859.76041
[7] I. Bermejo-Moreno, J. Bodart, J. Larsson, B. M. Barney, J. W. Nichols, and S. Jones, {\it Solving the compressible Navier-Stokes equations on up to 1.97 million cores and 4.1 trillion grid points}, in Proceedings of SC13: International Conference for High Performance Computing, Networking, Storage and Analysis, (New York, 2013), ACM, New York, pp. 62:1-62:10.
[8] L. Blackford, J. Choi, A. Cleary, E. D’Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, and R. Whaley, {\it ScaLAPACK Users’ Guide}, SIAM, Philadelphia, 1997. · Zbl 0886.65022
[9] J. Chao, A. Haselbacher, and S. Balachandar, {\it A massively parallel multi-block hybrid compact-WENO scheme for compressible flows}, J. Comput. Phys., 228 (2009), pp. 7473-7491. · Zbl 1172.76033
[10] S. C. Chen, D. J. Kuck, and A. H. Sameh, {\it Practical parallel band triangular systems solvers}, ACM Trans. Math. Software, 4 (1978), pp. 270-277. · Zbl 0384.65013
[11] A. Cleary and J. Dongarra, {\it Implementation in ScaLAPACK of Divide-and-Conquer Algorithms for Banded and Tridiagonal Linear Systems}, Tech. report UT-CS-97-358, University of Tennessee, Knoxville, TN, 1997.
[12] A. W. Cook, W. H. Cabot, P. L. Williams, B. J. Miller, B. R. de Supinski, R. K. Yates, and M. L. Welcome, {\it Tera-scalable algorithms for variable-density elliptic hydrodynamics with spectral accuracy}, in Proceedings of the 2005 ACM/IEEE Conference on Supercomputing (Washington, DC, 2005), IEEE Computer Society, Washington, DC, 2005, pp. 60-60.
[13] X. Deng and H. Maekawa, {\it Compact high-order accurate nonlinear schemes}, J. Comput. Phys., 130 (1997), pp. 77-91. · Zbl 0870.65075
[14] X. Deng and H. Zhang, {\it Developing high-order weighted compact nonlinear schemes}, J. Comput. Phys., 165 (2000), pp. 22-44. · Zbl 0988.76060
[15] J. J. Dongarra and A. H. Sameh, {\it On some parallel banded system solvers}, Parallel Comput., 1 (1984), pp. 223-235. · Zbl 0572.65015
[16] D. Fauconnier and E. Dick, {\it Spectral analysis of nonlinear finite difference discretizations}, J. Comput. Appl. Math., 246 (2013), pp. 113-121. · Zbl 1262.65099
[17] P. F. Fischer, F. P. Preparata, and J. E. Savage, {\it Generalized scans and tridiagonal systems}, Theoret. Comput. Sci., 255 (2001), pp. 423-436. · Zbl 0974.68058
[18] D. Ghosh, {\it Compact-Reconstruction Weighted Essentially Non-oscillatory Schemes for Hyperbolic Conservation Laws}, Ph.D. thesis, University of Maryland, College Park, MD, 2013.
[19] D. Ghosh and J. D. Baeder, {\it Compact reconstruction schemes with weighted ENO limiting for hyperbolic conservation laws}, SIAM J. Sci. Comput., 34 (2012), pp. A1678-A1706. · Zbl 1387.65085
[20] D. Ghosh and J. D. Baeder, {\it Weighted non-linear compact schemes for the direct numerical simulation of compressible, turbulent flows}, J. Sci. Comput., 61 (2014), pp. 61-89. · Zbl 1299.76098
[21] D. Ghosh, E. M. Constantinescu, and J. Brown, {\it Scalable Nonlinear Compact Schemes}, Tech. report ANL/MCS-TM-340, Argonne National Laboratory, Argonne, IL, 2014.
[22] D. Ghosh, S. Medida, and J. D. Baeder, {\it Application of compact-reconstruction weighted essentially nonoscillatory schemes to compressible aerodynamic flows}, AIAA J., 52 (2014), pp. 1858-1870.
[23] S. Ghosh, {\it Direct Numerical Simulation of the Interaction of a Laser-Induced Plasma with Isotropic Turbulence}, Ph.D. thesis, University of Minnesota, Minneapolis, MN, 2008.
[24] S. Gottlieb, D. I. Ketcheson, and C.-W. Shu, {\it High order strong stability preserving time discretizations}, J. Sci. Comput., 38 (2009), pp. 251-289. · Zbl 1203.65135
[25] Y. Guo, T. Xiong, and Y. Shi, {\it A positivity-preserving high order finite volume compact-WENO scheme for compressible Euler equations}, J. Comput. Phys., 274 (2014), pp. 505-523. · Zbl 1351.76108
[26] A. K. Henrick, T. D. Aslam, and J. M. Powers, {\it Mapped weighted essentially non-oscillatory schemes: Achieving optimal order near critical points}, J. Comput. Phys., 207 (2005), pp. 542-567. · Zbl 1072.65114
[27] C. Hirsch, {\it Numerical Computation of Internal and External Flows: The Fundamentals of Computational Fluid Dynamics}, Vols. 1 & 2, Elsevier Science, New York, 2007.
[28] J. Hofhaus and E. Van de Velde, {\it Alternating-direction line-relaxation methods on multicomputers}, SIAM J. Sci. Comput., 17 (1996), pp. 454-478. · Zbl 0851.65065
[29] G.-S. Jiang and C.-W. Shu, {\it Efficient implementation of weighted ENO schemes}, J. Comput. Phys., 126 (1996), pp. 202-228. · Zbl 0877.65065
[30] L. Jiang, H. Shan, and C. Liu, {\it Weighted compact scheme for shock capturing}, Int. J. Comput. Fluid Dyn., 15 (2001), pp. 147-155. · Zbl 1044.76046
[31] J. W. Kim and R. D. Sandberg, {\it Efficient parallel computing with a compact finite difference scheme}, Comput. & Fluids, 58 (2012), pp. 70-87. · Zbl 1365.65196
[32] C. B. Laney, {\it Computational Gasdynamics}, Cambridge University Press, Cambridge, UK, 1998. · Zbl 0947.76001
[33] C. Liu, L. Jiang, M. Visbal, and P. Xie, {\it Smart weighted compact scheme for shock tube and shock-entropy interaction}, in 36th AIAA Fluid Dynamics Conference and Exhibit (San Francisco, 2006), American Institute of Aeronautics and Astronautics, Reston, VA, 2006, AIAA 2006-3708.
[34] X.-D. Liu, S. Osher, and T. Chan, {\it Weighted essentially non-oscillatory schemes}, J. Comput. Phys., 115 (1994), pp. 200-212. · Zbl 0811.65076
[35] N. N. Mansour and A. A. Wray, {\it Decay of isotropic turbulence at low Reynolds number}, Phys. Fluids, 6 (1994), pp. 808-814. · Zbl 0825.76278
[36] N. Mattor, T. J. Williams, and D. W. Hewett, {\it Algorithm for solving tridiagonal matrix problems in parallel}, Parallel Comput., 21 (1995), pp. 1769-1782.
[37] U. Meier, {\it A parallel partition method for solving banded systems of linear equations}, Parallel Comput., 2 (1985), pp. 33-43. · Zbl 0599.65016
[38] S. Pirozzoli, {\it Conservative hybrid compact-WENO schemes for shock-turbulence interaction}, J. Comput. Phys., 178 (2002), pp. 81-117. · Zbl 1045.76029
[39] E. Polizzi and A. H. Sameh, {\it A parallel hybrid banded system solver: The SPIKE algorithm}, Parallel Comput., 32 (2006), pp. 177-194.
[40] E. Polizzi and A. H. Sameh, {\it SPIKE: A parallel environment for solving banded linear systems}, Comput. & Fluids, 36 (2007), pp. 113-120. · Zbl 1181.76110
[41] A. Povitsky and P. J. Morris, {\it A higher-order compact method in space and time based on parallel implementation of the Thomas algorithm}, J. Comput. Phys., 161 (2000), pp. 182-203. · Zbl 0959.65102
[42] Y.-X. Ren, M. Liu, and H. Zhang, {\it A characteristic-wise hybrid compact-WENO scheme for solving hyperbolic conservation laws}, J. Comput. Phys., 192 (2003), pp. 365-386. · Zbl 1037.65090
[43] R. S. Rogallo, {\it Numerical Experiments in Homogeneous Turbulence}, Tech. report NASA-TM-81315, NASA Ames Research Center, Moffett Field, CA, 1981.
[44] Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, 2nd ed., SIAM, Philadelphia, 2003. · Zbl 1031.65046
[45] C.-W. Shu, {\it Essentially Non-oscillatory and Weighted Essentially Non-oscillatory Schemes for Hyperbolic Conservation Laws}, Tech. report NASA CR-97-206253, ICASE Report 97-65, Institute for Computer Applications in Science and Engineering, Hampton, VA, 1997.
[46] C.-W. Shu, {\it High order weighted essentially nonoscillatory schemes for convection dominated problems}, SIAM Rev., 51 (2009), pp. 82-126. · Zbl 1160.65330
[47] H. S. Stone, {\it An efficient parallel algorithm for the solution of a tridiagonal linear system of equations}, J. ACM, 20 (1973), pp. 27-38. · Zbl 0269.65018
[48] X.-H. Sun and S. Moitra, {\it A Fast Parallel Tridiagonal Algorithm for a Class of CFD Applications}, Tech. report 3585, National Aeronautics and Space Administration, NASA Langley Research Center, Hampton, VA, 1996.
[49] H. H. Wang, {\it A parallel method for tridiagonal equations}, ACM Trans. Math. Software, 7 (1981), pp. 170-183. · Zbl 0473.65010
[50] Z. Wang and G. P. Huang, {\it An essentially nonoscillatory high-order Padé-type (ENO-Padé) scheme}, J. Comput. Phys., 177 (2002), pp. 37-58. · Zbl 1063.76070
[51] P. Xie and C. Liu, {\it Weighted compact and non-compact scheme for shock tube and shock entropy interaction}, in 45th AIAA Aerospace Sciences Meeting and Exhibit, American Institute of Aeronautics and Astronautics, Reston, VA, 2007, AIAA 2007-509.
[52] S. Zhang, S. Jiang, and C.-W. Shu, {\it Development of nonlinear weighted compact schemes with increasingly higher order accuracy}, J. Comput. Phys., 227 (2008), pp. 7294-7321. · Zbl 1152.65094
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.