A Krylov Space-Based Finite Element Time Domain Method for Broadband Frequency Domain Solutions

Show more

1. Introduction

Wave equations can be generally solved using two categories of methods: time-domain and frequency-domain methods. Finite-difference time-domain (FDTD) methods have been widely adopted for solving different kinds of wave propagation problems. In these methods, the field is discretized into a series of uniform hexahedral volumes. The spatial derivatives are approximated with second-order central differences and the leapfrog method is used for temporal discretization [1] . The interests in the time domain methods have been expanded over the past few decades for several reasons, such as the natural treatments of impulsive behaviors, nonlinear behaviors, and so on.

The solution to linear wave equations can be approximated by linear combinations of sinusoidal waves at various frequencies, which leads to a frequency-domain formulation for different time-harmonic sources. The time-domain solution is of interest in this research for its capability of obtaining frequency domain solutions across a frequency range. Besides, in the time domain, the residual of the linear system is reduced several orders of magnitude, and requires much less search direction in a Krylov subspace [2] .

The time domain methods, however, have been found to suffer from convergence problems for physical models that include locally resonant structures. Such structures may be the result of large material mismatches, or complex geometries. The convergence problems have also been a concern in structural optimizations such as the designs of metamaterials [3] [4] , where the geometry constantly changes during the design iterations and is not predictable.

The purpose of this paper is to introduce a Krylov space based time domain approach for frequency domain solutions. The proposed algorithm is suitable for physical models where slow convergence is found with traditional time domain methods. Related research can be found in [5] [6] [7] , and so on. Different from existing work, the proposed algorithm is derived directly from discrete Fourier transform of time domain data, by which the corresponding frequency domain solutions of a wide range can be obtained with negligible computational costs once the projection of the time domain solution onto the Krylov subspace is obtained. No matrix operation with complex numbers is required in the algorithm. Several numerical cases are examined to demonstrate the efficiency of the method, in which cases the spatial discretization is done with finite element methods.

2. Numerical Model

Wave propagations can be modeled by first order partial differential equations (PDEs) in general, which may be written as

$\frac{\partial Q}{\partial t}+\nabla \cdot F\left(Q\right)=0$ . (1)

In acoustics, the wave equations can be written in a non-conservative form, known as the linearized Euler equations

$\frac{\partial p}{\partial t}+{K}_{e}\nabla \cdot u=0$ , (2)

$\frac{\partial u}{\partial t}+\frac{1}{{\rho}_{e}}\nabla p=0$ , (3)

where p is the acoustic pressure, u is the velocity vector, K_{e} is the bulk modulus of compressibility of the material, and ρ_{e} is the density.

The wave propagation problems in this paper are modeled using a stabilized finite element formulation: Streamlined Upwind/Petrov Galerkin (SUPG) method [8] for time-domain applications. As the speed of computing resources increases and as the geometry conformity becomes more of a concern, finite element methods have become an alternative to the FDTD methods. There are mainly two different strategies in dealing with the convective terms in the hyperbolic equations, and it has been shown that SUPG has the advantage of using a reduced number of unknowns in comparison with the discontinuous Galerkin (DG) method.

Finite element methods typically start with formulating the equations using a weighted residual method, which can be cast in the form of

${\int}_{\Omega}\left[\varphi \right]\left(\frac{\partial Q}{\partial t}+\nabla \cdot F\right)\partial \Omega}=0$ , (4)

where $\varphi $ is a weighting function. The temporal discretization of the governing equation is advanced by implementing a backward differentiation formula (BDF), and the fully discretized equation is solved with an implicit time marching approach (Newton’s method) so that the time-step size can be determined by accuracy considerations instead of stability limitations as in explicit methods.

3. A Broadband Frequency Domain Method Based on Krylov Space Projections of Time Domain Solutions

While the time domain formulation can be used to obtain the frequency domain solution across a frequency range, the convergence of the frequency domain solution is not always as rapid as expected. Especially in physical problems where locally resonant structures exist, the solution procedure can easily take numerous time-marching steps before the errors are reduced to a tolerance.

To circumvent the problem of slow convergence in certain situations, the time domain method is reformulated with a Krylov space projection. Consider the fully discretized equations with BDF-1 scheme, the residual at time step j (t = jΔt) can be written as

${R}^{j}={\displaystyle {\int}_{\Omega}\left[\varphi \right]\left(\frac{{Q}^{j}-{Q}^{j-1}}{\Delta t}+\nabla \cdot F\left({Q}^{j}\right)\right)\partial \Omega}$ . (5)

