In this paper, finite element discretizations of the degenerated operator -ω²(y) u_xx-ω²(x)u_yy=g in the unit square are investigated, where the weight function satisfies ω(ξ)=ξ^α with α ≥ 0. We propose two multi-level methods in order to solve the resulting system of linear algebraic equations. The first method is a multi-grid algorithm with line-smoother. A proof of the smoothing property is given. The second method is a BPX-like preconditioner which we call MTS-BPX preconditioner. We show that the upper eigenvalue bound of the MTS-BPX preconditioned system matrix grows proportionally to the level number.

The boundary concentrated finite element method is a variant of the hp-version of the finite element method that is particularly suited for the numerical treatment of elliptic boundary value problems with smooth coefficients and low regularity boundary conditions. For this method we present two multilevel preconditioners that lead to preconditioned stiffness matrices with condition numbers that are bounded uniformly in the problem size N. The cost of applying the preconditioners is O(N). Numerical examples illustrate the efficiency of the algorithms.

Thesis (M.S.)--University of Toledo, 2009. / "In partial fulfillment of the requirements for the degree of Master of Science in Biomedical Science." Title from title page of PDF document. Bibliography: p. 39-48.

I implemented and tested the method of Non-Linear Conjugate Gradients (NLCG) to invert magnetotelluric (MT) and radiomagnetotelluric (RMT) data in two dimensions. The forward problem and the objective function gradients were computed using finite-difference methods. The NLCG algorithm was applied to three field data sets to test the performance of the code. It was then compared to the inversion techniques of Occam and damped Occam considering the quality of the output resistivity models and the computation times. The implemented code was further investigated by testing two line search techniques to reduce the objective function along a given search direction. The first line search procedure was constrained to the first Wolfe condition, leading to a rather inexact line search. The second, more thorough line search, was additionally constrained to the second Wolfe condition. Three preconditioners were applied to the NLCG algorithm and their performance was analysed. The first preconditioner was set to the diagonal of the approximate Hessian matrix and updated every 20-th iteration. Preconditioners two and three were updated with the Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm using the identity matrix and the diagonal of the approximate Hessian matrix as start preconditioners, respectively. The tests showed that the method of NLCG is more efficient pertaining to computation times compared to the Gauss-Newton (GN) based techniques (Occam and damped Occam). For the two smaller data sets that were inverted, the NLCG inversion was two to four times faster than Occam and damped Occam. For the larger data set, the NLCG inversion converged more than one order of magnitude faster than the GN based inversion techniques. This is because GN methods require to evaluate the entire sensitivity matrix to update the model, whereas NLCG only needs to compute a matrix-vector product of the Jacobian. Moreover, expensive operations such as matrix products and direct inversions of linearised systems are avoided by NLCG. A limitation of the NLCG algorithm is that it is prone to converge to local minima due to the fixed Lagrange multiplier that is used in the penalty function. Occam inversion, which determines the optimal Lagrange multiplier as part of the inversion, did not show such problems. The line search tests of the NLCG algorithm showed that an inexact line search yields higher convergence per CPU time than a more exact line search. In accordance to previous studies, preconditioning accelerated the convergence of the NLCG algorithm considerably. The preconditioners updated with the BFGS algorithm achieved highest convergence. Choosing the identity matrix as a start preconditioner led to fast but unstable convergence. The reasons for that could not be determined completely. Taking the diagonal of the approximate Hessian as a start preconditioner instead of the identity matrix led to slower convergence for most of the inversion tests, but convergence could be stabilised. All the tests performed within this project led to a robust implementation of the NLCG algorithm. A default set-up pertaining to line search and preconditioning could be established. However, the NLCG set-up can be adjusted by the user to improve convergence for a specific data set. This makes the algorithm implemented in this thesis more flexible than previously introduced NLCG codes. Preconditioning can certainly still be improved with further tests. Moreover, a future project will be to extend the 2D code to 3D, where NLCG should perform especially well, because the number of model parameters is usually higher in 3D.

