No description available.

Accelerating the convergence rate of Krylov subspace methods with parallelizable preconditioners is essential for obtaining effective iterative solvers for very large linear systems of equations. Substructuring provides a framework for constructing robust and parallel preconditioners for linear systems arising from the discretization of boundary value problems. Although collocation is a very general and effective discretization technique for many PDE problems, there has been relatively little work on preconditioners for collocation problems. This thesis proposes two preconditioning methods for solving linear systems of equations arising from Hermite bicubic collocation discretization of elliptic partial differential equations on square domains with mixed boundary conditions. The first method, called <i>edge preconditioning</i>, is based on a decomposition of the domain in parallel strips, and the second, called <i>edge-vertex preconditioning</i>, is based on a two-dimensional decomposition. The preconditioners are derived in terms of two special rectangular grids -- a coarse grid with diameter <i>H</i> and a hybrid coarse/fine grid -- which together with the fine grid of diameter <i>h</i> provide the framework for approximating the interface problem induced by substructuring. We show that the proposed methods are effective for nonsymmetric indefinite problems, both from the point of view of the cost per iteration and of the number of iterations. For an appropriate choice of <i>H</i>, the edge preconditioner requires <i>O(N)</i> arithmetic operations per iteration, while the edge-vertex preconditioner requires <i>O(N^4/3)</i> operations, where <i>N</i> is the number of unknowns. For the edge-vertex preconditioner, the number of iterations is almost constant when <i>h</i> and <i>H</i> decrease such that <i>H/h</i> is held constant and it increases very slowly with <i>H</i> when <i>h</i> is held constant. For both the edge- and edge-vertex preconditioners the number of iterations depends only weakly on <i>h</i> when <i>H</i> is constant. The edge-vertex preconditioner outperforms the edge-preconditioner for small enough <i>H</i>. Numerical experiments illustrate the parallel efficiency of the preconditioners which is similar or even better than that provided by the well-known PETSc parallel software library for scientific computing. / Ph. D.

In this thesis we study efficient parallel iterative solution algorithms for multi-physics problems. In particular, we consider fluid structure interaction (FSI) problems, a type of multi-physics problem in which a fluid and a deformable solid interact. All computations were performed in Oomph-Lib, a finite element library for the simulation of multi-physics problems. In Oomph-Lib, the constituent problems in a multi-physics problem are coupled monolithically, and the resulting system of non-linear equations solved with Newton's method. This requires the solution of sequences of large, sparse linear systems, for which optimal solvers are essential. The linear systems arising from the monolithic discretisation of multi-physics problems are natural candidates for solution with block-preconditioned Krylov subspace methods.We developed a generic framework for the implementation of block preconditioners within Oomph-Lib. Furthermore the framework is parallelised to facilitate the efficient solution of very large problems. This framework enables the reuse of all of Oomph-Lib's existing linear algebra infrastructure and preconditioners (including block preconditioners). We will demonstrate that a wide range of block preconditioners can be seamlessly implemented in this framework, leading to optimal iterative solvers with good parallel scaling.We concentrate on the development of an effective preconditioner for a FSI problem formulated in an arbitrary Lagrangian Eulerian (ALE) framework with pseudo-solid node updates (for the deforming fluid mesh). We begin by considering the pseudo-solid subsidiary problem; the deformation of a solid governed by equations of large displacement elasticity, subject to a prescribed boundary displacement imposed with Lagrange multiplier. We present a robust, optimal, augmented-Lagrangian type preconditioner for the resulting saddle-point linear system and prove analytically tight bounds for the spectrum of the preconditioned operator with respect to the discrete problem size.This pseudo-solid preconditioner is incorporated into a block preconditioner for the full FSI problem. One key feature of the FSI preconditioner is that existing optimal single physics preconditioners (such as the well known Navier-Stokes Least Squares Commutator preconditioner) can be employed to approximately solve the linear systems associated with the constituent sub-problems. We evaluate its performance on selected 2D and 3D problems. The preconditioner is optimal for most problems considered. In cases when sub-optimality is detected, we explain the reasons for such behavior and suggest potential improvements.

