An $O(N^{3})$ Algorithm for the Calculation of Far Field Radiation Patterns

We present a new method for computing the near-to-far-field (NTFF) transformation in finite-difference time-domain simulations which has an overall scaling of $O(N^{3})$ instead of the standard $O(N^{4})$ . By mapping the far field with a cartesian coordinate system, the 2-D surface integral can be split into two successive 1-D integrals. For a near field spanned by $N_{X}\times N_{Y}$ discrete sample points, and a far field spanned by $N_{\theta}\times N_{\phi}$ points, the NTFF calculation can then be performed in $O(N_{\theta}N_{X}N_{Y})+O(N_{\theta}N_{\phi}N_{Y})$ operations instead of $O(N_{\theta}N_{\phi}N_{X}N_{Y})$ .