The GMRES method is a widely used iterative method for solving the linear systems, of the form Ax = b, especially for the solution of discretized partial differential equations. With an appropriate preconditioner, the solution of the linear system Ax = b can be achieved with less computational effort. Additive Schwarz Preconditioners have two good properties. First, they are easily parallelizable, since several smaller linear systems need to be solved: one system for each of the sub-domains, usually corresponding to the restriction of the differential operator to that subdomain. These are called local problems. Second, if a coarse problem is introduced, they are optimal in the sense that bounds on the convergence rate of the preconditioned iterative method are independent (or slowly dependent) on the finite element mesh size and the number of subproblems. We study certain cases where the same optimality can be obtained without a coarse grid correction. In another part of this thesis we consider inexact GMRES when applied to singular (or nearly singular) linear systems. This applies when instead of matrix-vector products with A, one uses A = A+E for some error matrix E which usually changes from one iteration to the next. Following a similar study by Simoncini and Szyld (2003) for nonsingular systems, we prescribe how to relax the exactness of the matrixvector product and still achieve the desired convergence. In addition, similar criteria is given to guarantee that the computed residual with the inexact method is close to the true residual. Furthermore, we give a new computable criteria to determine the inexactness of matrix-vector product using in inexact CG, and applied it onto control problems governed by parabolic partial differential equations. / Mathematics

This thesis presents a new preconditioner for elliptic PDE problems on unstructured meshes. Using ideas from second generation wavelets, a multi-resolution basis is constructed to effectively compress the inverse of the matrix, resolving the sparsity vs. quality problem of standard approximate inverses. This finally allows the approximate inverse approach to scale well, giving fast convergence for Krylov subspace accelerators on a wide variety of large unstructured problems. Implementation details are discussed, including ordering and construction of factored approximate inverses, discretization and basis construction in one and two dimensions, and possibilities for parallelism. The numerical experiments in one and two dimensions confirm the capabilities of the scheme. Along the way I highlight many new avenues for research, including the connections to multigrid and other multi-resolution schemes.

This thesis presents a new preconditioner for elliptic PDE problems on unstructured meshes. Using ideas from second generation wavelets, a multi-resolution basis is constructed to effectively compress the inverse of the matrix, resolving the sparsity vs. quality problem of standard approximate inverses. This finally allows the approximate inverse approach to scale well, giving fast convergence for Krylov subspace accelerators on a wide variety of large unstructured problems. Implementation details are discussed, including ordering and construction of factored approximate inverses, discretization and basis construction in one and two dimensions, and possibilities for parallelism. The numerical experiments in one and two dimensions confirm the capabilities of the scheme. Along the way I highlight many new avenues for research, including the connections to multigrid and other multi-resolution schemes.

In this paper we consider the well-known BPX-preconditioner in conjunction with adaptive FEM. We present an algorithm which enables us to compute the preconditioner with optimal complexity by a total of only O(DoF) additional memory. Furthermore, we show how to combine the BPX-preconditioner with an overlapping Additive-Schwarz-preconditioner to obtain a preconditioner for finite element spaces with arbitrary polynomial degree distributions. Numerical examples illustrate the efficiency of the algorithms.

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.

P-version finite element method for the second order elliptic equation in an arbitrary sufficiently smooth domain is studied in the frame of DD method. Two types square reference elements are used with the products of the integrated Legendre's polynomials for the coordinate functions. There are considered the estimates for the condition numbers, preconditioning of the problems arising on subdomains and the Schur complement, the derivation of the DD preconditioner. For the result we obtain the DD preconditioner to which corresponds the generalized condition number of order (logp )2 . The paper consists of two parts. In part I there are given some preliminary results for 1D case, condition number estimates and some inequalities for 2D reference element. Part II is devoted to the derivation of the Schur complement preconditioner and conditionality number estimates for the p-version finite element matrixes. Also DD preconditioning is considered.

The primary motivation of this research is to develop and investigate parallel preconditioners for linear elliptic partial differential equations. Three preconditioners are studied: block-Jacobi preconditioner (BJ), a two-level tangential preconditioner (D0), and a three-level preconditioner (D1). Performance and scalability on a distributed memory parallel computer are considered. Communication cost and redundancy are explored as well. After experiments and analysis, we find that the three-level preconditioner D1 is the most efficient and scalable parallel preconditioner, compared to BJ and D0. The D1 preconditioner reduces both the number of iterations and computational time substantially. A new hybrid preconditioner is suggested which may combine the best features of D0 and D1. / Master of Science

This project is concerned with the development and implementation of a novel preconditioning method for the iterative solution of linear systems that arise in the finite element discretisation of the incompressible Navier-Stokes equations with weakly imposed boundary conditions. In this context we studied an augmented approach where the Schur complement associated with the momentum block of the Navier-Stokes equations has special sparse structure. We follow the standard inf-sup stable method of discretising the Navier-Stokes equations by the Taylor-Hood elements with the Lagrange multiplier constraints discretised using the same order approximation on matching grids. The resulting system of nonlinear equations is solved iteratively by Newton's method. The spectrum of the linearised Oseen's problem, preconditioned by the exact augmentation preconditioner was analysed. Then we developed inexact versions of the preconditioner aimed at achieving optimal scaling of the algorithm in terms of computational resources and wall-clock times. The experimental evaluation of the methodology involve a number of benchmark problems in two and three spatial dimensions. The obtained results demonstrate efficiency, robustness and almost optimal scaling of the solution algorithm with respect to the discrete problem size. We used OOMPH-LIB as a testbed for our experiments. The preconditioning strategies were implemented using OOMPH-LIB's Parallel Block Preconditioning Framework. The initial version of the software was significantly upgraded during the course of this project with newly implemented functionalities to facilitate the rapid development of sophisticated hierarchical design of parallel block preconditioners. Parallel performance analysis of the newly introduced functionalities demonstrate negligible overhead in terms of wall-clock time and the framework demonstrate good weak and strong parallel scaling.

In this paper we consider the well-known BPX-preconditioner in conjunction with adaptive FEM. We present an algorithm which enables us to compute the preconditioner with optimal complexity by a total of only O(DoF) additional memory. Furthermore, we show how to combine the BPX-preconditioner with an overlapping Additive-Schwarz-preconditioner to obtain a preconditioner for finite element spaces with arbitrary polynomial degree distributions. Numerical examples illustrate the efficiency of the algorithms.

Please download this dissertation to see the abstract.