Local preconditioners for two‐level non‐overlapping domain decomposition methods

We consider additive two‐level preconditioners, with a local and a global component, for the Schur complement system arising in non‐overlapping domain decomposition methods. We propose two new parallelizable local preconditioners. The first one is a computationally cheap but numerically relevant alternative to the classical block Jacobi preconditioner. The second one exploits all the information from the local Schur complement matrices and demonstrates an attractive numerical behaviour on heterogeneous and anisotropic problems. We also propose two implementations based on approximate Schur complement matrices that are cheaper alternatives to construct the given preconditioners but that preserve their good numerical behaviour. Through extensive computational experiments we study the numerical scalability and the robustness of the proposed preconditioners and compare their numerical performance with well‐known robust preconditioners such as BPS and the balancing Neumann–Neumann method. Finally, we describe a parallel implementation on distributed memory computers of some of the proposed techniques and report parallel performances. Copyright © 2001 John Wiley & Sons, Ltd.     

Schur complement‐based domain decomposition preconditioners with low‐rank corrections

This paper introduces a robust preconditioner for general sparse matrices based on low‐rank approximations of the Schur complement in a Domain Decomposition framework. In this ‘Schur Low Rank’ preconditioning approach, the coefficient matrix is first decoupled by a graph partitioner, and then a low‐rank correction is exploited to compute an approximate inverse of the Schur complement associated with the interface unknowns. The method avoids explicit formation of the Schur complement. We show the feasibility of this strategy for a model problem and conduct a detailed spectral analysis for the relation between the low‐rank correction and the quality of the preconditioner. We first introduce the SLR preconditioner for symmetric positive definite matrices and symmetric indefinite matrices if the interface matrices are symmetric positive definite. Extensions to general symmetric indefinite matrices as well as to nonsymmetric matrices are also discussed. Numerical experiments on general matrices illustrate the robustness and efficiency of the proposed approach. Copyright © 2016 John Wiley & Sons, Ltd.     

Projected Schur complement method for solving non‐symmetric systems arising from a smooth fictitious domain approach

This paper deals with a fast method for solving large‐scale algebraic saddle‐point systems arising from fictitious domain formulations of elliptic boundary value problems. A new variant of the fictitious domain approach is analyzed. Boundary conditions are enforced by control variables introduced on an auxiliary boundary located outside the original domain. This approach has a significantly higher convergence rate; however, the algebraic systems resulting from finite element discretizations are typically non‐symmetric. The presented method is based on the Schur complement reduction. If the stiffness matrix is singular, the reduced system can be formulated again as another saddle‐point problem. Its modification by orthogonal projectors leads to an equation that can be efficiently solved using a projected Krylov subspace method for non‐symmetric operators. For this purpose, the projected variant of the BiCGSTAB algorithm is derived from the non‐projected one. The behavior of the method is illustrated by examples, in which the BiCGSTAB iterations are accelerated by a multigrid strategy. Copyright © 2007 John Wiley & Sons, Ltd.     

Partitioned penalty methods for the transport equation in the evolutionary Stokes–Darcy‐transport problem

There has been a surge of work on models for coupling surface‐water with groundwater flows which is at its core the Stokes–Darcy problem, as well as methods for uncoupling the problem into subdomain, subphysics solves. The resulting (Stokes–Darcy) fluid velocity is important because the flow transports contaminants. The numerical analysis and algorithm development for the evolutionary transport problem has, however, focused on a quasi‐static Stokes–Darcy model and a single domain (fully coupled) formulation of the transport equation. This report presents a numerical analysis of a partitioned method for contaminant transport for the fully evolutionary system. The algorithm studied is unconditionally stable with one subdomain solve per step. Numerical experiments are given using the proposed algorithm that investigates the effects of the penalty parameters on the convergence of the approximations.     

(Almost) matrix‐free solver for piecewise linear functions in abs‐normal form

