A multilevel multipole-free algorithm is presented for solving electromagnetic scattering problems in the vicinity of a half space or layered medium. By replacing the multipole expansion in the fast inhomogeneous plane wave algorithm (FIPWA) with a multipole-free expansion, this new algorithm is simpler to derive and retains O (N log N) scaling in memory and processing time. To develop this new algorithm, known as the multipole-free fast inhomogeneous plane wave algorithm (MF-FIPWA), error control is established for arbitrary accuracy.; In addition, comparison of the memory usage and simulation time is presented for FIPWA and MF-FIPWA for moderate to large scale problems. Various alternate approaches to implementing MF-FIPWA are discussed in terms of how the fast algorithms set up translation matrices and where gains can be made. Finally, details of the advantages of using nonuniform sampling are provided. Results show 30% savings in memory usage and up to 20% savings in computing the matrix-vector product. |