Source-linked AI summary
Fundamental Schemes for Efficient Unconditionally Stable Implicit Finite-Difference Time-Domain Methods
Eng Leong Tan
TL;DR
Efficient unconditionally stable implicit FDTD methods need simpler formulations than conventional schemes while retaining their stability advantages. The paper develops generalized fundamental schemes with matrix-operator-free right-hand sides and compares original and new implementations. The new implementations substantially reduce computation costs, including a 1.83 overall flops-count efficiency gain over conventional ADI-FDTD for several schemes.
Problem
Explicit FDTD is constrained by the CFL condition, while implicit FDTD methods require more efficient and simpler formulations.
Method
The paper reformulates ADI, LOD, split-step, and other implicit schemes as fundamental schemes using generalized matrix operator equations and matrix-operator-free right-hand sides.
Results
1.83 overall efficiency gain in flops count reduction over conventional ADI-FDTD is achieved by the new ADI, LOD1/SS1, and LOD2 implementations after tridiagonal-solve costs are included.
Takeaways & Limitations
Fundamental updating structures provide a basis and benchmark for simplifying and improving implementations of implicit schemes.
Abstract
from arXiv · showhide
This paper presents the generalized formulations of fundamental schemes for efficient unconditionally stable implicit finite-difference time-domain (FDTD) methods. The fundamental schemes constitute a family of implicit schemes that feature similar fundamental updating structures, which are in simplest forms with most efficient right-hand sides. The formulations of fundamental schemes are presented in terms of generalized matrix operator equations pertaining to some classical splitting formulae, including those of alternating direction implicit, locally one-dimensional and split-step schemes. To provide further insights into the implications and significance of fundamental schemes, the analyses are also extended to many other schemes with distinctive splitting formulae. Detailed algorithms are described for new efficient implementations of the unconditionally stable implicit FDTD methods based on the fundamental schemes. A comparative study of various implicit schemes in their original and new implementations is carried out, which includes comparisons of their computation costs and efficiency gains.
I. INTRODUCTION
The paper motivates efficient unconditionally stable implicit FDTD methods by the CFL-limited efficiency of explicit FDTD and the complexity of existing implicit schemes. It introduces fundamental schemes as simplified formulations intended to reduce computational work and implementation complexity.
- I. INTRODUCTION: Explicit FDTD efficiency is restricted by the CFL condition, which limits the time step according to spatial mesh sizes.
- I. INTRODUCTION: ADI-FDTD removes the CFL condition, prompting renewed interest in unconditionally stable implicit FDTD schemes.
- I. INTRODUCTION: ADI, LOD, Crank-Nicolson, and split-step approaches are classical implicit schemes adapted for FDTD solutions of Maxwell's equations.
- I. INTRODUCTION: Recent efforts seek stable methods that are more efficient and simpler to implement than existing schemes.
- I. INTRODUCTION: The paper formulates fundamental schemes using generalized matrix operator equations associated with ADI, LOD, and split-step splitting formulae.
- I. INTRODUCTION: The proposed reformulations use matrix-operator-free right-hand sides with fewer terms, supporting coding simplification and reduced computation costs.
A. ADI
The ADI formulation is recast using auxiliary variables and simplified updating equations. The resulting implementation preserves equivalence while providing matrix-operator-free right-hand sides and direct efficiency benefits.
- A. ADI: ADI is based on generalized splitting formulae whose matrix operators must be chosen appropriately for the particular scheme.
- A. ADI: Auxiliary variables allow the original ADI algorithm to be reduced into a more efficient implementation.
- A. ADI: The reduced algorithm proceeds with transformed field variables during main iterations and retrieves field data only when output is required.
- A. ADI: Equations (8a)-(8d) provide an ADI scheme with simplest right-hand sides that contain no explicit matrix operator.
- A. ADI: The nonzero-initial-field implementation requires input initialization, but that initialization does not degrade accuracy because it is equivalent to the original scheme's initial-step relations.
B. LOD1/SS1
The LOD1/SS1 formulation is simplified through auxiliary variables into updating equations with matrix-operator-free right-hand sides. Its output field solution is directly available without special initialization.
- B. LOD1/SS1: LOD and split-step schemes use generalized splitting formulae, and when A and B do not commute their LOD1 and SS1 forms are first-order accurate in time.
- B. LOD1/SS1: The original LOD scheme can be reformulated into a simplest form with matrix-operator-free right-hand sides.
- B. LOD1/SS1: The reformulated equations use auxiliary and field variables to simplify the implementation.
- B. LOD1/SS1: The output field solution is directly available from the final update, and no special input initialization is required.
C. SS2
SS2 extends the split-step approach to second-order temporal accuracy through Strang splitting and three updating procedures. Its simplified right-hand sides improve implementation efficiency, but three implicit equations retain additional arithmetic cost.
- C. SS2: SS2 is a second-order split-step scheme based on Strang splitting formulae.
- C. SS2: The SS2 algorithm involves three updating procedures.
- C. SS2: SS2 can be implemented with matrix-operator-free right-hand sides, simplifying the updating equations.
- C. SS2: Because SS2 contains three implicit equations, it requires more arithmetic operations than schemes with two implicit equations.
D. LOD2
LOD2 preserves second-order temporal accuracy without the non-commutativity error and supports efficient, parallelizable output processing. Its simplified implementation uses matrix-operator-free right-hand sides comparable to the most efficient fundamental ADI scheme.
- D. LOD2: LOD2 avoids the non-commutativity error while preserving second-order temporal accuracy.Its time indices advance through fractional steps rather than only integer time levels.
- D. LOD2: Input processing is performed once at initialization, while output processing can run independently in parallel.Output processing need not disrupt the main iterations and can be reduced or infrequent when only selected fields or observation points are needed.
- D. LOD2: LOD2 has been found more efficient than ADI and SS2 in their original implementations.The efficiency advantage is associated with parallel, reduced, and infrequent output processing.
- D. LOD2: Equations (21a)-(21d) provide the most efficient LOD2 form with matrix-operator-free right-hand sides.This form is comparable to the most efficient ADI scheme in equations (8a)-(8d).
E. Fundamental Implications and Significance
The paper identifies a common fundamental structure across several implicit schemes: implicit updates with simple matrix-operator-free right-hand sides and explicit subtraction of vectors. This structure clarifies links among ADI, LOD, split-step, and other splitting schemes, while efficiency gains remain implementation-dependent.
- E. Fundamental Implications and Significance: Fundamental implementations share implicit updates with matrix-operator-free right-hand sides and explicit updates formed by subtracting two vectors.Schemes mainly differ in the ordering of implicit and explicit updates, with transformations possible through initialization and variable-role swaps.
- E. Fundamental Implications and Significance: The shared updating structure makes the link between LOD and ADI schemes particularly apparent through auxiliary variables.Proper initialization can make corresponding LOD and ADI field solutions equivalent.
- E. Fundamental Implications and Significance: D’Yakonov, delta-formulation, and Crank-Nicolson direct-splitting schemes can also be cast into the simplest fundamental form.The paper illustrates reductions of generalized D’Yakonov or Beam-Warming and Douglas-Gunn or delta formulations.
- E. Fundamental Implications and Significance: The fundamental scheme structure supports simplified higher-order split-step algorithms and a simpler Crank-Nicolson algorithm.These algorithms follow the same matrix-operator-free-right-hand-side pattern.
- E. Fundamental Implications and Significance: The extent of simplification and computation-efficiency improvement depends strongly on the particular matrix operators and implementation details.The paper’s primary scope is unconditionally stable implicit FDTD methods in electromagnetics, although extensions to other finite-difference schemes are noted.
III. EFFICIENT IMPLEMENTATIONS
The paper specializes the fundamental schemes to lossless isotropic Maxwell media by selecting splitting matrix operators and expressing field and auxiliary variables componentwise. These choices establish the basis for concrete efficient FDTD implementations.
- III. EFFICIENT IMPLEMENTATIONS: For a lossless isotropic medium, the implementation uses permittivity, permeability, and selected splitting matrix operators for Maxwell’s equations.The operators are constructed from spatial difference operators for the x, y, and z first derivatives.
- III. EFFICIENT IMPLEMENTATIONS: Field and auxiliary variables are written in vector-component form to support the implementation algorithms.The paper also introduces dedicated notations for the subsequent update equations.
A. ADI
The ADI implementation applies the fundamental scheme through direct, implicit, and explicit updates, with implementation choices that can reduce operations. For second-order central differences on Yee cells, the resulting equations correspond to the reported efficient ADI-FDTD algorithm.
- A. ADI: Equation (8a) is implemented directly, while subsequent ADI equations combine direct, implicit, and explicit updating forms.The same pattern applies to equations (8c) and (8d).
- A. ADI: Rescaling variables and coefficients saves the scaling otherwise needed for the final magnetic-field solution.Additional operation savings can result from combining selected updating equations.
- A. ADI: When final magnetic-field data is not needed frequently, selected updates can be combined for higher efficiency.This optimization targets workflows with infrequent output of final magnetic-field data.
- A. ADI: Detailed implementation choices include for-looping, tridiagonal solving, memory reuse, variable scaling, and difference-operator selection.The paper notes that these choices leave room for further implementation variation and efficiency exploration.
B. LOD2
The fundamental LOD2 implementation is developed through implicit and explicit updating equations, operator choices, loop consolidation, and memory reuse. Related LOD1/SS1 and SS2 algorithms follow the same formulation-based approach.
- B. LOD2: The LOD2 scheme is expanded into implicit updating procedures using the notations associated with its governing equations.The implementation discussion separately addresses equation (21a) and equation (21c).
- B. LOD2: Second-order central-differencing operators on Yee cells are selected for the detailed implementation.The operators are chosen to specify the next algorithmic discussion.
- B. LOD2: Some updating equations are combined within the same loops to minimize the number of for-loops.When auxiliary magnetic variables are not output, additional explicit updates can also be combined.
- B. LOD2: Variable memory spaces can be reused, including absorbing hξ spaces into Hξ spaces when applicable.Variables grouped by coordinate may share storage and successive assignments can reuse their names.
- B. LOD2: Detailed algorithms for fundamental LOD1/SS1 and SS2 schemes can be written by referring to their corresponding formulations.The text points to equations (15) and (17) as the references for these algorithms.
IV. DISCUSSIONS AND COMPARISONS
The paper compares original and new implementations of several unconditionally stable implicit FDTD schemes using operation counts, loop counts, and temporal accuracy. New implementations substantially reduce right-hand-side computation costs while retaining measurable overall efficiency gains after tridiagonal-solver costs are included.
- IV. DISCUSSIONS AND COMPARISONS: The comparison evaluates computation-efficiency gains of new implementations against original schemes, especially the conventional ADI-FDTD implementation.The study is intended to expose the common fundamental nature of the new updating structures.
- IV. DISCUSSIONS AND COMPARISONS: Flop counts are derived for complete time steps of ADI, LOD1/SS1, SS2, and LOD2 using their updating-equation right-hand sides.The count assumes precomputed multiplicative factors, equal numbers of field components, and minimized loop arrangements.
- IV. DISCUSSIONS AND COMPARISONS: 102 flops versus 42 flops: conventional versus new ADI-FDTD, while original LOD1/SS1 and LOD2 implementations use 72 flops and their new algorithms use 42.The comparison assumes no need for frequent magnetic-field output and reports total M/D+A/S counts.
- IV. DISCUSSIONS AND COMPARISONS: 63 flops versus 108 flops: the new SS2 algorithm versus its original implementation.SS2 has three updating procedures, each reflecting the 21-flop fundamental updating structure.
- IV. DISCUSSIONS AND COMPARISONS: 2.43 versus 1.83: new fundamental ADI, LOD1/SS1, and LOD2 achieve the former RHS efficiency gain, while including tridiagonal solves yields the latter overall gain.The estimated tridiagonal-system cost is about 5N flops for an order-N system with precomputed bidiagonally factorized elements.
- IV. DISCUSSIONS AND COMPARISONS: 12 versus 18 for-loops: ADI, LOD1/SS1, and LOD2 use 12, whereas SS2 uses 18 because it has three updating procedures.The comparison also summarizes temporal accuracy; LOD1/SS1 is first-order in time but can be converted to second-order schemes through shared updating structures.
- IV. DISCUSSIONS AND COMPARISONS: 42 flops and 12 for-loops: other implicit schemes converge to the same fundamental implementations despite distinctive original splitting formulae.This supports using fundamental schemes as a methodical efficiency-improvement basis and as benchmarks for future implicit schemes.
V. CONCLUSION
The paper formulates fundamental schemes for efficient unconditionally stable implicit FDTD methods and develops algorithms based on their shared updating structures. It concludes that these schemes support simpler, more efficient implementations and future scheme development across electromagnetics and other application areas.
- V. CONCLUSION: The paper generalizes fundamental schemes through matrix operator equations associated with ADI, LOD, and split-step splitting formulae.The analysis also covers additional schemes with distinctive splitting formulae.
- V. CONCLUSION: Fundamental schemes share simple updating structures with efficient right-hand sides, supporting new implementations and comparative computation-cost studies.The paper describes detailed algorithms and compares original and new implementations using computation costs and efficiency gains.
- V. CONCLUSION: The schemes are positioned for use beyond electromagnetics, coding simplification, efficiency improvement, and as bases or benchmarks for future implicit-scheme development.Their updating structures also invite investigations of further properties, extensions, and applications.