[ Search | Site Map | Contact ]

Center for Scientific Computation and Mathematical Modeling

Research Activities > Programs > Fast Approximate Algorithms > Weng Chew

Fast Multipole Method, Tree-Code and Related Approximate Algorithms.
Trading Exactness for Efficiency.

CSIC Building (#406), Seminar Room 4122.
Directions: home.cscamm.umd.edu/directions

Review of Some Fast Algorithms for Electromagnetic Scattering

Dr. Weng Chew

Center for Computational Electromagnetics and Electromagnetics Laboratory
Department of Electrical and Computer Engineering
University of Illinois

Abstract:   In this talk, we will review the multilevel fast multipole algorithm for solving electrodynamic problems, the fast inhomogeneous plane wave algorithm for solving problems in layered media, as well as the low-frequency multilevel fast multipole algorithm for solving problems in the “twilight zone” between the solutions of Laplace’s equation and Helmholtz equation. Traditionally, integral equation solvers applied to these problems yield dense matrices limiting problem sizes to about tens of thousands of unknowns.

The electrodynamic problem is a Helmholtz-type problem, and the information content in the far field does not diminish with distance as in the case of Laplace-type problems. This gives rise to communication bottleneck when the multilevel fast multipole algorithm is parallelized on a massively parallel computers that does not happen when the parallelization of a Laplace or Poisson solver is involved. We will discuss ways to overcome this communication bottleneck when ultra-large scale problems are solved on massively parallel computers. A problem with up to 20 million unknowns have been solved with such a parallelized code representing a three order of magnitude improvement over traditional solvers.

The generalization of the fast multipole algorithm to layered medium is not straightforward, but can be achieved by the use of the fast inhomogeneous algorithm. This algorithm diagonalizes the translator by the use of Sommerfeld-Weyl integrals for which layered medium effect can be easily added. We will describe the diagonlization of the translator for layered medium Green’s function. Problems involving layered media with over 1 million unknowns can be solved representing a two order of magnitude improvement over traditional solvers.

Lastly, in the “twilight zone” between electrodynamics and electrostatics, most algorithms suffer from low-frequency breakdown, including the method of moments. Ways to overcome this low-frequency breakdown will be discussed, and some examples with one million unknowns will be shown, representing a two orders of magnitude improvement over traditional solvers in this area.