Since the equations are linear, the residual can be expressed as

${R}^{j}=\left[\stackrel{\u02dc}{A}\right]{Q}^{j}+\left[\stackrel{\u02dc}{B}\right]{Q}^{j-1}$ , (6)

where

$\left[\stackrel{\u02dc}{A}\right]=\frac{\partial {R}^{j}}{\partial {Q}^{j}}$ (7)

and

$\left[\stackrel{\u02dc}{B}\right]=\frac{\partial {R}^{j}}{\partial {Q}^{j-1}}$ (8)

are the linearization matrices. Substitute this into the Newton’s step,

${Q}^{j}=-\left[\stackrel{\u02dc}{A}\right]\left[\stackrel{\u02dc}{B}\right]{Q}^{j-1}$ . (9)

Denote

$\left[M\right]=-\left[\stackrel{\u02dc}{A}\right]\left[\stackrel{\u02dc}{B}\right]$ (10)

and use deduction, given an initial condition Q^{0}, for any given time j, the time dependent solution can be described as

${Q}^{j}=\left[M\right]{Q}^{j-1}$ , (11)

which indicates that the time domain solution forms a Krylov basis with the iterative matrix [M], such that

${K}_{nt}=\left[\begin{array}{ccccc}{Q}^{0}& {\left[M\right]}^{1}{Q}^{0}& {\left[M\right]}^{2}{Q}^{0}& \cdots & {\left[M\right]}^{nt-1}{Q}^{0}\end{array}\right]$ , (12)

where nt is the number of time steps. It also indicates that, the damping of the numerical error is strongly related to the eigenvalues of the matrix [M]; the closer the eigenvalues are to 1.0, the slower the convergence would be.

Since the frequency domain solutions are of interest, the Fourier transform can be applied to the time domain solutions. At each frequency point f_{k}, the discrete Fourier transform may be expressed as

${\stackrel{^}{Q}}_{k}={\displaystyle \underset{j=1}{\overset{nt}{\sum}}{Q}^{j}{\text{e}}^{-\iota {\alpha}_{k}t}\Delta t}$ , (13)

where ι^{2} = −1 and

${\alpha}_{k}=2\text{\pi}{f}_{k}$ . (14)

Denote

${\psi}_{k}^{j}={\text{e}}^{-\iota {\alpha}_{k}t}$ , (15)

and substitute Equation (11) into Equation (13), the frequency domain solutions may now be written as

${\stackrel{^}{Q}}_{k}={\displaystyle \underset{j=1}{\overset{nt}{\sum}}{\left[M\right]}^{j-1}{Q}^{0}{\psi}_{k}^{j-1}\Delta t}$ . (16)

The initial condition Q^{0} can be projected into the eigen-space of matrix [M]. That is, it can be expressed as

${Q}^{0}={\displaystyle \underset{i=1}{\overset{nn}{\sum}}{a}_{i}{v}_{i}}$ . (17)

where nn is the number of nodes (degree of freedom), v_{i} is the i^{th} eigenvector of [M], and a_{i} is the corresponding coefficient. Therefore the solution at time step j can be re-written as

${Q}^{j}={\displaystyle \underset{i=1}{\overset{nn}{\sum}}{a}_{i}{v}_{i}{\lambda}_{i}^{j-1}}$ , (18)

then the frequency domain solution becomes

${\stackrel{^}{Q}}_{k}={\displaystyle \underset{j=1}{\overset{nt}{\sum}}{\displaystyle \underset{i=1}{\overset{nn}{\sum}}{a}_{i}{v}_{i}{\lambda}_{i}^{j-1}{\psi}_{k}^{j-1}}}$ . (19)

Switch the sum operators,

${\stackrel{^}{Q}}_{k}={\displaystyle \underset{i=1}{\overset{nn}{\sum}}{a}_{i}{v}_{i}}{\displaystyle \underset{j=1}{\overset{nt}{\sum}}{\lambda}_{i}^{j-1}{\psi}_{k}^{j-1}}$ , (20)

and this can be expressed as

${\stackrel{^}{Q}}_{k}={\displaystyle \underset{i=1}{\overset{nn}{\sum}}{a}_{i}{v}_{i}{w}_{i}}$ , (21)

with

${w}_{i}={\displaystyle \underset{j=1}{\overset{nt}{\sum}}{\lambda}_{i}^{j-1}{\psi}_{k}^{j-1}}=\frac{1-{\lambda}_{i}^{nt}{\psi}_{k}^{nt}}{1-{\lambda}_{i}{\psi}_{k}}$ . (22)

