Title: Numerical Methods in Discrete Inverse Problems Author: Marie Kubínová Department: Department of Numerical Mathematics Supervisor: RNDr. Iveta Hnětynková, Ph.D., Department of Numerical Mathe- matics Abstract: Inverse problems represent a broad class of problems of reconstruct- ing unknown quantities from measured data. A common characteristic of these problems is high sensitivity of the solution to perturbations in the data. The aim of numerical methods is to approximate the solution in a computationally efficient way while suppressing the influence of inaccuracies in the data, referred to as noise, that are always present. Properties of noise and its behavior in reg- ularization methods play crucial role in the design and analysis of the methods. The thesis focuses on several aspects of solution of discrete inverse problems, in particular: on propagation of noise in iterative methods and its representation in the corresponding residuals, including the study of influence of finite-precision computation, on estimating the noise level, and on solving problems with data polluted with noise coming from various sources. Keywords: discrete inverse problems, iterative solvers, noise estimation, mixed noise, finite-precision arithmetic - iii -

No description available.

Gitter QCD strebt nach höherer Präzision. Hier untersuchen wir zwei kritische Punkte, die zur Genauigkeit von Gitter-Ergebnissen beitragen. Im ersten Teil kalibrieren wir Gitterabstände von QCD Simulationen mit 2 + 1 Arten (flavor) dynamischer Quarks. Dabei nutzen wir neue Messungen und eine mehrere Modelle für den chiralen- und Kontinuumslimes, um die Ergebnisse der 2017 durchgeführten Studie [1] zu verbessern. Der zweite Teil befasst sich mit Simulationsalgorithmen. Wir testen einen Algorithmus, der eine schnellere Lösung der Dirac-Gleichung verspricht. Wir analysieren die Anwendung des FETI-Algorithmus (Finite Element Tear and Interconnect) im Zusammenhang mit Gitter-QCD-Simulationen und vergleichen ihn mit anderen modernen Lösungsverfahren aus der Klasse der Domänendekompositionslösern. Wir untersuchen verschiedene Präkonditionierer und ihre Auswirkungen auf die Konvergenz der Lösung. / Lattice QCD simulations strive for higher precision. Here, we study two critical points in the generation of high precision lattice results. In the first part, we calibrate the lattice spacings of QCD simulation with 2 + 1 flavors of dynamical fermions. We incorporate new measurements and use additional models for the chiral and continuum extrapolations to refine the result obtained in 2017 [1]. The second part focuses on simulation algorithms. We test an algorithm which promises faster solution of the Dirac equation. We analyze the application of the Finite Element Tear and Interconnect (FETI) algorithm in the context of lattice QCD simulations and compare it to other state-of-the-art domain decomposition solvers. We examine various preconditioners and their effects on the convergence of the solution.

Sudden cardiac death following cardiac arrest is a major killer in the industrialised world. The leading cause of sudden cardiac death are disturbances in the normal electrical activation of cardiac tissue, known as cardiac arrhythmia, which severely compromise the ability of the heart to fulfill the body's demand of oxygen. Ventricular fibrillation (VF) is the most deadly form of cardiac arrhythmia. Furthermore, electrical defibrillation through the application of strong electric shocks to the heart is the only effective therapy against VF. Over the past decades, a large body of research has dealt with the study of the mechanisms underpinning the success or failure of defibrillation shocks. The main mechanism of shock failure involves shocks terminating VF but leaving the appropriate electrical substrate for new VF episodes to rapidly follow (i.e. shock-induced arrhythmogenesis). A large number of models have been developed for the in silico study of shock-induced arrhythmogenesis, ranging from single cell models to three-dimensional ventricular models of small mammalian species. However, no extrapolation of the results obtained in the aforementioned studies has been done in human models of ventricular electrophysiology. The main reason is the large computational requirements associated with the solution of the bidomain equations of cardiac electrophysiology over large anatomically-accurate geometrical models including representation of fibre orientation and transmembrane kinetics. In this Thesis we develop simulation technology for the study of cardiac defibrillation in the human heart in the framework of the open source simulation environment Chaste. The advances include the development of novel computational and numerical techniques for the solution of the bidomain equations in large-scale high performance computing resources. More specifically, we have considered the implementation of effective domain decomposition, the development of new numerical techniques for the reduction of communication in Chaste's finite element method (FEM) solver, and the development of mesh-independent preconditioners for the solution of the linear system arising from the FEM discretisation of the bidomain equations. The developments presented in this Thesis have brought Chaste to the level of performance and functionality required to perform bidomain simulations with large three-dimensional cardiac geometries made of tens of millions of nodes and including accurate representation of fibre orientation and membrane kinetics. This advances have enabled the in silico study of shock-induced arrhythmogenesis for the first time in the human heart, therefore bridging an important gap in the field of cardiac defibrillation research.