Spectral graph theory is the interplay between linear algebra and combinatorial graph theory. Laplace’s equation and its discrete form, the Laplacian matrix, appear ubiquitously in mathematical physics. Due to the recent discovery of very fast solvers for these equations, they are also becoming increasingly useful in combinatorial optimization, computer vision, computer graphics, and machine learning. In this thesis, we develop highly efficient and parallelizable algorithms for solving linear systems involving graph Laplacian matrices. These solvers can also be extended to symmetric diagonally dominant matrices and M-matrices, both of which are closely related to graph Laplacians. Our algorithms build upon two decades of progress on combinatorial preconditioning, which connects numerical and combinatorial algorithms through spectral graph theory. They in turn rely on tools from numerical analysis, metric embeddings, and random matrix theory. We give two solver algorithms that take diametrically opposite approaches. The first is motivated by combinatorial algorithms, and aims to gradually break the problem into several smaller ones. It represents major simplifications over previous solver constructions, and has theoretical running time comparable to sorting. The second is motivated by numerical analysis, and aims to rapidly improve the algebraic connectivity of the graph. It is the first highly efficient solver for Laplacian linear systems that parallelizes almost completely. Our results improve the performances of applications of fast linear system solvers ranging from scientific computing to algorithmic graph theory. We also show that these solvers can be used to address broad classes of image processing tasks, and give some preliminary experimental results.

Diss. (sammanfattning) Stockholm : Karolinska institutet, 2007. / Härtill 5 uppsatser.

Diss. (sammanfattning) Stockholm : Karol. inst., 2002. / Härtill 5 uppsatser.

Thesis (Ph. D.)--Uniformed Services University of the Health Sciences, 2006. / Typescript (photocopy).

