Solving impossible equations

Eric Michielssen, professor of Electrical and Computer Engineering, has received the Sergei A. Schelkunoff Transactions Prize Paper Award for research impacting the ability to rapidly analyze electromagnetic phenomena.

This award is presented to the authors of the best paper published in the IEEE Transactions on Antennas and Propagation during the previous year.

The 2017 paper, “A Butterfly-Based Direct Integral-Equation Solver Using Hierarchical LU Factorization for Analyzing Scattering From Electrically Large Conducting Objects,“ co-authored by Han Guo (ECE doctoral student), Yang Liu (MSE PHD, EE, 2013 2015; Lawrence Berkeley National Lab), and Prof. Jun Hu (UESTC), describes a new algorithm for solving Maxwell’s equations that is orders of magnitude faster than prior algorithms, opening the door to its use for the design and optimization of electromagnetic devices.

Maxwell’s equations are a set of four partial differential equations published in 1865 that scientifically explained light, electricity, and magnetism for the first time. Called the “second great unification in physics,” these equations continue to hold the key to advancements in a wide array of applications, in particular high-frequency electronic devices and systems, and optics.

To solve Maxwell’s equations, Michielssen and his group convert them into a system of linear equations. In the last 2 decades, the number of unknowns in these linear equations has increased from about 100K to tens of millions.

“Just writing out these equations by hand would require a sheet of paper the size of the United States,” says Michielssen. “Using traditional methods, not even a suite of high-performance computers would be able to solve a matrix of this size.”

That is, until Michielssen revisited an algorithm that he developed back in 1996. This algorithm, which came to be known as Butterfly because of its resemblance to the Fast Fourier transform, was able to compress a system of linear equations. Michielssen originally used the algorithm to efficiently store systems of equations in computer memory.

At the time, a scheme for using the butterfly compression scheme to actually solve the equations remained elusive, thus limiting the practical applicability of the method.

However, that all changed when Michielssen and his co-workers adapted his old Butterfly compression scheme to directly solve highly complex equations quickly and efficiently.

The solution scheme is remarkably similar to the old tried and true method of Gaussian elimination for solving linear systems of equations by eliminating unknowns, a simple concept taught in most high schools.

“Now that we can rapidly analyze devices,” said Michielssen, “we’re asking ourselves – how can we optimize and synthesize them. That’s the next step. That means you have to do these equations over and over again – and that changes the game.”

And this is where the new method is expected to really shine.

Traditional techniques for analyzing electromagnetic phenomena rely on indirect, iterative solution methods that are notoriously expensive in terms of computational resources as well as time when used in optimization settings. In contrast, Michielssen’s method, rooted in Gaussian elimination, can be applied rapidly to problems that require the repeated solution of perturbed (ie, slightly altered) equations, a situation that naturally arises when synthesizing the shape or material composition of a device.

“Our butterfly scheme has blown new life into direct solution methods for Maxwell’s equations,” Michielssen said.  “For many real-world problems out there, our Butterfly method is orders of magnitude faster than prior algorithms, while using fewer computing resources.”

Michielssen’s approach is applicable anywhere you need to solve Maxwell’s equations. While he has used it primarily for radar cross section, the same technique can be used for antenna design, wireless system analysis, monitoring signal integrity, as well as high-frequency terahertz and imaging systems.

The calculations were done on the FLUX high-performance computing cluster at Michigan.

“This research would not have been possible without the vast computing resources available here at Michigan,” said Michielssen.

Michielssen, Louise Ganiard Johnson Professor of Engineering, is a Professor of Electrical Engineering & Computer Science, Associate Vice President for Advanced Research Computing, and Co-Director of the Precision Health Initiative. He is also Editor-in-Chief of the International Journal of Numerical Modelling, Electronic Networks, Devices, and Fields.