The abs‐normal form (ANF) is a compact algebraic representation for piecewise linear functions. These functions can be used to approximate piecewise smooth functions and contain valuable information about the nonsmoothness of the investigated function. The information helps to define step directions within general Newton methods that obey the structure of the original function and typically yield better convergence. However, the computation of the generalized Newton directions requires the solution of a piecewise linear equation in ANF. It was observed that the ANF can become very large, even for simple functions. Hence, if a solver is based on the ANF and uses the (Schur‐complement) matrices of the explicit ANF representation, it has to be considered computationally expensive. In this paper, we will address this question and present the first (almost) matrix‐free versions of some solver for ANFs. The theoretical discussion is supported by some numerical run‐time experiments.     

BEM‐FEM coupling for the 1D Klein–Gordon equation

A transmission (bidomain) problem for the one‐dimensional Klein–Gordon equation on an unbounded interval is numerically solved by a boundary element method‐finite element method (BEM‐FEM) coupling procedure. We prove stability and convergence of the proposed method by means of energy arguments. Several numerical results are presented, confirming theoretical results. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 2042–2082, 2014     

A spatial domain decomposition method for parabolic optimal control problems

We present a non-overlapping spatial domain decomposition method for the solution of linear–quadratic parabolic optimal control problems. The spatial domain is decomposed into non-overlapping subdomains. The original parabolic optimal control problem is decomposed into smaller problems posed on space–time cylinder subdomains with auxiliary state and adjoint variables imposed as Dirichlet boundary conditions on the space–time interface boundary. The subdomain problems are coupled through Robin transmission conditions. This leads to a Schur complement equation in which the unknowns are the auxiliary state adjoint variables on the space-time interface boundary. The Schur complement operator is the sum of space–time subdomain Schur complement operators. The application of these subdomain Schur complement operators is equivalent to the solution of an subdomain parabolic optimal control problem. The subdomain Schur complement operators are shown to be invertible and the application of their inverses is equivalent to the solution of a related subdomain parabolic optimal control problem. We introduce a new family of Neumann–Neumann type preconditioners for the Schur complement system including several different coarse grid corrections. We compare the numerical performance of our preconditioners with an alternative approach recently introduced by Benamou.     

An iterative solver for the Oseen problem and numerical solution of incompressible Navier–Stokes equations

Incompressible unsteady Navier–Stokes equations in pressure–velocity variables are considered. By use of the implicit and semi‐implicit schemes presented the resulting system of linear equations can be solved by a robust and efficient iterative method. This iterative solver is constructed for the system of linearized Navier–Stokes equations. The Schur complement technique is used. We present a new approach of building a non‐symmetric preconditioner to solve a non‐symmetric problem of convection–diffusion and saddle‐point type. It is shown that handling the differential equations properly results in constructing efficient solvers for the corresponding finite linear algebra systems. The method has good performance for various ranges of viscosity and can be used both for 2D and 3D problems. The analysis of the method is still partly heuristic, however, the mathematically rigorous results are proved for certain cases. The proof is based on energy estimates and basic properties of the underlying partial differential equations. Numerical results are provided. Additionally, a multigrid method for the auxiliary convection–diffusion problem is briefly discussed. Copyright © 1999 John Wiley & Sons, Ltd.     

Multigrid transfers for nonsymmetric systems based on Schur complements and Galerkin projections

A framework is proposed for constructing algebraic multigrid transfer operators suitable for nonsymmetric positive definite linear systems. This framework follows a Schur complement perspective as this is suitable for both symmetric and nonsymmetric systems. In particular, a connection between algebraic multigrid and approximate block factorizations is explored. This connection demonstrates that the convergence rate of a two‐level model multigrid iteration is completely governed by how well the coarse discretization approximates a Schur complement operator. The new grid transfer algorithm is then based on computing a Schur complement but restricting the solution space of the corresponding grid transfers in a Galerkin‐style so that a far less expensive approximation is obtained. The final algorithm corresponds to a Richardson‐type iteration that is used to improve a simple initial prolongator or a simple initial restrictor. Numerical results are presented illustrating the performance of the resulting algebraic multigrid method on highly nonsymmetric systems. Copyright © 2013 John Wiley & Sons, Ltd.     

