Search

Randomized methods are becoming increasingly popular in numerical linear algebra. However, few attempts have been made to use them in developing preconditioners. Our interest lies in solving large-scale sparse symmetric positive definite linear systems of equations, where the system matrix is preordered to doubly bordered block diagonal form (for example, using a nested dissection ordering). We investigate the use of randomized methods to construct high-quality preconditioners. In particular, we propose a new and efficient approach that employs Nyström’s method for computing low rank approximations to develop robust algebraic two-level preconditioners. Construction of the new preconditioners involves iteratively solving a smaller but denser symmetric positive definite Schur complement system with multiple right-hand sides. Numerical experiments on problems coming from a range of application areas demonstrate that this inner system can be solved cheaply using block conjugate gradients and that using a large convergence tolerance to limit the cost does not adversely affect the quality of the resulting Nyström–Schur two-level preconditioner. [ABSTRACT FROM AUTHOR]

We introduce a new and generic approximation to Schur complements arising from inf-sup stable mixed finite element discretizations of self-adjoint multiphysics problems. The approximation exploits the discretization mesh by forming local, or element, Schur complements of an appropriate system and projecting them back to the global degrees of freedom. The resulting Schur complement approximation is sparse, has low construction cost (with the same order of operations as assembling a general finite element matrix), and can be solved using off-the-shelf techniques, such as multigrid. Using results from saddle point theory, we give conditions such that this approximation is spectrally equivalent to the global Schur complement. We present several numerical results to demonstrate the viability of this approach on a range of applications. Interestingly, numerical results show that the method gives an effective approximation to the nonsymmetric Schur complement from the steady state Navier--Stokes equations. [ABSTRACT FROM AUTHOR]

Null-space methods for solving saddle point systems of equations have long been used to transform an indefinite system into a symmetric positive definite one of smaller dimension. A number of independent works in the literature have identified that we can interpret a null-space method as a matrix factorization. We review these findings, highlight links between them, and bring them into a unified framework. We also investigate the suitability of using null-space factorizations to derive sparse direct methods and present numerical results for both practical and academic problems. [ABSTRACT FROM AUTHOR]

The null-space method is a technique that has been used for many years to reduce a saddle point system to a smaller, easier to solve, symmetric positive definite system. This method can be understood as a block factorization of the system. Here we explore the use of preconditioners based on incomplete versions of a particular null-space factorization and compare their performance with the equivalent Schur complement based preconditioners. We also describe how to apply the nonsymmetric preconditioners proposed using the conjugate gradient method (CG) with a nonstandard inner product. This requires an exact solve with the (1,1) block, and the resulting algorithm is applicable in other cases where Bramble-Pasciak CG is used. We verify the efficiency of the newly proposed preconditioners on a number of test cases from a range of applications. [ABSTRACT FROM AUTHOR]

Solving problems regarding the optimal control of partial differential equations (PDEs)--also known as PDF-constrained optimization--is a frontier area of numerical analysis. Of particular interest is the problem of flow control, where one would like to effect some desired flow by exerting, for example, an external force. The bottleneck in many current algorithms is the solution of the optimality system--a system of equations in saddle point form that is usually very large and ill conditioned. In this paper we describe two preconditioners--a block diagonal preconditioner for the minimal residual method and a block lower-triangular preconditioner for a nonstandard conjugate gradient method--which can be effective when applied to such problems where the PDEs are the Stokes equations. We consider only distributed control here, although we believe other problems could be treated in the same way. We give numerical results, and we compare these with those obtained by solving the equivalent forward problem using similar techniques. [ABSTRACT FROM AUTHOR]

In this paper we investigate the possibility of using a block-triangular preconditioner for saddle point problems arising in PDE-constrained optimization. In particular, we focus on a conjugate gradient-type method introduced by Bramble and Pasciak that uses self-adjointness of the preconditioned system in a non-standard inner product. We show when the Chebyshev semi-iteration is used as a preconditioner for the relevant matrix blocks involving the finite element mass matrix that the main drawback of the Bramble-Pasciak method-the appropriate scaling of the preconditioners-is easily overcome. We present an eigenvalue analysis for the block-triangular preconditioners that gives convergence bounds in the non-standard inner product and illustrates their competitiveness on a number of computed examples. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Optimization problems with constraints which require the solution of a partial differential equation arise widely in many areas of the sciences and engineering, particularly in problemsof design. The solution of such PDE-constrained optimization problems is usually a major computational task. Here we consider simple problems of this type: distributed control problems in which the 2and 3-dimensional Poisson problem is the PDE. The large-dimensional linear systems which result from discretization and which need to be solved are of saddle-point type. We introduce two optimal preconditioners for these systems, which lead to convergence of symmetric Krylov subspace iterative methods in a number of iterations which does not increase with the dimension of the discrete problem. These preconditioners are block structured and involve standard multigrid cycles. The optimality of the preconditioned iterative solver is proved theoretically and verified computationally in several test cases. The theoretical proof indicates that these approaches may have much broader applicability for other PDEs. [ABSTRACT FROM AUTHOR]

Domain decomposition methods are among the most efficient for solving sparse linear systems of equations. Their effectiveness relies on a judiciously chosen coarse space. Originally introduced and theoretically proved to be efficient for self-adjoint operators, spectral coarse spaces have been proposed in the past few years for indefinite and non-self-adjoint operators. This paper presents a new spectral coarse space that can be constructed in a fully algebraic way unlike most existing spectral coarse spaces. We present theoretical convergence results for Hermitian positive definite diagonally dominant matrices. Numerical experiments and comparison against state-of-the-art preconditioners in the multigrid community show that the resulting two-level Schwarz preconditioner is efficient especially for non-self-adjoint operators. Furthermore, in this case, our proposed preconditioner outperforms state-of-the-art preconditioners. [ABSTRACT FROM AUTHOR]

Projected Krylov methods are full-space formulations of Krylov methods that take place in a nullspace. Provided projections into the nullspace can be computed accurately, those methods only require products between an operator and vectors lying in the nullspace. We provide systematic principles for obtaining the projected form of any well-defined Krylov method. Projected Krylov methods are mathematically equivalent to constraint-preconditioned Krylov methods provided the initial guess is well chosen, but require less memory. As a consequence, there are situations where certain known methods such as MINRES and SYMMLQ are well defined in the presence of an indefinite preconditioner. [ABSTRACT FROM AUTHOR]