Preconditioner | EPFL Graph Search

In mathematics, preconditioning is the application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solving methods. Preconditioning is typically related to reducing a condition number of the problem. The preconditioned problem is then usually solved by an iterative method. Preconditioning for linear systems In linear algebra and numerical analysis, a preconditioner P of a matrix A is a matrix such that P^{-1}A has a smaller condition number than A. It is also common to call T=P^{-1} the preconditioner, rather than P, since P itself is rarely explicitly available. In modern preconditioning, the application of T = P^{-1}, i.e., multiplication of a column vector, or a block of column vectors, by T = P^{-1}, is commonly performed in a matrix-free fashion, i.e., where neither

Multi space reduced basis preconditioners for parametrized partial differential equations

Niccolò Dal Santo

The multiquery solution of parametric partial differential equations (PDEs), that is, PDEs depending on a vector of parameters, is computationally challenging and appears in several engineering contexts, such as PDE-constrained optimization, uncertainty quantification or sensitivity analysis. When using the finite element (FE) method as approximation technique, an algebraic system must be solved for each instance of the parameter, leading to a critical bottleneck when we are in a multiquery context, a problem which is even more emphasized when dealing with nonlinear or time dependent PDEs. Several techniques have been proposed to deal with sequences of linear systems, such as truncated Krylov subspace recycling methods, deflated restarting techniques and approximate inverse preconditioners; however, these techniques do not satisfactorily exploit the parameter dependence. More recently, the reduced basis (RB) method, together with other reduced order modeling (ROM) techniques, emerged as an efficient tool to tackle parametrized PDEs. In this thesis, we investigate a novel preconditioning strategy for parametrized systems which arise from the FE discretization of parametrized PDEs. Our preconditioner combines multiplicatively a RB coarse component, which is built upon the RB method, and a nonsingular fine grid preconditioner. The proposed technique hinges upon the construction of a new Multi Space Reduced Basis (MSRB) method, where a RB solver is built at each step of the chosen iterative method and trained to accurately solve the error equation. The resulting preconditioner directly exploits the parameter dependence, since it is tailored to the class of problems at hand, and significantly speeds up the solution of the parametrized linear system. We analyze the proposed preconditioner from a theoretical standpoint, providing assumptions which lead to its well-posedness and efficiency. We apply our strategy to a broad range of problems described by parametrized PDEs: (i) elliptic problems such as advection-diffusion-reaction equations, (ii) evolution problems such as time-dependent advection-diffusion-reaction equations or linear elastodynamics equations (iii) saddle-point problems such as Stokes equations, and, finally, (iv) Navier-Stokes equations. Even though the structure of the preconditioner is similar for all these classes of problems, its fine and coarse components must be accurately chosen in order to provide the best possible results. Several comparisons are made with respect to the current state-of-the-art preconditioning and ROM techniques. Finally, we employ the proposed technique to speed up the solution of problems in the field of cardiovascular modeling.

EPFL2018

Efficient Preconditioning of hp-FEM Matrices by Hierarchical Low-Rank Approximations

Paolo Gatto, Jan Sickmann Hesthaven

We introduce a preconditioner based on a hierarchical low-rank compression scheme of Schur complements. The construction is inspired by standard nested dissection, and relies on the assumption that the Schur complements can be approximated, to high precision, by Hierarchically-Semi-Separable matrices. We build the preconditioner as an approximate factorization of a given matrix A, and no knowledge of A in assembled form is required by the construction. The factorization is amenable to fast inversion, and the action of the inverse can be determined fast as well. We investigate the behavior of the preconditioner in the context of DG finite element approximations of elliptic and hyperbolic problems, with respect to both the mesh size and the order of approximation.

Springer Verlag2017

Multi space reduced basis preconditioners for parametrized partial differential equations

Niccolò Dal Santo

EPFL2018