Implementation of Hierarchical Tree Structure in Fast Multipole Method in 2-D Seismic Elastic Domain

Document Type : Geotechnical Earthquake Engineering


International Institute of Earthquake Engineering and Seismology (IIEES)


A numerical boundary element, as an appurtenance of integral equation method, has some useful characteristics that facilitate the solutions of numerical equations, but asymmetrical and sparse structure of formed stiffness matrix in large-scale boundary element method related to high degree of freedom problems make it unpractical, especially in seismic analysis of large-scale surface topographies with irregularities. Nowadays, fast algorithms such as fast multi-pole method present new media in numerical solutions with the aim of revolutionary changes in geometric definitions. In contrary with the usual node-to-node or element-toelement interconnection implementation, the cell-to-cell relation along hierarchy tree structure is applied. In most papers, the fast algorithm uses a two-level hierarchical tree structure as a part of algorithm internally without detail illustration. Therefore, a comprehensive detail of hierarchical tree structure is requested. In this paper, a multi-level (level definition is dynamic) hierarchical tree structure is presented with graphical theme and examples. This paper presents the relation between conventional boundary element method geometric structure with hierarchical tree model, and later, explains the method along with its abilities and limitations.


  1. Kamalian, M., Gatmiri, B., Sohrabi-Bidar, A., and Khalaj, A. (2007) Amplification pattern of 2D semi-sine shaped valleys subjected to vertically
  2. propagating incident waves. Commun. Numer. Methods Eng., 23(10), 871-887.
  3. Friedman, M.B. and Shaw, R. (1962) Diffraction of pulses by cylindrical obstacles of arbitrary cross section. J. Appl. Mech., 29(1), 40-46.
  4. Cole, D.N., Kosloff, D.D., and Minster, J.B. (1978) A numerical boundary integral equation method for elastodynamics. Bulletin of the Seismological Society of America , 68(5), 1331-1357.
  5. Niwa, Y., Fukui, T., Kato, S., and Fujiki, K. (1980) An application of the integral equation method to two-dimensional elastodynamics. Theor. Appl.
  6. Mech., 28, 281-290.
  7. Manolis, G.D. and Beskos, D.E. (1981) Dynamic stress concentration studies by boundary integrals and Laplace transforms. Int. J. Numer. Methods
  8. Eng., 17(4), 573-599.
  9. Manolis, G.D. (1983) A comparative study on three boundary element method approaches to problems in elastodynamics. Int. J. Numer. Methods Eng.,
  10. (1), 73-91.
  11. Mansur, W.J. (1983) A Time-Stepping Technique to Solve Wave Propagation Problems Using the Boundary Element Method. Ph.D. Dissertation,
  12. University of Southampton.
  13. Antes, H. (1985) A boundary elements procedure for transient wave propagation in two-dimensional isotropic elastic media. Finite Elem. Anal. Des.,
  14. (4), 313-322.
  15. Spyrakos, C.C. and Antes, H. (1986) Time domain boundary element method approaches in elastodynamics: a comparative study. Comput. Struct., 24(4), 529-535.
  16. Israil, A.S.M. and Banerjee, P.K. (1990b) Advanced time-domain formulation of BEM for two-dimensional transient elastodynamics. Int. J. Numer. Methods Eng., 29(7), 1421-1440.
  17. Kamalian, M., Gatmiri, B., and Sohrabi-Bidar, A. (2003) On time-domain two dimensional site response analysis of topographic structures by BEM. J. Seism. Earthq. Eng., 5(2), 35-45.
  18. Greengard, L.F. and Rokhlin, V. (1987) A fast algorithm for particle simulations. J. Comput. Phys., 73, 325-348.
  19. Darve, E. (2000) The fast multipole method: Numerical Implementation. J. of computational Physics, 160, 195-240.
  20. Greenbaum, A., Greengard, L., and McFadden, GB. (1993) Laplace's equation and Dirichlet-Neumann map in multiply connected domains. J. Comput. Phys., 105, 267-278.
  21. Greengard, L. (1988) The Rapid Evaluation of Potential Fields in Particle Systems. MIT Press, Cambridge, MA.
  22. Greengard L. and Helsing J. (1988) On the numerical evaluation of elastostatic fields in locally isotropic two-dimensional composits. J. Mech. Phys., 46, 1441-1462.
  23. Greengard, L. and Kropinski, M.C. (1996) Integral equation methods for stokes flow and isotropic elasticity in the plane. J. Comput. Phys.,
  24. , 403-414.
  25. Ergin A. Michielssen E. Shanker B. (1999) Fast transient analysis of acoustic wave scattering from rigid bodies using a two-level plane wave
  26. time domain algorithm. J. Acoust. Soc. Am., 106, 2405-2416.
  27. Warren, M.S. and Salmon, J.K. (1992) Astrophysical N-body simulations using hierarchical tree data structures. Supercomputing, 92, 570-
  28. Board, J.A., Causey, J.W., Leathrum, J.F., Windemuth, A., and Schulten, K. (1992) Accelerated molecular dynamics simulation with the parallel fast multipole method. Chem. Phys. Lett., 198, 89-94.
  29. Salmon, J.K., Warren, M.S., and Winckelmans, G.S. (1994) Fast parallel tree codes for gravitational and fluid dynamical N-body problems.
  30. Int. J. Supercomput. Appl., 8, 124-142.
  31. Takahashi, T., Nishimura, N., and Kobayashi, S. (2001) Fast Boundary Integral Equation method for Elastodynamic Problems in 2D in Time
  32. Domain. Trans. JSME (A), 661(67), 1409-1416.
  33. Otani, Y., Takahashi, T., and Nishimura, N. (2003) A fast boundary integral equation method for elastodynamics in time domain and its parallelisation. J. American Society of Mechanical Engineers, 55(4), 161-185.
  34. Nishimura, N. (2002) Fast multipole accelerated boundary integral equation methods. J. American Society of Mechanical Engineers, 55(4), 299-324.
  35. Shen, L. and Liu Y.J. (2007) An adaptive fast multipole boundary element method for threedimensional potential problems. Comput. Mech.,
  36. , 681-691.
  37. Liu, Y.L. and Nishimura N. (2006) The fast multipole boundary element method for potential problems: A tutorial. Eng. Anal. Boundary Elements, 30, 371-381.