Accelerating boundary integral equation method using a special-purpose computer
Corresponding Author
T. Takahashi
Computational Astrophysics Laboratory, The Institute of Physical and Chemical Research (RIKEN), 2-1 Hirosawa, Wako, Saitama, 351-0198, Japan
Computational Astrophysics Laboratory, The Institute of Physical and Chemical Research (RIKEN), 2-1 Hirosawa, Wako, Saitama, 351-0198, JapanSearch for more papers by this authorA. Kawai
Department of Informational Society Studies, Faculty of Human and Social Studies, Saitama Institute of Technology, 1690 Fusaiji, Okabe, Ohsato, Saitama, 369-0293, Japan
Search for more papers by this authorT. Ebisuzaki
Computational Astrophysics Laboratory, The Institute of Physical and Chemical Research (RIKEN), 2-1 Hirosawa, Wako, Saitama, 351-0198, Japan
Search for more papers by this authorCorresponding Author
T. Takahashi
Computational Astrophysics Laboratory, The Institute of Physical and Chemical Research (RIKEN), 2-1 Hirosawa, Wako, Saitama, 351-0198, Japan
Computational Astrophysics Laboratory, The Institute of Physical and Chemical Research (RIKEN), 2-1 Hirosawa, Wako, Saitama, 351-0198, JapanSearch for more papers by this authorA. Kawai
Department of Informational Society Studies, Faculty of Human and Social Studies, Saitama Institute of Technology, 1690 Fusaiji, Okabe, Ohsato, Saitama, 369-0293, Japan
Search for more papers by this authorT. Ebisuzaki
Computational Astrophysics Laboratory, The Institute of Physical and Chemical Research (RIKEN), 2-1 Hirosawa, Wako, Saitama, 351-0198, Japan
Search for more papers by this authorAbstract
We present a new solution to accelerate the boundary integral equation method (BIEM). The calculation time of the BIEM is dominated by the evaluation of the layer potential in the boundary integral equation. We performed this task using MDGRAPE-2, a special-purpose computer designed for molecular dynamics simulations. MDGRAPE-2 calculates pairwise interactions among particles (e.g. atoms and ions) using hardwired-pipeline processors. We combined this hardware with an iterative solver. During the iteration process, MDGRAPE-2 evaluates the layer potential. The rest of the calculation is performed on a conventional PC connected to MDGRAPE-2. We applied this solution to the Laplace and Helmholtz equations in three dimensions. Numerical tests showed that BIEM is accelerated by a factor of 10–100. Our rather naive solution has a calculation cost of O(N2 × Niter), where N is the number of unknowns and Niter is the number of iterations. Copyright © 2005 John Wiley & Sons, Ltd.
REFERENCES
- 1 Brebbia CA, Dominguez J. Boundary Elements: An Introductory Course ( 2nd edn). CMP: Southampton/McGraw-Hill: New York, 1992.
- 2 Bonnet M. Boundary Integral Equation Methods for Solids and Fluids. Wiley: West Sussex, 1995.
- 3 Kobayashi S, Fukui T, Kitahara M, Nishimura N, Hirose S. Boundary Element Method in Wave Analysis. Kyoto University Press: Kyoto, 2000 (in Japanese).
- 4 Kobayashi S, Kamiya H, Nishimura N. An algorithm for vectorization in boundary element computation for elastodynamics. In Computational Engineering with Boundary Elements, vol. 2, Solid and Computational Problems, AH-D Cheng, S Grilli, CA Brebbia (eds). CMP: Southampton, 1990; 127–137.
- 5 Cunha MTF, Telles JCF, Countinho ALGA, Panetta J. On the parallelization of boundary element codes using standard and portable libraries. Engineering Analysis with Boundary Elements 2004; 28: 893–902.
- 6 Engineering Analysis with Boundary Elements 1996; 18: 181–251 (Special issue for ‘Parallel BEM and Related Methods and Algorithms’, Brebbia CA, Tanaka M, Aliabadi MH, Cheng A, Kamiya N (eds)).
- 7 Engineering Analysis with Boundary Elements 1997; 19: 1–85 (Special issue for ‘High Performance Computing’, Ingber MS, Davies AJ (eds)).
- 8 Rokhlin V. Rapid solution of integral equations of classical potential theory. Journal of Computational Physics 1985; 60: 187–207.
- 9 Greengard L, Rokhlin V. A fast algorithm for particle simulations. Journal of Computational Physics 1987; 73: 325–348.
- 10 Chew WC, Jin J-M, Lu C-C, Michielssen E, Song JM. Fast solution methods in electromagnetics. IEEE Transactions on Antennas and Propagation 1997; 45: 533–543.
- 11 Nishimura N. Fast multipole accelerated boundary integral equation methods. Applied Mechanics Review 2002; 55: 299–324.
10.1115/1.1482087 Google Scholar
- 12 Beylkin G, Coifman R, Rokhlin V. Fast wavelet transforms and numerical algorithms I. Communications on Pure and Applied Mathematics 1991; 44: 141–183.
- 13 Dahmen W, Pröeßdorf S, Schneider R. Wavelet approximation methods for pseudodifferential equations II: matrix compression and fast solution. Advances in Computational Mathematics 1993; 1: 259–335.
10.1007/BF02072014 Google Scholar
- 14 Barrett R, Eijkhout V, Romine C, Vorstt H. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM: Philadelphia, PA, 1994.
10.1137/1.9781611971538 Google Scholar
- 15 Engineering Analysis with Boundary Elements 2003; 27: 403–564 (Special issue for ‘Large Scale Problems using BEM’, Nishimura N, Hayami K (eds)).
- 16 Narumi T. Special-purpose computer for molecular dynamics simulations. Doctoral Thesis, University of Tokyo, 1997.
- 17 Susukita R, Ebisuzaki T, Elmegreen BG, Furusawa H, Kato K, Kawai A, Kobayashi Y, Koishi T, McNiven GD, Narumi T, Yasuoka K. Hardware accelerator for molecular dynamics: MDGRAPE-2. Computer Physics Communications 2003; 155: 115–131.
- 18 Greengard L, Gropp WD. A parallel version of the fast multipole method. Computers Mathematical Application 1990; 20: 63–71.
- 19 Narumi T, Kawai A, Koishi T. An 8.61 T op/s molecular dynamics simulation for NaCl with a special-purpose computer: MDM. Proceedings of Supercomputing 2001. ACM: New York, 2001 (in CD-ROM).
- 20 Fukushige T, Kawai A, Makino J. Structure of dark matter halos from hierarchical clustering. III. Shallowing of the inner cusp. Astrophysical Journal 2004; 606: 625–634.
- 21 Makino J. A fast parallel treecode with GRAPE. Publication of Astronomical Society Japan 2004; 56: 521–531.
- 22 M Abramowitz, IA Stegun (eds). Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables (eighth Dover printing). Dover: New York, 1972.
- 23 Saad Y, Schultz MH. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on Scientific and Statistical Computing 1986; 7: 856–869.
- 24 Barnes J, Hut P. A hierarchical O(N log N) force calculation algorithm. Nature 1986; 324: 446–449.
- 25 Makino J. Treecode with a special-purpose processor. Publications of the Astronomical Society of Japan 1991; 43: 621–638.
- 26 Sugimoto D, Chikada Y, Makino J, Ito T, Ebisuzaki T, Umemura M. A special-purpose computer for gravitational many-body problems. Nature 1990; 345: 33–35.
- 27 Makino J, Taiji M, Ebisuzaki T, Sugimoto D. GRAPE-4: a massively parallel special-purpose computer for collisional N-body simulations. Astrophysical Journal 1997; 480: 432–446.
- 28 Makino J. Yet another fast multipole method without multipoles—pseudoparticle multipole method. Journal of Computational Physics 1999; 151: 910–920.
- 29 Kawai A, Makino J, Ebisuzaki T. Performance analysis of high-accuracy tree code based on pseudoparticle multipole method. Astrophysical Journal Supplement 2004; 151: 13–33.
- 30 Takahashi T. The application of MDGRAPE to boundary element method. Proceedings of RIKEN Symposia 2003; 3–7 (in Japanese).
- 31 Taiji M, Naurmi T, Ohno Y, Futatsugi N, Suenaga A, Takada N, Konagaya A. Protein Explorer: a petaflops special-purpose computer system for molecular dynamics simulations. Proceedings of Supercomputing 2003. ACM: New York, 2003 (in CD-ROM).
- 32 Ito T, Yabe T, Okazaki M, Yanagi M. Special-purpose computer HORN-1 for reconstruction of virtual image in three dimensions. Computer Physics Communications 1993; 82: 104–110.
- 33 Uragou M. Analytical integrals of fundamental solution of three-dimensional Laplace equation and their gradients. Transactions of Japanese Society of Mechanical Engineers 2000; 66A: 254–261 (in Japanese).
10.1299/kikaia.66.254 Google Scholar