L'inversion de forme d'onde complète (FWI) est un processus non-linéaire et mal posé d’ajustement de données, dans notre cas, issues d’acquisitions simiques. Cette technique cherche à reconstruire, à partir d’un modèle initial obtenu à faible nombre d’onde (faible résolution), des paramètres constitutifs contrôlant la propagation des ondes à grands nombres d’ondes (forte résolution). Durant ce processus itératif, certains artéfacts peuvent altérer la qualité du modèle reconstruit. Afin de diminuer ces artéfacts et d’assurer une reconstruction des paramètres qui soit cohérente d’un point de vue géologique, différentes techniques de pré-conditionnement ou de régularisation peuvent être proposées.Cette thèse se focalise sur le potentiel de nouveaux filtres multi-dimensionnels construits dans l’espace des nombres d’ondes et orientés suivant les structures géologiques. Une stratégie de pré-conditionnement a été mise au point à l’aide de ces filtres et a été appliquée avec succès à la problématique FWI. La formulation analytique 1D de l’opérateur inverse de covariance laplacienne (Tarantola, 2005) constitue la base de la formulation d’opérateurs de dimension supérieure qui sont validés ici en les comparants avec l’opérateur analytique de covariance laplacienne 1D. Nous avons utilisé cette fonction analytique inverse 1D comme la base de filtrage de dimension supérieure, via l’addition de multiples fonctions inverses orientées orthogonalement. Ces fonctions laplaciennes inverses additionnelles (AIL) sont obtenues pour des configurations 2D et 3D après discrétisation par des techniques de différences finies. Nous montrons que l’on peut calculer un filtre en nombre d’onde de manière rapide et robuste en résolvant le système linéaire associé à ces opérateurs inverses. Lorsque des pentes sont inclues à l’étape de discrétisation par différences finies, il est alors possible d’utiliser ces opérateurs comme des filtres en nombre d’ondes orientés vers les structures géologiques, ceci avec une grande efficacité.Ce filtre (AIL) montre des propriétés rapides de convergence et des performances indépendantes du vecteur à filtrer. Nous montrons notamment comment ce filtre peut être utilisé comme un opérateur utile pour le gradient associé à la FWI. Le pré-conditionnement du gradient peut atténuer les effets du problème mal-posé qui vont s’étendre dans l’espace des modèles. Deux exemples synthétiques (Valhall et Marmousi) calculés dans l’espace des fréquences sont proposés dans cette thèse. Le pré-conditionnement AIL s’avère efficace pour atténuer d’une part la signature mal-posée provenant de la présence de bruit ambient dans les données observées et d’autre part d’artéfacts liés aux effets de repliement spatial liés aux conditions d’imagerie par FWI. La possibilité d’inclure des pentes permet de filtrer de manière préférentielle en considérant des pendages géologiques. Cette stratégie de filtrage permet l’atténuation d’artéfacts, tout en préservant le contenu en nombre d’ondes de la stratigraphie orthogonale au pendage.Un cas réel d’inversion 2D FWI est finalement abordé permettant tout d’abord d’illustrer la sensibilité des résultats d’inversion au modèle initial. Celui-ci est d’importance majeure, particulièrement dans les régions profondes dépassant la pénétration maximale des ondes transmises. L’application de la technique FWI à cette acquisition sismique a permis d’améliorer de manière significative la cohérence sur une image migrée par renversement du temps (RTM). Nous montrons également que le pré-conditionneur AIL permet une décroissance significative du nombre de tirs requis à modéliser dans la boucle d’inversion, sans pour autant dégrader le contenu en nombre d’onde des structures géologiques principales dans les résultats finaux obtenus après inversion. / Full waveform inversion (FWI) is a non-linear, ill-posed, local data fitting technique. FWI looks to moves from an initial, low-wavenumber representation of the earth parameters to a broadband representation. During this iterative process a number of undesirable artifacts can map into our model parameter reconstruction. To mitigate these artifacts and to ensure a geologically consistent model parameter reconstruction, various preconditioning and/or regularization strategies have been proposed.This thesis details the construction of new, efficient, multi-dimensional, structurally-orientated wavenumber filters. A preconditioning strategy has been devised using these filters that we have successfully applied to FWI. The 1D analytical inverse Laplacian covariance operator (Tarantola, 2005) forms the basis of higher dimensional operators and is initially validated by comparing to the 1D analytical Laplacian covariance operator. We use this analytical 1D inverse function as the basis for higher dimensional filtering via the addition of multiple, orthogonally orientated inverse functions. These additive inverse laplacian functions (AIL) are shown in 2D and 3D configurations and are discretized using finite-difference techniques. We show that one can calculate, a rapid and robust wavenumber filter, by solving the linear system associated with these inverse operators. When dip is included at the finite difference discretization stage, it is possible to use these operators as highly efficient, structurally orientated wavenumber filters.The AIL filter is shown to be rapid to converge and its performance is independent of the vector to be filtered. We show, that the filter can be a useful preconditioning operator for the FWI gradient. Preconditioning the gradient can mitigate against ill-posed effects mapping into the model-space. Two synthetic (Valhall and Marmousi) frequency domain FWI example are shown in this thesis. The AIL preconditioner has success at mitigating the ill-posed imprint coming from ambient noise in the observed data and also artifacts from spatial aliasing effects in the FWI imaging condition. The ability to include dip, allows one to preferentially filter along geological dip. This filtering strategy allows the mitigation of artifacts, while simultaneously preserving the stratigraphic based wavenumber content that is orthogonal to dip.A 2D, real data FWI case-study is also shown and we highlight the sensitivity of the inversion result to the initial model. The initial model is of key importance, this especially true in the areas deeper than the maximum penetration of transmitted waves. The application of FWI on this line is able to significantly improve gather alignment on a RTM, migrated image. We also see that the AIL preconditioner can allows us to significantly decrease the number of shot records we are required to model in our inversion workflow without degrading the key geological wavenumber content in the final inversion result.

No description available.