High Order Spatial Generalization of 2D and 3D Isotropic Discrete Gradient Operators with Fast Evaluation on GPUs
详细信息 查看全文
- 作者：Sébastien Leclaire (1)
Maud El-Hachem (1)
Jean-Yves Trépanier (1)
Marcelo Reggio (1) - 关键词：Numerical differentiation ; Isotropic finite difference ; Order of accuracy ; Convolution ; Jacket plugin for MATLAB ; CUDA
- 刊名：Journal of Scientific Computing
- 出版年：2014
- 出版时间：June 2014
- 年：2014
- 卷：59
- 期：3
- 页码：545-573
- 全文大小：
- 参考文献：1. Ando, S.: Consistent gradient operators. IEEE Trans. Pattern Anal. Mach. Intell. 22(3), 252-65 (2000). 10.1109/34.841757 CrossRef
2. Brigham, E.O.: The Fast Fourier Transform and Its Applications. Prentice-Hall, Upper Saddle River (1988)
3. Chow, T.: Mathematical Methods for Physicists: A Concise Introduction. Cambridge University Press, Cambridge (2000) CrossRef
4. Farber, R.: Cuda, Supercomputing for the Masses: Part 11: Revisiting Cuda Memory Spaces (2009). http://www.drdobbs.com/parallel/cuda-supercomputing-for-the-masses-part/215900921
5. Fornberg, B.: Generation of finite difference formulas on arbitrarily spaced grids. Math. Comput. 51(184), 699-06 (1988) CrossRef
6. Gonzalez, R.C., Woods, R.E.: Digital Image Processing, 3rd edn. Prentice-Hall, Upper Saddle River (2006)
7. Grogger, H.A.: Finite difference approximations of first derivatives for three-dimensional grid singularities. J. Comput. Phys. 225(2), 2377-397 (2007) CrossRef
8. http://www.accelereyes.com/
9. Herceg, D., Cvetkovic, L.: On a numerical differentiation. SIAM J. Numer. Anal. 23(3), 686-91 (1986) CrossRef
10. Jastram, C., Behle, A.: Acoustic modelling on a grid of vertically varying spacing. Geophys. Prospect. 40(2), 157-69 (1992). doi:10.1111/j.1365-2478.1992.tb00369.x CrossRef
11. Knupp, P., Salari, K.: The mathematical model and numerical algorithm. In: Verification of Computer Codes in Computational Science and Engineering, Discrete Mathematics and Its Applications, pp. 7-7. Chapman and Hall/CRC (2002). doi:10.1201/9781420035421.ch2
12. Kumar, A.: Isotropic finite-differences. J. Comput. Phys. 201(1), 109-18 (2004) CrossRef
13. Leclaire, S., El-Hachem, M., Reggio, M.: MATLAB—A Fundamental Tool for Scientific Computing and Engineering Applications—Volume 3, Chap. Convolution Kernel for Fast CPU/GPU Computation of 2D/3D Isotropic Gradients on a Square/Cubic Lattice. InTech (2012)
14. Leclaire, S., Reggio, M., Trépanier, J.Y.: Isotropic color gradient for simulating very high-density ratios with a two-phase flow lattice boltzmann model. Comput. Fluids 48(1), 98-12 (2011). doi:10.1016/j.compfluid.2011.04.001 CrossRef
15. Leclaire, S., Reggio, M., Trépanier, J.Y.: Progress and investigation on lattice boltzmann modeling of multiple immiscible fluids or components with variable density and viscosity ratios. J. Comput. Phys. (0), (2013). doi:10.1016/j.jcp.2013.03.039 . http://www.sciencedirect.com/science/article/pii/S0021999113002179
16. NVIDIA: NVIDIA CUDA Programming Guide 2.0 (2008)
17. NVIDIA: CUDA Toolkit 4.2 CUFFT Library. NVIDIA Corporation (2012)
18. Patra, M., Karttunen, M.: Stencils with isotropic discretization error for differential operators. Numer. Methods Partial Differ. Equ. 22(4), 936-53 (2006). doi:10.1002/num.20129 CrossRef
19. Podlozhnyuk, V.: Fft-Based 2d Convolution. Tech. Rep, NVIDIA (2007)
20. Podlozhnyuk, V.: Image Convolution with Cuda. Tech. Rep. NVIDIA Corporation (2007)
21. Ramadugu, R., Thampi, S.P., Adhikari, R., Succi, S., Ansumali, S.: Lattice differential operators for computational physics. EPL (Europhys. Lett.) 101(5), 50006 (2013). http://stacks.iop.org/0295-5075/101/i=5/a=50006
22. Sbragaglia, M., Benzi, R., Biferale, L., Succi, S., Sugiyama, K., Toschi, F.: Generalized lattice boltzmann method with multirange pseudopotential. Phys. Rev. E 75(2), 026,702 (2007) CrossRef
23. Shan, X.: Analysis and reduction of the spurious current in a class of multiphase lattice boltzmann models. Phys. Rev. E 73(4), 047,701 (2006) CrossRef
24. Shen, G., Cangellaris, A.C.: A new fdtd stencil for reduced numerical anisotropy in the computer modeling of wave phenomena. Int. J. RF Microw. Comput. Aided Eng. 17(5), 447-54 (2007) CrossRef
25. Shi, J., Zhang, Y.T., Shu, C.W.: Resolution of high order WENO schemes for complicated flow structures. J. Comput. Phys. 186(2), 690-96 (2003). doi:10.1016/S0021-9991(03)00094-9 . http://www.sciencedirect.com/science/article/pii/S0021999103000949
26. Thampi, S.P., Ansumali, S., Adhikari, R., Succi, S.: Isotropic discrete laplacian operators from lattice hydrodynamics. J. Comput. Phys. (0), (in press) (2012). doi:10.1016/j.jcp.2012.07.037
27. Tscharntke, T., Hochberg, M.E., Rand, T.A., Resh, V.H., Krauss, J.: Author sequence and credit for contributions in multiauthored publications. PLoS Biol. 5(1), e18 (2007) CrossRef
28. Xiao, F., Tang, X., Mao, R., Zhang, X.: 3d low-dispersion ifd-fdtd based on 3d isotropic finite difference. Microw. Opt. Technol. Lett. 46(4), 381-84 (2005) CrossRef
29. Zalesak, S.T.: Fully multidimensional flux-corrected transport algorithms for fluids. J. Comput. Phys. 31(3), 335-62 (1979) CrossRef
30. Zu, Y.Q., He, S.: Phase-field-based lattice boltzmann model for incompressible binary fluid systems with density and viscosity contrasts. Phys. Rev. E 87(4), 043301 (2013) - 作者单位：Sébastien Leclaire (1)
Maud El-Hachem (1)
Jean-Yves Trépanier (1)
Marcelo Reggio (1)
1. Department of Mechanical Engineering, école Polytechnique, 2500, Chemin de Polytechnique, Montreal, QC, H3T 1J4, Canada - ISSN：1573-7691
文摘
Based on the concept of isotropic centered finite differences, this work generalizes the spatial order of accuracy of the 2D and 3D isotropic discrete gradient operators to a higher order. A suitable methodology is used to obtain a set of equations from which it is possible to deduce stencil weights to achieve numerical approximations of both high order spatial and high order isotropic gradients. We consider that the suggested discretization will be useful for enhancing the quality of the results in various scientific fields. The spatial order ( \(S\) ) controls the spatial order of accuracy of the gradient norm and direction, while the isotropic order?( \(I\) ) controls, in some situations, the spatial order of accuracy of the gradient direction. A useful list of the stencil weights needed to construct different high order spatial and isotropic gradients is given. Numerical tests show that the numerical spatial orders of accuracy of the gradient approximation are the same as those predicted theoretically. Also, to illustrate the benefit of the new discretizations, some simulations with a multiphase lattice Boltzmann model are presented. Then, a series of benchmarks comparing various efficient convolution algorithms used to compute function or image gradients is presented. Different platforms implemented on CPUs and GPUs are studied, namely: plain MATLAB; the Jacket plugin for MATLAB; and CUDA. The results show situations in which substantial computational speedup can be obtained with CUDA and the Jacket plugin for MATLAB versus MATLAB on a CPU. Examples of 2D and 3D gradient computations using convolution products performed with our code are available for download as electronic supplementary material.