The set of the eigenvalues and eigenvectors can be approximated by the Arnoldi algorithm [9] . The algorithm can be summarized with the following:

Algorithm. A Krylov space-based time domain method for broadband frequency domain solutions

1) Use Q^{0} as the initial condition for time-domain method to get matrices [A] and [B] as in Equations (7-8).

2) Set i = 1, and set

${q}_{1}=\frac{{Q}^{0}}{\Vert {Q}^{0}\Vert}$ . (23)

and start the Arnoldi iteration. Store the q_{i} vectors in the [Q] matrix, and h_{j}_{,i} items in the [H] matrix.

3) Calculate

${u}_{i}=M{q}_{i}$ . (24)

4) Set j = 1.

5) Calculate

${h}_{j,i}={q}_{j}^{H}{u}_{i}$ . (25)

${u}_{i}={u}_{i}-{h}_{j,i}{q}_{j}$ (26)

6) If j = i, stop the inner loop; otherwise set j = j + 1 and go to step 5.

7) Calculate

${h}_{i+1,i}=\Vert {u}_{i}\Vert $ . (27)

8) If h_{i}_{+1,i} = 0, stop the Arnoldi iteration.

9) Calculate

${q}_{i+1}=\frac{{u}_{i}}{{h}_{i+1,i}}$ . (28)

10) If i = niter (the prescribed number of Arnoldi iteration), stop the Arnoldi iteration; otherwise set i = i + 1 and go to step 3.

11) Calculate the eigenvalues [Λ] and eigenvectors [V_{H}] of the Hessenberg matrix [H] obtained by the Arnoldi iteration, and the eigenvectors [V] of the [M] matrix is given by

$\left[V\right]={\left[Q\right]}^{-1}\left[{V}_{H}\right]$ (29)

12) Calculate the coefficients a_{i} by Equation (17).

13) Calculate the weight coefficients w_{i} by Equation (22).

14) Calculate the frequency domain solutions by Equation (21).

Since in some cases the time domain solution procedure starts by introducing an excitation such as a Gaussian pulse, an intermediate state Q^{0} after the excitation is completed, will be needed in order to proceed with the algorithm. In this case, one needs to calculate the frequency domain solutions before the intermediate state by Equation (13) and add it to the primitive frequency domain solution.

For physical problems which require a lot of iterations before the frequency domain solutions reach convergence, this algorithm is recommended. In fact, the eigenvalues in these problems are found to be close to 1.0, which can be effectively approximated by the Arnoldi algorithm since these eigenvalues are typically extremes in the eigensystems. The advantage of using this algorithm is that, the number of time steps nt can be chosen to be an arbitrary number, so that the number of iterations is reduced from nt to niter as is needed for the Arnoldi iteration.

4. Numerical Examples

An acoustic wave propagation case with artificial material properties is designed to examine the efficiency of the proposed algorithm. The geometry is shown in Figure 1, where the background material (material 1) is shown in gray color, and the inclusion (material 2) is shown in black color. This geometry is a simple locally resonant structure. The unit cell is a square with edge length a = 1 cm. The frequency range of interest is from 0.5 kHz to 3 kHz as reported in a design of acoustic metamaterials [4] . Three cases with different material properties are considered, and the relative material properties of the inclusion are shown in Table 1.

Figure 1. The geometry of the acoustic wave propagation case.

Table 1. The relative material properties of the inclusion.

a. K_{e} is the bulk modulus of compressibility of the material, and ρ_{e} is the density. b. The superscripts represent the acoustic materials 1 (background) and 2 (inclusion).

The simulation is configured as initiating a Gaussian pulse in the left end, and sensors are used to collect information for use in the frequency domain solutions. In addition, periodic boundary conditions are applied to the upper and lower parts of the domain, and absorbing boundary conditions [10] are applied to the left and right ends.

The frequency domain solutions for a sensor located in the center of the computational domain are used as the reference. Since the convergence of the solutions is of primary concern, only the frequency domain solutions after the completion of the Gaussian pulse are considered. It is shown in Figure 2 that the time domain solutions for cases 1 and 2 take a long time before settling down. It is thus to be expected that the convergences of the frequency solution will be slow, and the errors to the converged numerical solutions are plotted in Figure 3. In practice, the numbers of time steps required for cases 1 and 2 to reach the error level of 10^{−10} are 441,769 and 26,280, respectively. In comparison, in both cases the solutions converge to the level of 10^{−10} within 100 Arnoldi iterations with the proposed time domain-based broadband frequency domain algorithm, as shown in Figure 4. However, it is also noted that the solution may diverge due to the fact that the eigenvalues approximated by the Arnoldi algorithm can be bigger than 1, and their exponentials may be exceedingly large. It is thus necessary to monitor the approximated eigenvalues in some cases to ensure their values are all below 1, and if one or more of them are larger than 1, more Arnoldi iterations need to be taken.