H-matrix techniques use a data-sparse tree structure to represent a dense or a sparse matrix. The leaves of the tree store matrix sub-blocks that are represented in full-matrix format or Rk-matrix (low rank matrix) format. H-matrix arithmetic is defined over the H-matrix representation, which includes operations such as addition, multiplication, inversion, and LU factorization. These H-matrix operations approximate results with almost optimal computational complexity. Based on the properties of H-matrices, the H-matrix preconditioner technique has been introduced. It uses H-matrix operations to construct preconditioners, which are used in iterative methods to speed up the solution of large systems of linear equations (Ax = b). To apply the H-matrix preconditioner technique, the first step is to represent a problem in H-matrix format. The approaches to construct an H-matrix can be divided into two categories: geometric approaches and algebraic approaches. In this thesis, we present our contributions to algebraic H-matrix construction approaches and H-matrix preconditioner technique. We have developed a new algebraic H-matrix construction approach based on matrix graphs and multilevel graph clustering approaches. Based on the new construction approach, we have also developed a scheme to build algebraic H-matrix preconditioners for systems of saddle point type. To verify the effectiveness of our new construction approach and H-matrix preconditioner scheme, we have applied them to solve various systems of linear equations arising from finite element methods and meshfree methods. The experimental results show that our preconditioners are competitive to other H-matrix preconditioners based on domain decomposition and existing preconditioners such as JOR and AMG preconditioners. Our H-matrix construction approach and preconditioner technique provide an alternative effective way to solve large systems of linear equations.

For sequences of related linear systems, the computation of a preconditioner for every system can be expensive. Often a fixed preconditioner is used, but this may not be effective as the matrix changes. This research examines the benefits of both reusing and recycling preconditioners, with special focus on ILUTP and factorized sparse approximate inverses and proposes an update that we refer to as a sparse approximate map or SAM update. Analysis of the residual and eigenvalues of the map will be provided. Applications include the Quantum Monte Carlo method, model reduction, oscillatory hydraulic tomography, diffuse optical tomography, and Helmholtz-type problems. / Master of Science

[pt] Muitos problemas provenientes do mundo real podem ser modelados por sistemas de equações diferenciais parciais (EDP´s). No entanto, as equações resultantes da discretização produzem matrizes grandes e freqüentementes mal condicionadas. Este trabaho implementa o método de elementos finitos mistos para resolver numericamente um sistema de EDP´s oriundo de um modelo de escoamento de fluidos em meios porosos e melhora sua performance usando precondicionadores e processamento paralelo. / [en] Many problems arising from real world can be represented by systems of partial diferential equations (PDE´s). However, the resulting discrete equations produce large and frequently bad conditioned matrices. This work implements the mixed finite element method to numerically solve a system of PDE´s coming from a multiphase flow in porous media model and improve its performance by preconditioners and parallel processing.

Solving linear systems of equations is an integral part of most scientific simulations. In recent years, there has been a considerable interest in large scale scientific simulation of complex physical processes. Iterative solvers are usually preferred for solving linear systems of such magnitude due to their lower computational requirements. Currently, computational scientists have access to a multitude of iterative solver options available as "plug-and- play" components in various problem solving environments. Choosing the right solver configuration from the available choices is critical for ensuring convergence and achieving good performance, especially for large complex matrices. However, identifying the "best" preconditioned iterative solver and parameters is challenging even for an expert due to issues such as the lack of a unified theoretical model, complexity of the solver configuration space, and multiple selection criteria. Therefore, it is desirable to have principled practitioner-centric strategies for identifying solver configuration(s) for solving large linear systems. The current dissertation presents a general practitioner-centric framework for (a) problem independent retrospective analysis, and (b) problem-specific predictive modeling of performance data. Our retrospective performance analysis methodology introduces new metrics such as area under performance-profile curve and conditional variance-based finetuning score that facilitate a robust comparative performance evaluation as well as parameter sensitivity analysis. We present results using this analysis approach on a number of popular preconditioned iterative solvers available in packages such as PETSc, Trilinos, Hypre, ILUPACK, and WSMP. The predictive modeling of performance data is an integral part of our multi-stage approach for solver recommendation. The key novelty of our approach lies in our modular learning based formulation that comprises of three sub problems: (a) solvability modeling, (b) performance modeling, and (c) performance optimization, which provides the flexibility to effectively target challenges such as software failure and multiobjective optimization. Our choice of a "solver trial" instance space represented in terms of the characteristics of the corresponding "linear system", "solver configuration" and their interactions, leads to a scalable and elegant formulation. Empirical evaluation of our approach on performance datasets associated with fairly large groups of solver configurations demonstrates that one can obtain high quality recommendations that are close to the ideal choices.

