An investigation of preconditioning techniques is presented for a Newton--Krylov algorithm that is used for the computation of steady, compressible, high Reynolds number flows about airfoils. A second-order centred-difference method is used to discretize the compressible Navier--Stokes (NS) equations that govern the fluid flow. The one-equation Spalart--Allmaras turbulence model is used. The discretized equations are solved using Newton's method and the generalized minimal residual (GMRES) Krylov subspace method is used to approximately solve the linear system. These preconditioning techniques are first applied to the solution of the discretized steady convection-diffusion equation. Various orderings, iterative block incomplete LU (BILU) preconditioning and multigrid preconditioning are explored. The baseline preconditioner is a BILU factorization of a lower-order discretization of the system matrix in the Newton linearization. An ordering based on the minimum discarded fill (MDF) ordering is developed and compared to the widely popular reverse Cuthill--McKee ordering. An evolutionary algorithm is used to investigate and enhance this ordering. For the convection-diffusion equation, the MDF-based ordering performs well and RCM is superior for the NS equations. Experiments for inviscid, laminar and turbulent cases are presented to show the effectiveness of iterative BILU preconditioning in terms of reducing the number of GMRES iterations, and hence the memory requirements of the Newton--Krylov algorithm. Multigrid preconditioning also reduces the number of GMRES iterations. The framework for the iterative BILU and BILU-smoothed multigrid preconditioning algorithms is presented in detail.

Simultaneous localization and mapping (SLAM) and Structure from Motion (SfM) are important problems in robotics and computer vision. One of the challenges is to solve a large-scale optimization problem associated with all of the robot poses, camera parameters, landmarks and measurements. Yet neither of the two reigning paradigms, direct and iterative methods, scales well to very large and complex problems. Recently, the subgraph-preconditioned conjugate gradient method has been proposed to combine the advantages of direct and iterative methods. However, how to find a good subgraph is still an open problem. The goal of this dissertation is to address the following two questions: (1) What are good subgraph preconditioners for SLAM and SfM? (2) How to find them? To this end, I introduce support theory and support graph theory to evaluate and design subgraph preconditioners for SLAM and SfM. More specifically, I make the following contributions: First, I develop graphical and probabilistic interpretations of support theory and used them to visualize the quality of subgraph preconditioners. Second, I derive a novel support-theoretic metric for the quality of spanning tree preconditioners and design an MCMC-based algorithm to find high-quality subgraph preconditioners. I further improve the efficiency of finding good subgraph preconditioners by using heuristics and domain knowledge available in the problems. Our results show that the support-theoretic subgraph preconditioners significantly improve the efficiency of solving large SLAM problems. Third, I propose a novel Hessian factor graph representation, and use it to develop a new class of preconditioners, generalized subgraph preconditioners, that combine the advantages of subgraph preconditioners and Hessian-based preconditioners. I apply them to solve large SfM problems and obtain promising results. Fourth, I develop the incremental subgraph-preconditioned conjugate gradient method for large-scale online SLAM problems. The main idea is to combine the advantages of two state-of-the-art methods, incremental smoothing and mapping, and the subgraph-preconditioned conjugate gradient method. I also show that the new method is efficient, optimal and consistent. To sum up, preconditioning can significantly improve the efficiency of solving large-scale SLAM and SfM problems. While existing preconditioning techniques do not utilize the problem structure and have no performance guarantee, I take the first step toward a more general setting and have promising results.

Convergence acceleration techniques for the iterative solution of system of equations arising in the discretisations of compressible flow problems governed by the steady state Euler or Navier-Stokes equations is considered. The system of PDE is discretised using a finite difference or finite volume method yielding a large sparse system of equations. A solution is computed by integrating the corresponding time dependent problem in time until steady state is reached. A convergence acceleration technique based on semicirculant approximations is applied. For scalar model problems, it is proved that the preconditioned coefficient matrix has a bounded spectrum well separated from the origin. A very simple time marching scheme such as the forward Euler method can be used, and the time step is not limited by a CFL-type criterion. Instead, the time step can asymptotically be chosen as a constant, independent of the number of grid points and the Reynolds number. Numerical experiments show that grid and parameter independent convergence is achieved also in more complicated problem settings. A comparison with a multigrid method shows that the semicirculant convergence acceleration technique is more efficient in terms of arithmetic complexity. Another convergence acceleration technique based on fundamental solutions is proposed. An algorithm based on Fourier technique is provided for the fast application. Scalar model problems are considered and a theory, where the preconditioner is represented as an integral operator is derived. Theory and numerical experiments show that for first order partial differential equations, grid independent convergence is achieved.

Diss. (sammanfattning) Stockholm : Karolinska institutet, 2006. / Härtill 4 uppsatser.

Thesis (Ph. D.)--University of Missouri-Columbia, 2007. / The entire dissertation/thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file (which also appears in the research.pdf); a non-technical general description, or public abstract, appears in the public.pdf file. Vita. Includes bibliographical references.

Thesis (Ph.D.)--Memorial University of Newfoundland, Faculty of Medicine, 2000. / Typescript. Bibliography: p. 137-164.

