In this paper we present a comparison study for three different iterative Krylov methods that we have recently developed for the simultaneous numerical solution of wave propagation problems at multiple frequencies. The three approaches have in common that they require the application of a single shift-and-invert preconditioner at a suitable seed frequency. The focus of the present work, however, lies on the performance of the respective iterative method. We conclude with numerical examples that provide guidance concerning the suitability of the three methods.@en

For the Full Waveform Inversion in frequency-domain, the fast numerical solution of the time-harmonic wave equation is required. For large three-dimensional problems, the problem size exceeds several million of unknowns, and a short-recurrence Krylov method such as IDR(s) is used to solve linear systems of this size. Especially for high-frequency simulations, an efficient preconditioner needs to be applied in order to speed-up convergence. In our presentation, we introduce a new preconditioner for the time-harmonic wave equation that exploits the hierarchical structure of the discretized problem. We use multilevel sequentially semiseparable (MSSS) matrix computations for the approximate inversion of the preconditioner. For large three-dimensional problems, we present a memory-efficient modification of the MSSS preconditioner that resembles the approximate solution of a sequence of two-dimensional problems. We conclude our presentation with numerical examples for the time-harmonic wave equation in both acoustic and elastic media, and in two and three spatial dimensions. @en

In this paper we present a comparison study of three different frameworks of iterative Krylov methods that we have recently developed for the simultaneous numerical solution of frequency-domain wave propagation problems when multiple wave frequencies are present. The three approaches have in common that they require the application of a single shift-and-invert preconditioner at a suitable seed frequency. In particular for three-dimensional problems, we present the efficient application of the elastic shift-and-invert preconditioner by means of an additive coarse grid correction. The focus of the present work lies, however, on the performance of the respective iterative method. We conclude with numerical examples that provide guidance concerning the suitability of the three methods.@en

In this work, we present a new numerical framework for the efficient solution of the time-harmonic elastic wave equation at multiple frequencies. We show that multiple frequencies (and multiple right-hand sides) can be incorporated when the discretized problem is written as a matrix equation. This matrix equation can be solved efficiently using the preconditioned IDR(s) method. We present an efficient and robust way to apply a single preconditioner using MSSS matrix computations. For 3D problems, we present a memory-efficient implementation that exploits the solution of a sequence of 2D problems. Realistic examples in two and three spatial dimensions demonstrate the performance of the new algorithm.@en

We consider wave propagation problems that are modeled in the frequency-domain, and that need to be solved simultaneously for multiple frequencies within a fixed range. For this, a single shift-and-invert preconditioner at a so-called seed frequency is applied. The choice of the seed is crucial for the performance of preconditioned multi-shift GMRES and is closely related to the parameter choice for the Complex Shifted Laplace preconditioner. Based on a classical GMRES convergence bound, we present an analytic formula for the optimal seed parameter that purely depends on the original frequency range. The new insight is exploited in a two-level preconditioning strategy: A shifted Neumann preconditioner with minimized spectral radius is additionally applied to multi-shift GMRES. Moreover, we present a reformulation of the multi-shift problem to a matrix equation solved with, for instance, global GMRES. Here, our analysis allows for rotation of the spectrum of the linear operator. Numerical experiments for the time-harmonic visco-elastic wave equation demonstrate the performance of the new preconditioners.@en

Seismic Full-Waveform Inversion is an imaging technique to better understand the earth's subsurface. Therefore, the reflection intensity of sound waves is measured in a field experiment and is matched with the results from a computer simulation in a least-squares sense. From a computational point-of-view, but also from an economic view point, the efficient numerical solution of the elastic wave equation on current hardware is the main bottleneck of the computations, especially when a large three-dimensional computational domain is considered. In our research, we focused on an alternative problem formulation in frequency-domain. The mathematical challenge then becomes to efficiently solve the time-harmonic elastic wave equation at multiple frequencies. The resulting sequence of shifted linear systems is solved with a new framework of Krylov subspace methods derived for this specific problem formulation. Our numerical analysis gives insight in the theoretical convergence behavior of the new algorithm.@en

In the context of Galerkin discretizations of a partial differential equation (PDE), the modes of the classical method of proper orthogonal decomposition (POD) can be interpreted as the ansatz and trial functions of a low-dimensional Galerkin scheme. If one also considers a Galerkin method for the time integration, one can similarly define a POD reduction of the temporal component. This has been described earlier but not expanded upon—probably because the reduced time discretization globalizes time, which is computationally inefficient. However, in finite-time optimal control systems, time is a global variable and there is no disadvantage from using a POD reduced Galerkin scheme in time. In this paper, we provide a newly developed generalized theory for space-time Galerkin POD, prove its optimality in the relevant function spaces, show its application for the optimal control of nonlinear PDEs, and, by means of a numerical example with Burgers’ equation, discuss the competitiveness by comparing to standard approaches.@en

In the context of Galerkin discretizations of a partial differential equation (PDE), the modes of the classical method of proper orthogonal decomposition (POD) can be interpreted as the ansatz and trial functions of a low-dimensional Galerkin scheme. If one also considers a Galerkin method for the time integration, one can similarly define a POD reduction of the temporal component. This has been described earlier but not expanded upon—probably because the reduced time discretization globalizes time, which is computationally inefficient. However, in finite-time optimal control systems, time is a global variable and there is no disadvantage from using a POD reduced Galerkin scheme in time. In this paper, we provide a newly developed generalized theory for space-time Galerkin POD, prove its optimality in the relevant function spaces, show its application for the optimal control of nonlinear PDEs, and, by means of a numerical example with Burgers’ equation, discuss the competitiveness by comparing to standard approaches.@en

We consider wave propagation problems that are modeled in the frequency-domain, and that need to be solved simultaneously for multiple frequencies within a fixed range. For this, a single shift-and-invert preconditioner at a so-called seed frequency is applied. The choice of the seed is crucial for the performance of preconditioned multi-shift GMRES and is closely related to the parameter choice for the Complex Shifted Laplace preconditioner. Based on a classical GMRES convergence bound, we present an optimal seed parameter that purely depends on the original frequency range. The new insight is exploited in a two-level preconditioning strategy: A shifted Neumann preconditioner with minimized spectral radius is additionally applied to multi-shift GMRES. Moreover, we present a reformulation of the multi-shift problem to a matrix equation solved with, for instance, global GMRES. Here, our analysis allows for rotation of the spectrum of the linear operator. Numerical experiments for the time-harmonic visco-elastic wave equation demonstrate the performance of the new preconditioners.@en