Hostname: page-component-8448b6f56d-42gr6 Total loading time: 0 Render date: 2024-04-18T08:22:26.528Z Has data issue: false hasContentIssue false
  • English
  • Français

Fast direct solvers for integral equations in complex three-dimensional domains

Published online by Cambridge University Press:  08 May 2009

Leslie Greengard ,
Denis Gueyffier ,
Per-Gunnar Martinsson  and
Vladimir Rokhlin
Leslie Greengard
Affiliation:
Courant Instiute of Mathematical Sciences, New York University, New York, NY 10012, USAE-mail:greengard@courant.nyu.edu
Denis Gueyffier
Affiliation:
Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USAE-mail:dgueyffier@giss.nasa.gov
Per-Gunnar Martinsson
Affiliation:
Department of Applied Mathematics, University of Colorado at Boulder, 526 UCB, Boulder, CO 80309-0526, USAE-mail:per-gunnar.martinsson@colorado.edu
Vladimir Rokhlin
Affiliation:
Department of Mathematics and Department of Computer Science, Yale University, 10 Hillhouse Avenue, New Haven CT 06511, USAE-mail:rokhlin@cs.yale.edu
Get access Rights & Permissions [Opens in a new window]

Abstract

Methods for the solution of boundary integral equations have changed significantly during the last two decades. This is due, in part, to improvements in computer hardware, but more importantly, to the development of fast algorithms which scale linearly or nearly linearly with the number of degrees of freedom required. These methods are typically iterative, based on coupling fast matrix-vector multiplication routines with conjugate-gradient-type schemes. Here, we discuss methods that are currently under development for the fast, direct solution of boundary integral equations in three dimensions. After reviewing the mathematical foundations of such schemes, we illustrate their performance with some numerical examples, and discuss the potential impact of the overall approach in a variety of settings.

