A method of massively parallel computation on supercomputers has been developed to facilitate numerical simulation of electromagnetic fields in the vicinities of electrically large and complex radiating and scattering objects. In this method as in methods developed previously for the same purpose, Maxwell’s equations are solved by use of finite-difference approximations in both space and time. However, unlike in the other methods, this method is not limited to implicit (and thus parallel) solution in space with explicit (and thus sequential) time stepping with small time steps to ensure numerical stability. Instead, this method provides for parallel solution for all time steps, and the time steps can be larger and thus fewer — this characteristic is often characterized in the literature as “coarse-grained parallelism.”

Computations for all M Time Steps in a numerical simulation of spatially complex, time-dependent electromagnetic field are performed in parallel.
This method follows an approach that combines the fully implicit Crank-Nicolson time-stepping method with a massive degree of parallelism in computation. This approach enables the application of fully implicit techniques; in comparison with explicit techniques, implicit techniques exhibit superior numerical properties (principally, unconditional stability) while also providing optimal efficiency for parallel computation. The time-parallel algorithm in this method imposes relatively simple requirements for communication and synchronization among different processors; this characteristic in combination with coarsegrained parallelism, makes for highly efficient implementation on emerging massively parallel multiple-instruction, multiple-data computers.

The basic equation of the method is obtained by applying the Crank-Nicolson method to the second-order inhomogeneous linear recursion (SOILR) equation of the finite-difference formulation of the Maxwell’s equations. The resulting form of the basic equation is

(IM)ψ(m+1) = 2(m) - (I - αM)

ψ(m-1) + f (m+1) for 1 < m < M - 1

where I is the identity matrix, α is a constant, M is an N × N matrix that arises from the spatial discretization of the Laplacian operator in Maxwell’s equations, ψ(m) denotes the solution (a vector that represents the electromagnetic-field quantity of interest) at the mth time step, and f(m) denotes the time- and space-discretized source term for initial and boundary conditions at the mth time step. The eigenvalue/ eigenvector decomposition of M is given by M = ΘΛΘ–1, where Θ is the set of eigenvectors and Λ is a diagonal matrix that represents the set of eigenvalues of M.

Let there be a diagonal matrix

S = (I - αΛ)-1.

Let

ψ(m-1) + f (m+1) for 1 < m < M - 1

Then it can be shown that the basic equation can be put in the form

Unlike the basic SOILR equation as formulated in the preceding paragraph, this SOILR equation is diagonalized and can therefore be solved efficiently by use of either of two parallel-computation algorithms called the Recursive Doubling Algorithm (RDA) or the Cyclic Reduction Algorithm (CRA). For two- and three-dimensional problems, this SOILR equation can be solved in O(N2 logM) and O(N3 logM), respectively, on M processors, where O(x) denotes an amount of computing time or a number of arithmetic operations proportional to a number of the order of x.

The figure illustrates the time-parallel algorithm, which is divided into four steps. Step 1 involves determination of the eigenvalue/eigenvector decomposition of M and the computation of S. In step 2, the source vectors f(m) are computed and multiplied by SΘ–1 to obtain f~(m). The parallel computation to solve the diagonalized form of the basic SOILR equation is performed in step 3, yielding the vectors ψ∼(m). The desired solution vectors are computed in step 4 by matrix·vector multiplication; namely,

This work was done by Amir Fijany, Michael A. Jensen, Yahya Rahmat-Samii, and Jacob Barhen of Caltech for NASA’s Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.nasatech.com  under the Information Sciences category. NPO-19453