NCSA NEWS

Faster Algorithm Brings New Breakthroughs in Electromagnetic Simulations

released July 11, 2001

 

Contact
Karen Green
NCSA Public Information Officer
kareng@ncsa.uiuc.edu
217.265.0748 phone
217.244.7396 fax

CHAMPAIGN, IL — Researchers at the Center for Computational Electromagnetics at the University of Illinois at Urbana-Champaign have developed an algorithm to solve complex electromagnetic problems that is eight times faster than the previous fastest algorithm, a feat that will impact the analysis of electromagnetic scattering and allow complex real-world problems to be solved using computer simulations.

This is the latest of three years of breakthrough simulations the center has achieved using supercomputers at the U of I's National Center for Supercomputing Applications (NCSA).

Weng Cho Chew, a professor of electrical and computer engineering at the U of I, and Research Scientist Sanjay Velamparambil used a 128-processor SGI Origin2000 supercomputer at NCSA to compute electromagnetic scattering from a full-size aircraft at a frequency of 8 gigahertz. The simulation involved nearly 10.2 million unknown variables. The research is funded by the U. S. Air Force Office of Scientific Research through the Multidisciplinary Research Program of the University Research Initiative (MURI).

Electromagnetic scattering refers to how electromagnetic waves (microwaves in this instance) are scattered when they come in contact with an object—in this case an airplane. Scattering affects information that can be obtained about the size, shape, and speed of the object. The algorithm developed by Chew's group greatly speeds up the solution of integral equations that arise in analyzing scattering and radiation problems. Their technique can be applied to many areas of electrical engineering, including the design of high-speed electronic circuits and the creation of high-resolution radar cross-sections.

Three years ago, Chew's simulations could handle about 2 million unknowns. Further refinements to the code about a year ago allowed the team to solve problems with more than 9 million variables. The importance of this latest simulation in the wake of the center's previous achievements is in the technology used. The current simulation uses a new massively parallel computer code called ScaleME (Scalable Multipole Engine) and a methodology known as message passing, which harnesses the latent power of a massively parallel computer.

Developing a scalable, parallel algorithm using message passing is a challenge with numerous bottlenecks. Chew and his associates came up with practical solutions to many of these bottlenecks and developed a core algorithm that is more than eight times faster than previous algorithms. This makes ScaleME the fastest algorithm to date used in electromagnetic scattering research.

Although the current simulation is done on a supercomputer, ScaleME is highly portable and works equally well on a variety of parallel computers, including low-cost Linux clusters built from off-the-shelf components. This fact will allow a larger number of users, often with limited budgets, to do large-scale simulations.

"The power of today's supercomputers will be available on the desktop machines of tomorrow, and solving 10 million unknowns will be a routine task with this kind of technology," Chew said. "The rapid improvements in computational algorithms, amplified by the leaps-and-bounds progress in computer technology, will alter how scientific studies and engineering designs will be done in the future—more work will be done in the virtual world rather than in real laboratories," he added.

Velamparambil, the principal architect of ScaleME, said, "Solving electromagnetic problems is very different from solving electrostatic problems, because electromagnetic interaction is very long range, while electrostatic interaction is short range. Consequently, a naïve approach to parallelizing the code incurs large communication-cost overhead, which has to be removed by careful algorithm redesign."

Armed with the experience gained from these breakthrough simulations, Chew and his team are currently working on electromagnetic scattering problems involving larger aircrafts. That means solving even larger problems with more complexities and more intricate details.

Chew and Velamparambil acknowledged John Towns, director of NCSA's Scientific Computing division, for providing the help needed to make these large-scale simulations possible. Additional help was provided by NCSA's Wayne Louis Hoyenga, Melissa Johnson, and Scott Koranda.

The National Center for Supercomputing Applications is the leading-edge site for the National Computational Science Alliance. NCSA is a leader in the development and deployment of cutting-edge high-performance computing, networking, and information technologies. The National Science Foundation, the state of Illinois, the University of Illinois, industrial partners, and other federal agencies fund NCSA.

The National Computational Science Alliance is a partnership to prototype an advanced computational infrastructure for the 21st century and includes more than 50 academic, government and industry research partners from across the United States. The Alliance is one of two partnerships funded by the National Science Foundation's Partnerships for Advanced Computational Infrastructure (PACI) program, and receives cost-sharing at partner institutions. NSF also supports the National Partnership for Advanced Computational Infrastructure (NPACI), led by the San Diego Supercomputer Center.

 

Releases Archive