Introduction In recent years, domain decomposition methods have been used extensively to efficiently solve boundary value problems for partial differential equations in complex{form domains. On the other hand, multilevel techniques on hierarchical data structures also have developed into an effective tool for the construction and analysis of fast solvers. But direct realization of multilevel techniques on a parallel computer system for the global problem in the original domain involves difficult communication problems. I this paper, we present and analyze a combination of these two approaches: domain decomposition and multilevel decomposition on hierarchical structures to design optimal preconditioning operators.

This study is concerned with the development and implementation of a preconditioner for a set of hyperbolic partial differential equations resulting from a new 5-moment closure for the prediction of gas flows both in and out of local equilibrium. This new 5-moment closure offers a robust and efficient system of first-order hyperbolic partial differential equations that has proven to provide an accurate treatment of one-dimensional gases, both in and for significant departures from local thermodynamic equilibrium. However, numerical computations using this model have proven to be difficult as a result of a singularity in the closing flux of the system. This also causes infinitely large wavespeeds in the system. The main goal of this work is to mitigate these numerical issues. Since the solution of a hyperbolic system is characterized by the waves of the system, one could suggest to scale these wavespeeds to remove the arbitrarily large speeds without altering the solution of the system. To accomplish this, this work starts with a detailed study of the behaviour of the system’s wavespeeds, given by the eigenvalues of the flux Jacobian of the system. Since, it is not possible to solve for these eigenvalues explicitly, it is suggested to approximate them by interpolation between the few states at which these waves can be solved for explicitly. With an estimate for the wavespeeds, the nature of the singularity in the system can be analyzed mathematically. The results of this mathematical analysis are used to develop a preconditioner matrix to remove the singularity from the model. To implement the proposed preconditioned model numerically, a centred-difference scheme with artificial dissipation is proposed. A dual-time-stepping strategy is developed and implemented with implicit Euler time marching for both physical and pseudo time iteration. This dual-time treatment allows the preconditioned system to remain applicable to time-accurate problems and is found to greatly increase the robustness of the solution of the steady-state problems. Solutions to several canonical problems for both continuum and non-equilibrium flow are computed and comparisons are made to classical models.

Exascale systems are predicted to have approximately one billion cores, assuming Gigahertz cores. Limitations on affordable network topologies for distributed memory systems of such massive scale bring new challenges to the currently dominant parallel programing model. Currently, there are many efforts to evaluate the hardware and software bottlenecks of exascale designs. It is therefore of interest to model application performance and to understand what changes need to be made to ensure extrapolated scalability. Fast multipole methods (FMM) were originally developed for accelerating N-body problems for particle-based methods in astrophysics and molecular dynamics. FMM is more than an N-body solver, however. Recent efforts to view the FMM as an elliptic PDE solver have opened the possibility to use it as a preconditioner for even a broader range of applications. In this thesis, we (i) discuss the challenges for FMM on current parallel computers and future exascale architectures, with a focus on inter-node communication, and develop a performance model that considers the communication patterns of the FMM for spatially quasi-uniform distributions, (ii) employ this performance model to guide performance and scaling improvement of FMM for all-atom molecular dynamics simulations of uniformly distributed particles, and (iii) demonstrate that, beyond its traditional use as a solver in problems for which explicit free-space kernel representations are available, the FMM has applicability as a preconditioner in finite domain elliptic boundary value problems, by equipping it with boundary integral capability for satisfying conditions at finite boundaries and by wrapping it in a Krylov method for extensibility to more general operators. Compared with multilevel methods, FMM is capable of comparable algebraic convergence rates down to the truncation error of the discretized PDE, and it has superior multicore and distributed memory scalability properties on commodity architecture supercomputers. Compared with other methods exploiting the low rank character of off-diagonal blocks of the dense resolvent operator, FMM-preconditioned Krylov iteration may reduce the amount of communication because it is matrix-free and exploits the tree structure of FMM. Fast multipole-based solvers and preconditioners are demonstrably poised to play a leading role in exascale computing.

A loss of sarcolemmal dystrophin was observed by immuno-fluorescence studies in rabbit hearts subjected to in situ myocardial ischemia and by immuno-blotting of the Triton soluble membrane fraction of isolated rabbit cardiomyocytes subjected to in vitro ischemia. This ischemic loss of dystrophin was a specific event in that no ischemic loss of sarcolemmal α-sarcoglycan, γ-sarcoglycan, αDG, or βDG was observed. The maintenance of sarcolemmal βDG (43 Kd) during ischemia was interesting in that dystrophin binds to the C-terminus of βDG. However, during late in vitro ischemia, a 30 Kd band was observed that was immuno-reactive for βDG. Additionally, this 30 Kd-βDG band was observed in rabbit myocardium subjected to autolysis. Finally, the 30 Kd-βDG was observed in the purified sarcolemmal fraction of rabbit cardiomyocytes subjected to a prolonged period of in vitro ischemia, confirming the sarcolemmal localization of this band. The potential patho-physiologic significance of this band was indicated by the appearance of this band at 120-180 min of in vitro ischemia, directly correlating with the onset of irreversible injury, as manifested by osmotic fragility. Additionally the appearance of this band was significantly reduced by the endogenous cardioprotective mechanism, in vitro ischemic preconditioning, which delays the onset of osmotic fragility. In addition to dystrophin, βDG binds caveolin-3 and Grb-2 at its C-terminus. The presence of Grb-2 and caveolin-3 in the membrane fractions of oxygenated and ischemic cardiomyocytes was determined by Western blotting. An increase in the level of membrane Grb-2 and caveolin-3 was observed following ischemic preconditioning as compared to control cells. The formation of this 30 Kd-βDG degradation product is potentially related to the transition from the reversible to the irreversible phase of myocardial ischemic cell injury and a decrease in 30 Kd-βDG might mediate the cardioprotection provided by ischemic preconditioning.