A linear,decoupled fractional time‐stepping method for the nonlinear fluid–fluid interaction

In this paper, a linear decoupled fractional time stepping method is proposed and developed for the nonlinear fluid–fluid interaction governed by the two Navier–Stokes equations. Partitioned time stepping method is applied to two‐physics problems with stiffness of the coupling terms being treated explicitly and is also unconditionally stable. As for each fluid, the velocity and pressure are respectively determined by just solving one vector‐valued quasi‐elliptic equation and the Possion equation with homogeneous Neumann boundary condition per time step. Therefore, the cost of the fluid–fluid interaction is dominant to solve four simple linear equations, which greatly reduces the computational cost of the whole system. The method exploits properties of the fluid–fluid system to establish its stability and convergence with the same results as the standard scheme. Finally, numerical experiments are presented to show the performance of the proposed method.     

An optimal sixth‐order quartic B‐spline collocation method for solving Bratu‐type and Lane‐Emden–type problems

This paper is concerned with the numerical solutions of Bratu‐type and Lane‐Emden–type boundary value problems, which describe various physical phenomena in applied science and technology. We present an optimal collocation method based on quartic B‐spine basis functions to solve such problems. This method is constructed by perturbing the original problem and on a uniform mesh. The method has been tested by four nonlinear examples. In order to show the advantage of the new method, numerical results are compared with those obtained by some of the existing methods, such as normal quartic B‐spline collocation method and the finite difference method (FDM). It has been observed that the order of convergence of the proposed method is six, which is two orders of magnitude larger than the normal quartic B‐spline collocation method. Moreover, our method gives highly accurate results than the FDM.     

A fast singly diagonally implicit runge–kutta method for solving 1D unsteady convection‐diffusion equations

In this article, a fast singly diagonally implicit Runge–Kutta method is designed to solve unsteady one‐dimensional convection diffusion equations. We use a three point compact finite difference approximation for the spatial discretization and also a three‐stage singly diagonally implicit Runge–Kutta (RK) method for the temporal discretization. In particular, a formulation evaluating the boundary values assigned to the internal stages for the RK method is derived so that a phenomenon of the order of the reduction for the convergence does not occur. The proposed scheme not only has fourth‐order accuracy in both space and time variables but also is computationally efficient, requiring only a linear matrix solver for a tridiagonal matrix system. It is also shown that the proposed scheme is unconditionally stable and suitable for stiff problems. Several numerical examples are solved by the new scheme and the numerical efficiency and superiority of it are compared with the numerical results obtained by other methods in the literature. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 788–812, 2014     

A block preconditioning technique for the streamfunction‐vorticity formulation of the Navier‐Stokes equations

Iterative methods of Krylov‐subspace type can be very effective solvers for matrix systems resulting from partial differential equations if appropriate preconditioning is employed. We describe and test block preconditioners based on a Schur complement approximation which uses a multigrid method for finite element approximations of the linearized incompressible Navier‐Stokes equations in streamfunction and vorticity formulation. By using a Picard iteration, we use this technology to solve fully nonlinear Navier‐Stokes problems. The solvers which result scale very well with problem parameters. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

Convergence of an implicit Voronoi finite volume method for reaction–diffusion problems

We investigate the convergence of an implicit Voronoi finite volume method for reaction–diffusion problems including nonlinear diffusion in two space dimensions. The model allows to handle heterogeneous materials and uses the chemical activities of the involved species as primary variables. The numerical scheme works with boundary conforming Delaunay meshes and preserves positivity and the dissipative property of the continuous system. Starting from a result on the global stability of the scheme (uniform, mesh‐independent global upper, and lower bounds), we prove strong convergence of the chemical activities and their gradients to a weak solution of the continuous problem. To illustrate the preservation of qualitative properties by the numerical scheme, we present a long‐term simulation of the Michaelis–Menten–Henri system. Especially, we investigate the decay properties of the relative free energy over several magnitudes of time, and obtain experimental orders of convergence for this quantity. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 141–174, 2016     