It is seen from Figure 5 that in cases 1 and 2 the frequency domain solutions have peaks at their resonant frequencies, which indicate the long-term vibrations of the acoustic wave within the structure. In case 3, the solutions converge

Figure 2. The time domain solutions at a sensor located in the center of the geometry.

Figure 3. The convergence of frequency domain solutions with the time-marching approach.

Figure 4. The convergence of frequency domain solutions with the Krylov space-based time domain algorithm.

promptly with time marching method, and the resonant frequency is not obvious, due to the fact that most of the vibrations are damped after the excitation is completed. In addition, the Arnoldi iteration is also able to reduce the error level for this case.

Figure 5. The Frequency domain solutions at a sensor located in the center of the geometry.

5. Conclusion

A Krylov space-based time domain method is introduced for broadband frequency domain solutions. This method is useful for dealing with physical models for which slow convergences are observed with traditional time marching methods. The efficiency of the method is examined in several test cases to show its fast convergence in such problems. An acoustic wave propagation problem is modeled with a stabilized finite element method. In the test cases, the proposed method uses less than 100 iterations before an error level is reached. This decrease is orders of magnitude less than the time-marching approach.

Acknowledgements

The author is currently an employee of Mentor, a Siemens Business. A portion of the work was performed while the author was working at the SimCenter of the University of Tennessee at Chattanooga. Supports from both sides were greatly appreciated.

References

[1] Taflove, A. and Hagness, S.C. (2000) Computational Electrodynamics. Artech House Publishers, London.

[2] Anderson, W.K., Wang, L., Kapadia, S., Tanis, C. and Hilbert, B. (2011) Petrov-Galerkin and Discontinuous-Galerkin Methods for Time-Domain and Frequency-Domain Electromagnetic Simulations. Journal of Computational Physics, 230, 8360-8385.

https://doi.org/10.1016/j.jcp.2011.06.025

[3] Lin, W. (2016) Design Optimization of Acoustic Metamaterials and Phononic Crystals with a Time Domain Method. PhD Dissertation, University of Tennessee at Chattanooga, Chattanooga, TN.

[4] Lin, W., Newman, J.C., Anderson, W.K. and Zhang, X. (2017) Topology and Shape Optimization of Broadband Acoustic Metamaterials and Phononic Crystals. Acoustical Science and Technology, 38, 254-260.

https://doi.org/10.1250/ast.38.254

[5] Druskin, V. and Knizhnerman, L. (1994) Spectral Approach to Solving Three-Dimensional Maxwell’s Diffusion Equations in the Time and Frequency Domains. Radio Science, 29, 937-953.

https://doi.org/10.1029/94RS00747

[6] Botchev, M.A. (2016) Krylov Subspace Exponential Time Domain Solution of Maxwell’s Equations in Photonic Crystal Modeling. Journal of Computational and Applied Mathematics, 293, 20-34.

https://doi.org/10.1016/j.cam.2015.04.022

[7] Grimm, V. and Hochbruck, M. (2006) Error Analysis of Exponential Integrators for Oscillatory Second-Order Differential Equations. Journal of Physics A: Mathematical and General, 39, 5495.

https://doi.org/10.1088/0305-4470/39/19/S10

[8] Brooks, A.N. and Hughes, T.J. (1982) Streamline Upwind/Petrov-Galerkin Formulations for Convection Dominated Flows with Particular Emphasis on the Incompressible Navier-Stokes Equations. Computer Methods in Applied Mechanics and Engineering, 32, 199-259.

https://doi.org/10.1016/0045-7825(82)90071-8

[9] Arnoldi, W.E. (1951) The Principle of Minimized Iterations in the Solution of the Matrix Eigenvalue Problem. Quarterly of Applied Mathematics, 9, 17-29.

https://doi.org/10.1090/qam/42792

[10] Mur, G. (1981) Absorbing Boundary Conditions for the Finite-Difference Approximation of the Time-Domain Electromagnetic-Field Equations. IEEE Transactions on Electromagnetic Compatibility, EMC-23, 377-382.

https://doi.org/10.1109/TEMC.1981.303970