|
Article information
2016 , Volume 21, ¹ 2, p.3-11
Abramov T.
Fast numerical solution of boundary value problems with known Greens function using cyclic convolution
Author has developed a method for fast numerical solution of boundary value problems with known explicit form of Green’s function. Solution of this kind of problems can be established just as an integral of product of two known functions, rather than solution of a difference problem. In the discrete formulation, we have just some kind of sum to calculate, but naive algorithm requires O(N2) operations, where N is the number of nodes of the computational grid. This procedure is extremely inefficient when N is large enough, and parallel computing doesn’t significantly help when N is about 106 and greater. The performance of the procedure could be improved substantially due to the modification of the algorithm. The desired sum (solution of the problem) has been converted to the form of cyclic convolution, which can be calculated in O(N log N) operations. The proposed method relies on this conversion only, and it does not imply any specific algorithm for calculating a cyclic convolution. In practice, the convolution theorem is often used for this. It uses both forward and inverse fast discrete Fourier transforms. The method has been numerically implemented for the problem of simulating Rayleigh - Taylor instability in high viscous incompressible and immiscible Newtonian fluid in the three-dimensional domain. It delivers the increase of the calculation speed by several orders of magnitude compared to the naive summation. The developed program uses convolution theorem for cyclic convolution. Fourier transforms have been calculated using NVIDIA’s graphics accelerators with the help of cuFFT library.
[full text]
Keywords: cyclic convolution, convolution theorem, fast Fourier transform, boundary value problem, Greens function, Rayleigh - Taylor instability
Author(s):
Abramov Timofey
Position: Junior Research Scientist
Office: Trofimuk Institute of Petroleum-Gas Geology and Geophysics of the Siberian Branch of the RAS, Novosibirsk state University
Address: 630090, Russia, Novosibirsk
E-mail: AbramovTV@ipgg.sbras.ru
References:
[1] Knuth, D.E. The art of computer programming. Vol. 2. Seminumerical Algorithms. 3rd edition. Addison-Wesley; 1998: 784.
[2] Gonzalez, R.C., Woods, R.E. Digital image processing. 2nd edition. Prentice Hall; 2002:793.
[3] Numerical methods in astrophysics: An introduction / P. Bodenheimer, G.P. Laughlin, M. Rozyczka, T. Plewa, H.W. Yorke. CRC Press; 2006: 344.
[4] Nussbaumer, H.J. Fast fourier transform and convolution algorithms. Second corrected and updated edition. Springer-Verlag; 1982: 276.
[5] The linear and cyclic convolution. Available at: http://www.dsplib.ru/content/conv/conv.html (accessed 21.07.2015). (In Russ.)
[6] Elsgolts, L. Differential equations and the calculus of variations. Moscow: Mir Publishers;1970: 440.
[7] Lunev, B.V. Isostasy as the dynamic equilibrium of a viscous fluid. Doklady AN SSSR. 1986; 290(1):72–76. (In Russ.)
[8] Lunev, B.V., Lapkovskii, V.V. Fast numerical simulation of salt tectonics: possibility of the operational application in geological practice. Physical Mesomechanics.2009; 12(1):63–74. (In Russ.)
[9] Abramov, T.V. Massively parallel Rayleigh—Taylor instability simulation using analytical expression of Green’s function of the corresponding boundary value problem. Computational Technologies. 2015; 20(4):3–16. (In Russ.)
Bibliography link:
Abramov T. Fast numerical solution of boundary value problems with known Greens function using cyclic convolution // Computational technologies. 2016. V. 21. ¹ 2. P. 3-11
|