A direct Schur–Fourier decomposition for the efficient solution of high‐order Poisson equations on loosely coupled parallel computers

In this paper a parallel direct Schur–Fourier decomposition (DSFD) algorithm for the direct solution of arbitrary order discrete Poisson equations on parallel computers is proposed. It is based on a combination of a Direct Schur method and a Fourier decomposition and allows to solve each Poisson equation almost to machine accuracy using only one communication episode. Thus, it is well suited for loosely coupled parallel computers, that have a high network latency compared with the CPU performance. Several three‐dimensional direct numerical simulations (DNS) of wall‐bounded turbulent incompressible flows have been carried out using the DSFD algorithm. Numerical examples illustrating the robustness and scalability of the method on a PC cluster with a conventional 100 Mbits/s network are also presented. Copyright © 2005 John Wiley & Sons, Ltd.     

A monotone conservative Eulerian–Lagrangian scheme for reaction‐diffusion‐convection equations modeling chemotaxis

A numerical method for convection dominated diffusion problems, that exploits the use of characteristics, is derived and analyzed. It is shown to preserve positivity of solutions and be locally mass conserving. Stability, consistency and order one convergence are verified. Because of the way in which it determines characteristic pre‐images of grid cells, the method can be easily implemented for 1‐, 2‐, or 3‐dimensional problems on rectangular grids.© 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Unified multipliers‐free theory of dual‐primal domain decomposition methods

The concept of dual‐primal methods can be formulated in a manner that incorporates, as a subclass, the non preconditioned case. Using such a generalized concept, in this article without recourse to “Lagrange multipliers,” we introduce an all‐inclusive unified theory of nonoverlapping domain decomposition methods (DDMs). One‐level methods, such as Schur‐complement and one‐level FETI, as well as two‐level methods, such as Neumann‐Neumann and preconditioned FETI, are incorporated in a unified manner. Different choices of the dual subspaces yield the different dual‐primal preconditioners reported in the literature. In this unified theory, the procedures are carried out directly on the matrices, independently of the differential equations that originated them. This feature reduces considerably the code‐development effort required for their implementation and permit, for example, transforming 2D codes into 3D codes easily. Another source of this simplification is the introduction of two projection‐matrices, generalizations of the average and jump of a function, which possess superior computational properties. In particular, on the basis of numerical results reported there, we claim that our jump matrix is the optimal choice of the B operator of the FETI methods. A new formula for the Steklov‐Poincaré operator, at the discrete level, is also introduced. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

A note on an accelerated high‐accuracy multigrid solution of the convection‐diffusion equation with high Reynolds number

We present a new strategy to accelerate the convergence rate of a high‐accuracy multigrid method for the numerical solution of the convection‐diffusion equation at the high Reynolds number limit. We propose a scaled residual injection operator with a scaling factor proportional to the magnitude of the convection coefficients, an alternating line Gauss‐Seidel relaxation, and a minimal residual smoothing acceleration technique for the multigrid solution method. The new implementation strategy is tested to show an improved convergence rate with three problems, including one with a stagnation point in the computational domain. The effect of residual scaling and the algebraic properties of the coefficient matrix arising from the fourth‐order compact discretization are investigated numerically. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 1–10, 2000     

Semi‐implicit schemes for transient Navier–Stokes equations and eddy viscosity models

This study presents two computational schemes for the numerical approximation of solutions to eddy viscosity models as well as transient Navier–Stokes equations. The eddy viscosity model is one example of a class of Large Eddy Simulation models, which are used to simulate turbulent flow. The first approximation scheme is a first order single step method that treats the nonlinear term using a semi‐implicit discretization. The second scheme employs a two step approach that applies a Crank–Nicolson method for the nonlinear term while also retaining the semi‐implicit treatment used in the first scheme. A finite element approximation is used in the spatial discretization of the partial differential equations. The convergence analysis for both schemes is discussed in detail, and numerical results are given for two test problems one of which is the two dimensional flow around a cylinder. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009