Hostname: page-component-7c8c6479df-ph5wq Total loading time: 0 Render date: 2024-03-19T14:02:46.331Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  08 May 2009

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

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
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, 158179.Google 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, 159184.Google 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, 274284.Google 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. 512515.Google Scholar
Beylkin, G., Coifman, R. and Rokhlin, V. (1991), ‘Fast wavelet transforms and numerical algorithms I’, Comm. Pure Appl. Math. 14, 141183.Google 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.Google Scholar
Canning, F. X. and Rogovin, K. (1998), ‘Fast direct solution of standard moment-method matrices’, IEEE Antennas Propag. 40, 1526.Google Scholar
Carrier, J., Greengard, L. and Rokhlin, V. (1988), ‘A fast adaptive multipole algorithm for particle simulations’, SIAM J. Sci. Statist. Comput. 9, 669686.Google 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, 6781.Google Scholar
Chen, Y. (2002). ‘Fast direct solver for the Lippman–Schwinger equation’, Adv. Comput. Math. 16, 175190.Google Scholar
Cheng, H., Gimbutas, Z., Martinsson, P. G. and Rokhlin, V. (2005), ‘On the compression of low rank matrices’, SIAM J. Sci. Comput. 26, 13891404.Google Scholar
Chew, W. C. (1989). ‘An N 2 algorithm for the multiple scattering solution of N scatterers’, Micro. Opt. Tech. Lett. 2, 380383.Google 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, 297301.Google Scholar
Darve, E. and Have, P. (2004), ‘Fast multipole method for Maxwell equations stable at all frequencies’, Royal Soc. London, Trans. Ser. A 362, 603628.Google Scholar
Davis, M. E. and McCammon, J. A. (1990), ‘Electrostatics in biomolecular structure and dynamicsChem. Rev. 90, 509521.Google Scholar
Eidelman, Y. and Gohberg, I. (1999). ‘Linear complexity inversion algorithms for a class of structured matrices’, Integral Equations Operator Theory 35, 2852.Google Scholar
Gimbutas, Z. (1999), A generalized fast multipole method for non-oscillatory kernels. PhD Dissertation, Yale University.Google 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. 159162.Google Scholar
Goreinov, S. A., Yrtyshnikov, E. E. and Zamarashkin, N. L. (1997), ‘A theory of pseudoskeleton approximations’, Linear Algebra Appl. 261, 121.Google 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, 14411462.Google Scholar
Greengard, L. and Rokhlin, V. (1987), ‘A fast algorithm for particle simulations’, J. Comput. Phys. 73, 325348.Google Scholar
Greengard, L. and Rokhlin, V. (1991), ‘On the numerical solution of two-point boundary value problems’, Comm. Pure Appl. Math. 44, 419452.Google 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. 229269.Google Scholar
Greengard, L. and Strain, J. (1991). ‘The Fast Gauss Transform’, SIAM J. Sci. Statist. Comput. 12, 7994.Google Scholar
Gu, M. and Eisenstat, S. C. (1996), ‘Efficient algorithms for computing a strong rank-revealing QR factorization’, SIAM J. Sci. Comput. 17, 848869.Google 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, 89108.Google Scholar
Hackbusch, W. and Khoromskij, B. N. (2000), ‘A sparse H-matrix arithmetic II: Application to multi-dimensional problems’, Computing 64, 2147.Google Scholar
Hackbusch, W. and Nowak, Z. P. (1989), ‘On the fast matrix multiplication in the boundary element method by panel clustering’, Numer. Math. 54, 463491.Google 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, 13191342.Google 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, 642658.Google Scholar
James, D. L. and Pai, D. K. (1999), ‘ArtDefo: Accurate real time deformable objects’, in Proc. SIGGRAPH 99, pp. 6572.Google 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. 448455.Google Scholar
Kastner, R. (1989), ‘An ‘add-on method’ for the analysis of scattering from large planar structures’, IEEE Trans. Antennas Propag. 37, 353361.Google 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. 466473.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, 403429.Google Scholar
Liang, J. and Subramaniam, S. (1997), ‘Computation of molecular electrostatics with boundary element methods’, Biophys. J. 73, 1830.Google Scholar
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, 1931419319.Google Scholar
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, 12931304.Google Scholar
Martinsson, P.-G. (2006), ‘Fast evaluation of electrostatic interactions in multiphase dielectric media’, J. Comput. Phys. 211, 289299.Google Scholar
Martinsson, P.-G. and Rokhlin, V. (2005), ‘A fast direct solver for boundary integral equations in two dimensions’, J. Comput. Phys. 205, 123.Google Scholar
Martinsson, P.-G. and Rokhlin, V. (2007), ‘A fast direct solver for scattering problems involving elongated structures’, J. Comput. Phys. 221, 288302.Google 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, 277283.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, 14471459.Google Scholar
Nishimura, N. (2002), ‘Fast multipole accelerated boundary integral equation methods’, Appl. Mech. Rev. 55, 299324.Google 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, 10591072.Google 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, 128137.Google Scholar
Rokhlin, V. (1985), ‘Rapid solution of integral equations of classical potential theory’, J. Comput. Phys. 60, 187207.Google Scholar
Rokhlin, V. (1988), ‘A fast algorithm for the discrete Laplace transformation’, J. Complexity 4, 1232.Google 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, 856869.Google Scholar
Sharp, K. A. and Honig, B. (1990), ‘Electrostatic interactions in macromolecules: Theory and applications’, Ann. Rev. Biophys. Biophys. Chem. 19, 301332.Google Scholar
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, 11171159.Google Scholar
Strain, J. (1992), ‘The fast Laplace transform based on Laguerre functions’, Math. Comp. 58, 275284.Google 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. 675682.Google Scholar