Type
Research Article
Information
Acta Numerica , Volume 18 , May 2009 , pp. 243 - 275
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alpert, B. and Rokhlin, V. (1991), ‘A fast algorithm for the evaluation of Legendre expansions’, SIAM J. Sci. Statist. Comput. 12, 158–179.CrossRefGoogle Scholar
Alpert, B., Beylkin, G., Coifman, R. and Rokhlin, V. (1993), ‘Wavelet-like bases for the fast solution of second-kind integral equations’, SIAM J. Sci. Comput. 14, 159–184.CrossRefGoogle Scholar
Altman, M. D., Bardhan, J. P., Tidor, B. and White, J. K. (2006), ‘FFTSVD: A fast multiscale boundary-element method solver suitable for bio-MEMS and biomolecule simulation’, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems 25, 274–284.CrossRefGoogle Scholar
Bardhan, J. P., Altman, M. D., Lippow, S. M., Tidor, B. and White, J. K. (2005), ‘A curved panel integration technique for molecular surfaces’, in Proc. NSTI–Nanotech 2005 Conf., Vol. 1, pp. 512–515.Google Scholar
Beylkin, G., Coifman, R. and Rokhlin, V. (1991), ‘Fast wavelet transforms and numerical algorithms I’, Comm. Pure Appl. Math. 14, 141–183.CrossRefGoogle Scholar
Boschitsch, A. H., Fenley, M. O. and Olson, W. K. (1999), ‘A fast adaptive multipole algorithm for calculating screened Coulomb (Yukawa) interactions’, J. Comput. Phys. 151, 212.CrossRefGoogle Scholar
Canning, F. X. and Rogovin, K. (1998), ‘Fast direct solution of standard moment-method matrices’, IEEE Antennas Propag. 40, 15–26.CrossRefGoogle Scholar
Carrier, J., Greengard, L. and Rokhlin, V. (1988), ‘A fast adaptive multipole algorithm for particle simulations’, SIAM J. Sci. Statist. Comput. 9, 669–686.CrossRefGoogle Scholar
Chandrasekaran, S., Dewilde, P., Gu, M., Lyons, W. and Pals, T. (2006), ‘A fast solver for HSS representations via sparse matrices’, SIAM J. Matrix Anal. Appl. 29, 67–81.CrossRefGoogle Scholar
Chen, Y. (2002). ‘Fast direct solver for the Lippman–Schwinger equation’, Adv. Comput. Math. 16, 175–190.CrossRefGoogle Scholar
Cheng, H., Gimbutas, Z., Martinsson, P. G. and Rokhlin, V. (2005), ‘On the compression of low rank matrices’, SIAM J. Sci. Comput. 26, 1389–1404.CrossRefGoogle Scholar
Chew, W. C. (1989). ‘An N 2 algorithm for the multiple scattering solution of N scatterers’, Micro. Opt. Tech. Lett. 2, 380–383.CrossRefGoogle Scholar
Chew, W. C., Jin, J.-M., Michielssen, E. and Song, J., editors (2001). Fast and Efficient Algorithms in Computational Electromagnetics, Artech House, Boston.Google Scholar
Cooley, J. W. and Tukey, J. W. (1965), ‘An algorithm for the machine calculation of complex Fourier series’, Math. Comput. 19, 297–301.CrossRefGoogle Scholar
Darve, E. and Have, P. (2004), ‘Fast multipole method for Maxwell equations stable at all frequencies’, Royal Soc. London, Trans. Ser. A 362, 603–628.CrossRefGoogle Scholar
Davis, M. E. and McCammon, J. A. (1990), ‘Electrostatics in biomolecular structure and dynamics’ Chem. Rev. 90, 509–521.CrossRefGoogle Scholar
Eidelman, Y. and Gohberg, I. (1999). ‘Linear complexity inversion algorithms for a class of structured matrices’, Integral Equations Operator Theory 35, 28–52.CrossRefGoogle Scholar
Gimbutas, Z. (1999), A generalized fast multipole method for non-oscillatory kernels. PhD Dissertation, Yale University.CrossRefGoogle Scholar
Gope, D., Chowdhury, I. and Jandhyala, V. (2005), ‘DiMES: Multilevel fast direct solver based on multipole expansions for parasitic extraction of massively coupled 3D microelectronic structures’, in Proc. 42nd Annual Conference on Design Automation, pp. 159–162.CrossRefGoogle Scholar
Goreinov, S. A., Yrtyshnikov, E. E. and Zamarashkin, N. L. (1997), ‘A theory of pseudoskeleton approximations’, Linear Algebra Appl. 261, 1–21.CrossRefGoogle Scholar
Gradshteyn, I. S. and Ryzhik, I. M. (2000), Table of Integrals, Series, and Products, Academic Press, New York.Google Scholar
Greengard, L. and Helsing, J. (1998), ‘On the numerical evaluation of elastostatic fields in locally isotropic two-dimensional composites’, J. Mech. Phys. Solids 46, 1441–1462.CrossRefGoogle Scholar
Greengard, L. and Rokhlin, V. (1987), ‘A fast algorithm for particle simulations’, J. Comput. Phys. 73, 325–348.CrossRefGoogle Scholar
Greengard, L. and Rokhlin, V. (1991), ‘On the numerical solution of two-point boundary value problems’, Comm. Pure Appl. Math. 44, 419–452.CrossRefGoogle Scholar
Greengard, L. and Rokhlin, V. (1997), A new version of the fast multipole method for the Laplace equation in three dimensions. In Acta Numerica, Vol. 6, Cambridge University Press, pp. 229–269.Google Scholar
Greengard, L. and Strain, J. (1991). ‘The Fast Gauss Transform’, SIAM J. Sci. Statist. Comput. 12, 79–94.CrossRefGoogle Scholar
Gu, M. and Eisenstat, S. C. (1996), ‘Efficient algorithms for computing a strong rank-revealing QR factorization’, SIAM J. Sci. Comput. 17, 848–869.CrossRefGoogle Scholar
Guenther, R. B. and Lee, J. W. (1988), Partial Differential Equations of Mathematical Physics and Integral Equations, Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Hackbusch, W. (1999), ‘A sparse matrix arithmetic based on H-matrices I: Introduction to H-matrices’, Computing 62, 89–108.CrossRefGoogle Scholar
Hackbusch, W. and Khoromskij, B. N. (2000), ‘A sparse H-matrix arithmetic II: Application to multi-dimensional problems’, Computing 64, 21–47.CrossRefGoogle Scholar
Hackbusch, W. and Nowak, Z. P. (1989), ‘On the fast matrix multiplication in the boundary element method by panel clustering’, Numer. Math. 54, 463–491.CrossRefGoogle Scholar
Holst, M. J., Baker, N. A. and Wang, F. (2000), ‘Adaptive multilevel finite element solution of the Poisson–Boltzmann equation I: Algorithms and examples’, J. Comput. Chem. 21, 1319–1342.3.0.CO;2-8>CrossRefGoogle Scholar
Huang, J. and Greengard, L. (2002), ‘A new version of the fast multipole method for screened Coulomb interactions interactions in three dimensions’, J. Comput. Phys. 180, 642–658.Google Scholar
James, D. L. and Pai, D. K. (1999), ‘ArtDefo: Accurate real time deformable objects’, in Proc. SIGGRAPH 99, pp. 65–72.CrossRefGoogle Scholar
Kapur, S. and Long, D. (1997), ‘IES 3: A fast integral equation solver for efficient 3-D extraction’, in Proc. IEEE International Conference on Computer Aided Design, pp. 448–455.Google Scholar
Kastner, R. (1989), ‘An ‘add-on method’ for the analysis of scattering from large planar structures’, IEEE Trans. Antennas Propag. 37, 353–361.CrossRefGoogle Scholar
Kuo, S. S., Altman, M. D., Bardhan, J. P., Tidor, B. and White, J. K. (2002), ‘Fast methods for simulation of biomolecular electrostatics’, in Proc. IEEE–ACM Int. Conf. Comput. Aided Design, pp. 466–473.Google Scholar
Lee, J.-Y. and Greengard, L. (1997), ‘A fast adaptive numerical method for stiff two-point boundary value problems’, SIAM J. Sci. Comput. 18, 403–429.CrossRefGoogle Scholar
Liang, J. and Subramaniam, S. (1997), ‘Computation of molecular electrostatics with boundary element methods’, Biophys. J. 73, 1830.CrossRefGoogle ScholarPubMed
Lu, B., Cheng, X., Huang, J. and McCammon, J. A. (2006), ‘Order N algorithm for computation of electrostatic interactions in biomolecular systems’, Proc. Nat. Acad. Sci. 103, 19314–19319.CrossRefGoogle ScholarPubMed
Marshall, S. A., Vizcarra, C. L. and Mayo, S. L. (2005), ‘One- and two-body decomposable Poisson–Boltzmann methods for protein design calculations’, Protein Science 14, 1293–1304.CrossRefGoogle ScholarPubMed
Martinsson, P.-G. (2006), ‘Fast evaluation of electrostatic interactions in multiphase dielectric media’, J. Comput. Phys. 211, 289–299.CrossRefGoogle Scholar
Martinsson, P.-G. and Rokhlin, V. (2005), ‘A fast direct solver for boundary integral equations in two dimensions’, J. Comput. Phys. 205, 1–23.CrossRefGoogle Scholar
Martinsson, P.-G. and Rokhlin, V. (2007), ‘A fast direct solver for scattering problems involving elongated structures’, J. Comput. Phys. 221, 288–302.CrossRefGoogle Scholar
Michielssen, E., Boag, A. and Chew, W. C. (1996), ‘Scattering from elongated objects: Direct solution in O(N log2N) operations’, IEEE Proc. H 143, 277–283.Google Scholar
Nabors, K. and White, J. (1991), ‘FASTCAP: A multipole accelerated 3-D capacitance extraction program’, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems 10, 1447–1459.CrossRefGoogle Scholar
Nishimura, N. (2002), ‘Fast multipole accelerated boundary integral equation methods’, Appl. Mech. Rev. 55, 299–324.CrossRefGoogle Scholar
Pals, T. (2004), Multipole for scattering computations: Spectral discretization, stabilization, fast solvers. PhD Dissertation, Department of Electrical and Computer Engineering, University of California, Santa Barbara.Google Scholar
Phillips, J. R. and White, J. (1997), ‘A precorrected-FFT method for electrostatic analysis of complicated 3-D structures’, IEEE Trans. Computer-Aided Design 16, 1059–1072.CrossRefGoogle Scholar
Rocchia, W., Sridharan, S., Nicholls, A., Alexov, E., Chiabrera, A. and Honig, B. (2002), ‘Rapid grid-based construction of the molecular surface for both molecules and geometric objects: Applications to the finite difference Poisson–Boltzmann method’, J. Comput. Chem. 23, 128–137.CrossRefGoogle Scholar
Rokhlin, V. (1985), ‘Rapid solution of integral equations of classical potential theory’, J. Comput. Phys. 60, 187–207.CrossRefGoogle Scholar
Rokhlin, V. (1988), ‘A fast algorithm for the discrete Laplace transformation’, J. Complexity 4, 12–32.CrossRefGoogle Scholar
Saad, Y. and Schultz, M. H. (1986), ‘GMRES: A generalized minimum residual algorithm for solving nonsymmetric linear systems’, SIAM J. Sci. Statist. Comput. 7, 856–869.CrossRefGoogle Scholar
Sharp, K. A. and Honig, B. (1990), ‘Electrostatic interactions in macromolecules: Theory and applications’, Ann. Rev. Biophys. Biophys. Chem. 19, 301–332.CrossRefGoogle ScholarPubMed
Sherman, J. and Morrison, W. J. (1949), ‘Adjustment of an inverse matrix corresponding to changes in the elements of a given column or a given row of the original matrix’, Ann. Math. Statist. 20, 621.Google Scholar
Starr, P. and Rokhlin, V. (1994). ‘On the numerical solution of two-point boundary value problems II’, Comm. Pure Appl. Math. 47, 1117–1159.CrossRefGoogle Scholar
Strain, J. (1992), ‘The fast Laplace transform based on Laguerre functions’, Math. Comp. 58, 275–284.CrossRefGoogle Scholar
Woodbury, M. A. (1950), Inverting modified matrices. Memorandum Report 42, Statistical Research Group, Princeton University.Google Scholar
Ying, L., Biros, G., Zorin, D. and Langston, M. H. (2003), ‘A new parallel kernel-independent fast multipole method’, in Proc. ACM/IEEE Conf. on Supercomp., p. 14.Google Scholar
Zhu, Z. and White, J. K. (2005), ‘FastSies: A fast stochastic integral equation solver for modeling the rough surface effect’, in Proc. 2005 IEEE/ACM Int. Conference on Computer-Aided Design, pp. 675–682.Google Scholar