La symétrie est par définition un concept multidisciplinaire. Il apparaît dans de nombreux domaines. En général, elle revient à une transformation qui laisse invariant un objet. Le problème de satisfaisabilité (SAT) occupe un rôle central en théorie de la complexité. Il est le problème de décision de référence de la classe NP-complet (Cook, 71). Il consiste à déterminer si une formule CNF admet ou non une valuation qui la rend vraie. Dans la première contribution de ce mémoire, nous avons introduit une nouvelle méthode complète qui élimine toutes les symétries locales pour la résolution du problème SAT en exploitant son groupe des symétries. Les résultats obtenus montrent que l'exploitation des symétries locales est meilleure que l'exploitation des symétries globales sur certaines instances SAT et que les deux types de symétries sont complémentaires, leur combinaison donne une meilleure exploitation.En deuxième contribution, nous proposons une approche d'apprentissage de clauses pour les solveurs SAT modernes en utilisant les symétries. Cette méthode n'élimine pas les modèles symétriques comme font les méthodes statiques d'élimination des symétries. Elle évite d'explorer des sous-espaces correspondant aux no-goods symétriques de l'interprétation partielle courante. Les résultats obtenus montrent que l'utilisation de ces symétries et ce nouveau schéma d'apprentissage est profitable pour les solveurs CDCL.En Intelligence Artificielle, on inclut souvent la non-monotonie et l'incertitude dans le raisonnement sur les connaissances avec exceptions. Pour cela, en troisième et dernière contribution, nous avons étendu la notion de symétrie à des logiques non classiques (non-monotones) telles que les logiques préférentielles, les X-logiques et les logiques des défauts.Nous avons montré comment raisonner par symétrie dans ces logiques et nous avons mis en évidence l'existence de certaines symétries dans ces logiques qui n'existent pas dans les logiques classiques. / Symmetry is by definition a multidisciplinary concept. It appears in many fields. In general, it is a transformation which leaves an object invariant. The problem of satisfiability (SAT) is one of the central problems in the complexity theory. It is the first decision Np-complete problem (Cook, 71). It deals with determining if a CNF formula admits a valuation which makes it true. First we introduce a new method which eliminates all the local symmetries during the resolution of a SAT problem by exploiting its group of symmetries. Our experimental results show that for some SAT instances, exploiting local symmetries is better than exploiting just global symmetries and both types of symmetries are complementary. As a second contribution, we propose a new approach of Conflict-Driven Clause Learning based on symmetry. This method does not eliminate the symmetrical models as the static symmetry elimination methods do. It avoids exploring sub-spaces corresponding to symmetrical No-goods of the current partial interpretation. Our experimental results show that using symmetries in clause learning is advantageous for CDCL solvers.In artificial intelligence, we usually include non-monotony and uncertainty in the reasoning on knowledge with exceptions. Finally, we extended the concept of symmetry to non-classical logics that are preferential logics, X-logics and default logics. We showed how to reason by symmetry in these logics and we prove the existence of some symmetries in these non-classical logics which do not exist in classical logics.

[pt] A otimização topológica tem como objetivo encontrar a distribuição mais eficiente de material em um domínio especificado sem violar as restrições de projeto definidas pelo usuário. Quando aplicada a estruturas contínuas, a otimização topológica é geralmente realizada por meio de métodos de densidade, conhecidos na literatura técnica. Neste trabalho, daremos ênfase à aplicação de sua formulação discreta, na qual um determinado domínio é discretizado na forma de uma estrutura base, ou seja, uma distribuição espacial finita de nós conectados entre si por meio de barras de treliça. O método de estrutura base fornece uma aproximação para as estruturas de Michell, que são compostas por um número infinito de barras, por meio de um número reduzido de elementos de treliça. O problema de determinar a estrutura final com peso mínimo, para um único caso de carregamento, considerando um comportamento linear elástico do material e restrições de tensão, pode ser formulado como um problema de programação linear. O objetivo deste trabalho é fornecer uma implementação escalável para o problema de otimização de treliças com peso mínimo, considerando domínios com geometrias arbitrárias. O método remove os elementos que são desnecessários, partindo de uma treliça cujo grau de conectividade é definido pelo usuário, mantendo-se fixos os pontos nodais. Propomos uma implementação escalável do método de estrutura base, utilizando um algoritmo de pontos interiores eficiente e robusto, em um ambiente de computação paralela (envolvendo unidades de processamento gráfico ou GPUs). Os resultados apresentados, em estruturas bi e tridimensionais com milhões de barras, ilustram a viabilidade e a eficiência computacional da implementação proposta. / [en] Topology optimization aims to find the most efficient material distribution in a specified domain without violating user-defined design constraints. When applied to continuum structures, topology optimization is usually performed by means of the well-known density methods. In this work we focus on the application of its discrete formulation where a given domain is discretized into a ground structure, i.e., a finite spatial distribution of nodes connected using truss members. The ground structure method provides an approximation to optimal Michell-type structures, composed of an infinite number of members, by using a reduced number of truss members. The optimal least weight truss for a single load case, under linear elastic conditions, subjected to stress constraints can be posed as a linear programming problem. The aim of this work is to provide a scalable implementation for the optimization of least weight trusses embedded in any domain geometry. The method removes unnecessary members from a truss that has a user-defined degree of connectivity while keeping the nodal locations fixed. We discuss in detail the scalable implementation of the ground structure method using an efficient and robust interior point algorithm within a parallel computing environment (involving Graphics Processing Units or GPUs). The capabilities of the proposed implementation is illustrated by means of large scale applications on practical problems with millions of members in both 2D and 3D structures.

