We discuss a full-waveform based material profile reconstruction in two-dimensional heterogeneous semi-infinite domains. In particular, we try to image the spatial variation of shear moduli/wave velocities, directly in the time-domain, from scant surficial measurements of the domain's response to prescribed dynamic excitation. In addition, in one-dimensional media, we try to image the spatial variability of elastic and attenuation properties simultaneously. To deal with the semi-infinite extent of the physical domains, we introduce truncation boundaries, and adopt perfectly-matched-layers (PMLs) as the boundary wave absorbers. Within this framework we develop a new mixed displacement-stress (or stress memory) finite element formulation based on unsplit-field PMLs for transient scalar wave simulations in heterogeneous semi-infinite domains. We use, as is typically done, complex-coordinate stretching transformations in the frequency-domain, and recover the governing PDEs in the time-domain through the inverse Fourier transform. Upon spatial discretization, the resulting equations lead to a mixed semi-discrete form, where both displacements and stresses (or stress histories/memories) are treated as independent unknowns. We propose approximant pairs, which numerically, are shown to be stable. The resulting mixed finite element scheme is relatively simple and straightforward to implement, when compared against split-field PML techniques. It also bypasses the need for complicated time integration schemes that arise when recent displacement-based formulations are used. We report numerical results for 1D and 2D scalar wave propagation in semi-infinite domains truncated by PMLs. We also conduct parametric studies and report on the effect the various PML parameter choices have on the simulation error. To tackle the inversion, we adopt a PDE-constrained optimization approach, that formally leads to a classic KKT (Karush-Kuhn-Tucker) system comprising an initial-value state, a final-value adjoint, and a time-invariant control problem. We iteratively update the velocity profile by solving the KKT system via a reduced space approach. To narrow the feasibility space and alleviate the inherent solution multiplicity of the inverse problem, Tikhonov and Total Variation (TV) regularization schemes are used, endowed with a regularization factor continuation algorithm. We use a source frequency continuation scheme to make successive iterates remain within the basin of attraction of the global minimum. We also limit the total observation time to optimally account for the domain's heterogeneity during inversion iterations. We report on both one- and two-dimensional examples, including the Marmousi benchmark problem, that lead efficiently to the reconstruction of heterogeneous profiles involving both horizontal and inclined layers, as well as of inclusions within layered systems. / text

The object of the thesis is the computational complexity of certain combinatorial optimisation problems called \emph{valued constraint satisfaction problems}, or \emph{VCSPs} for short. The requirements and optimisation criteria of these problems are expressed by sums of \emph{(valued) constraints} (also called \emph{cost functions}). More precisely, the input of a VCSP consists of a finite set of variables, a finite set of cost functions that depend on these variables, and a cost $u$; the task is to find values for the variables such that the sum of the cost functions is at most $u$. By restricting the set of possible cost functions in the input, a great variety of computational optimisation problems can be modelled as VCSPs. Recently, the computational complexity of all VCSPs for finite sets of cost functions over a finite domain has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of infinite-domain VCSPs by studying the complexity of VCSPs for piecewise linear (PL) and piecewise linear homogeneous (PLH) cost functions. The VCSP for a finite set of PLH cost functions can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We show this by (polynomial-time many-one) reducing the problem to a finite-domain VCSP which can be solved using a linear programming relaxation. We apply this result to show the polynomial-time tractability of VCSPs for {\it submodular} PLH cost functions, for {\it convex} PLH cost functions, and for {\it componentwise increasing} PLH cost functions; in fact, we show that submodular PLH functions and componentwise increasing PLH functions form maximally tractable classes of PLH cost functions. We define the notion of {\it expressive power} for sets of cost functions over arbitrary domains, and discuss the relation between the expressive power and the set of fractional operations improving the same set of cost functions over an arbitrary countable domain. Finally, we provide a polynomial-time algorithm solving the restriction of the VCSP for {\it all} PL cost functions to a fixed number of variables.