Orientador: Aurelio Ribeiro Leite de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T19:56:24Z (GMT). No. of bitstreams: 1 Silva_LinoMarcosda_D.pdf: 2297954 bytes, checksum: 2213b987c2753edec9152998b30b7c74 (MD5) Previous issue date: 2014 / Resumo: O método de pontos interiores para programação linear resolve em poucas iterações problemas de grande porte. No entanto, requer a cada iteração a resolução de dois sistemas lineares, os quais possuem a mesma matriz de coeficientes. Essa etapa se constitui no passo mais caro do método por aumentar consideravelmente o tempo de processamento e a necessidade de armazenamento de dados. Reduzir o tempo de solução dos sistemas lineares é, portanto, uma forma de melhorar o desempenho do método. De um modo geral, problemas de programação linear de grande porte possuem matrizes esparsas. Uma vez que os sistemas lineares a serem resolvidos são simétricos positivos definidos, métodos iterativos como o método dos gradientes conjugados precondicionado podem ser utilizados na resolução dos mesmos. Além disso, fatores de Cholesky incompletos podem ser utilizados como precondicionadores para o problema. Por outro lado, fatorações incompletas podem sofrer falhas na diagonal durante o processo de fatoração, e quando tais falhas ocorrem uma correção é efetuada somando-se um valor positivo aos elementos da diagonal da matriz do sistema linear e a fatoração da nova matriz é reiniciada, aumentando dessa forma o tempo de precondicionamento, quer seja devido a reconstrução do precondicionador, quer seja devido a perda de qualidade do mesmo. O precondicionador fatoração controlada de Cholesky tem um bom desempenho nas iterações iniciais do método de pontos interiores e tem sido importante nas implementações de abordagens de precondicionamento híbrido. No entanto, sendo uma fatoração incompleta, o mesmo não está livre da ocorrência de falhas no cálculo do pivô. Neste estudo propomos duas modificações à fatoração controlada de Cholesky a fim de evitar ou diminuir o número de reinícios da fatoração das matrizes diagonalmente modificadas. Resultados computacionais mostram que a técnica pode reduzir significativamente o tempo de resolução de certas classes de problemas de programação linear via método de pontos interiores / Abstract: The interior point method solves large linear programming problems in few iterations. However, each iteration requires computing the solution of one or more linear systems. This constitutes the most expensive step of the method by greatly increasing the processing time and the need for data storage. According to it, reducing the time to solve the linear system is a way of improving the method performance. In general, large linear programming problems have sparse matrices. Since the linear systems to be solved are symmetric positive definite, iterative methods such as the preconditioned conjugate gradient method can be used to solve them. Furthermore, incomplete Cholesky factor can be used as a preconditioner to the problem. On the other hand, breakdown may occur during incomplete factorizations. When such failure occur, a correction is made by adding a positive number to diagonal elements of the linear system matrix and the factorization of the new matrix is restarted, thus increasing the time of preconditioning, either due to computing the preconditioner, or due to loss of its quality. The controlled Cholesky factorization preconditioner performs well in early iterations of interior point methods and has been important on implementations of hybrid preconditioning approaches. However, being an incomplete factorization, it is not free from faulty pivots. In this study we propose two modifications to the controlled Cholesky factorization in order to avoid or decrease the refactoring diagonally modified matrices number. Computational results show that the proposed techniques can significantly reduces the time for solving linear programming problems by interior point method / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

The preprint delivers an efficient solution technique for the numerical simulation of crack propagation of 2D linear elastic formulations based on finite elements together with the conjugate gradient method in order to solve the corresponding linear equation systems. The developed iterative numerical approach using hierarchical preconditioners comprehends the interesting feature that the hierarchical data structure will not be destroyed during crack propagation. Thus, one gets the possibility to simulate crack advance in a very effective numerical manner including adaptive mesh refinement and mesh coarsening. Test examples are presented to illustrate the efficiency of the given approach. Numerical simulations of crack propagation are compared with experimental data.

This paper concerns the solution of plate bending problems in domains composed of rectangles. Domain decomposition (DD) is the basic tool used for both the parallelization of the conjugate gradient method and the construction of efficient parallel preconditioners. A so-called Dirich- let DD preconditioner for systems of linear equations arising from the fi- nite element approximation by non-conforming Adini elements is derived. It is based on the non-overlapping DD, a multilevel preconditioner for the Schur-complement and a fast, almost direct solution method for the Dirichlet problem in rectangular domains based on fast Fourier transform. Making use of Xu's theory of the auxiliary space method we construct an optimal preconditioner for plate problems discretized by conforming Bogner-Fox-Schmidt rectangles. Results of numerical experiments carried out on a multiprocessor sys- tem are given. For the test problems considered the number of iterations is bounded independent of the mesh sizes and independent of the number of subdomains. The resulting parallel preconditioned conjugate gradient method requiresO(h^-2 ln h^-1 ln epsilon^-11) arithmetical operations per processor in order to solve the finite element equations with the relative accuracy epsilon.