<p>Diffusion is a phenomenon in which particles move from regions of higher density to regions of lower density. Many physical systems, in fields as diverse as plant biology and finance, are known to involve diffusion phenomena. Typically, diffusion systems are modeled by partial differential equations (PDEs), which include certain parameters. These parameters characterize a given diffusion system. Therefore, for both modeling and simulation of a diffusion system, one has to either know or determine these parameters. Moreover, as PDEs are infinite order dynamic systems, for computational purposes one has to approximate them by a finite order model. In this thesis, we investigate these two issues of model reduction and parameter estimation by considering certain specific cases of heat diffusion systems. </p><p>We first address model reduction by considering two specific cases of heat diffusion systems. The first case is a one-dimensional heat diffusion across a homogeneous wall, and the second case is a two-dimensional heat diffusion across a homogeneous rectangular plate. In the one-dimensional case we construct finite order approximations by using some well known PDE solvers and evaluate their effectiveness in approximating the true system. We also construct certain other alternative approximations for the one-dimensional diffusion system by exploiting the different modal structures inherently present in it. For the two-dimensional heat diffusion system, we construct finite order approximations first using the standard finite difference approximation (FD) scheme, and then refine the FD approximation by using its asymptotic limit.</p><p>As for parameter estimation, we consider the same one-dimensional heat diffusion system, as in model reduction. We estimate the parameters involved, first using the standard batch estimation technique. The convergence of the estimates are investigated both numerically and theoretically. We also estimate the parameters of the one-dimensional heat diffusion system recursively, initially by adopting the standard recursive prediction error method (RPEM), and later by using two different recursive algorithms devised in the frequency domain. The convergence of the frequency domain recursive estimates is also investigated. </p>

This thesis tackles the problem of automatically proving the validity of mathematical formulas generated by program verification tools. In particular, it focuses on Satisfiability Modulo Theories (SMT): a young research topic that has seen great advances during the last decade. The solvers of this family have various applications in hardware design, program verification, model checking, etc.SMT solvers offer a good compromise between expressiveness and efficiency. They rely on a tight cooperation between a SAT solver and a combination of decision procedures for specific theories, such as the free theory of equality with uninterpreted symbols, linear arithmetic over integers and rationals, or the theory of arrays.This thesis aims at improving the efficiency and the expressiveness of the Alt-Ergo SMT solver. For that, we designed a new decision procedure for the theory of linear integer arithmetic. This procedure is inspired by Fourier-Motzkin's method, but it uses a rational simplex to perform computations in practice. We have also designed a new combination framework, capable of reasoning in the union of the free theory of equality, the AC theory of associative and commutativesymbols, and an arbitrary signature-disjoint Shostak theory. This framework is a modular and non-intrusive extension of the ground AC completion procedure with the given Shostak theory. In addition, we have extended Alt-Ergo with existing decision procedures to integrate additional interesting theories, such as the theory of enumerated data types and the theory of arrays. Finally, we have explored preprocessing techniques for formulas simplification as well as the enhancement of Alt-Ergo's SAT solver.

A direct method is developed for solving the 2-D planar/axisymmetric Euler equations. The Euler equations are discretized using a finite-volume method with upwind flux splitting schemes, and the resulting nonlinear system of equations are solved using Newton&amp / #8217 / s Method. Both analytical and numerical methods are used for Jacobian calculations. Numerical method has the advantage of keeping the Jacobian consistent with the numerical flux vector without extremely complex or impractical analytical differentiations. However, numerical method may have accuracy problem and may need longer execution time. In order to improve the accuracy of numerical method detailed error analyses were performed. It was demonstrated that the finite-difference perturbation magnitude and computer precision are the most important parameters that affect the accuracy of numerical Jacobians. A relation was developed for optimum perturbation magnitude that can minimize the error in numerical Jacobians. Results show that very accurate numerical Jacobians can be calculated with optimum perturbation magnitude. The effects of the accuracy of numerical Jacobians on the convergence of flow solver are also investigated. In order to reduce the execution time for numerical Jacobian evaluation, flux vectors with perturbed flow variables are calculated for only related cells. A sparse matrix solver based on LU factorization is used for the solution, and to improve the Jacobian matrix solution some strategies are considered. Effects of different flux splitting methods, higher-order discretizations and several parameters on the performance of the solver are analyzed.

No description available.