Block preconditioners for energy stable schemes of magnetohydrodynamics equations

In this article, we develop the first and second order unconditionally energy stable schemes for magnetohydrodynamics (MHD) equations and design robust preconditioners for these schemes. Inspired by operator preconditioning ideas, appropriate parameter-dependent norms on function spaces are subtly defined to uniformly bound the bilinear and trilinear terms, which implies the uniform well-posedness of the schemes under the newly defined norms. Then robust block preconditioners are constructed using the Riesz operators. We prove that, if time step size $k\le C$, the proposed preconditioners are uniformly robust with respect to physical parameters and discrete parameters. Various numerical experiments, including energy stability tests, Kelvin–Helmholtz instability and magnetic driven cavity physical benchmark problems, are presented to manifest unconditional energy stability of the schemes and robustness of our preconditioners.     

Block triangular preconditioners for nonsymmetric saddle point problems: field-of-values analysis

A preconditioned minimal residual method for nonsymmetric saddle point problems is analyzed. The proposed preconditioner is of block triangular form. The aim of this article is to show that a rigorous convergence analysis can be performed by using the field of values of the preconditioned linear system. As an example, a saddle point problem obtained from a mixed finite element discretization of the Oseen equations is considered. The convergence estimates obtained by using a field–of–values analysis are independent of the discretization parameter h. Several computational experiments supplement the theoretical results and illustrate the performance of the method. Received March 20, 1997 / Revised version received January 14, 1998     

Block band Toeplitz preconditioners derived from generating function approximations: analysis and applications

We are concerned with the study and the design of optimal preconditioners for ill-conditioned Toeplitz systems that arise from a priori known real-valued nonnegative generating functions f(x,y) having roots of even multiplicities. Our preconditioned matrix is constructed by using a trigonometric polynomial θ(x,y) obtained from Fourier/kernel approximations or from the use of a proper interpolation scheme. Both of the above techniques produce a trigonometric polynomial θ(x,y) which approximates the generating function f(x,y), and hence the preconditioned matrix is forced to have clustered spectrum. As θ(x,y) is chosen to be a trigonometric polynomial, the preconditioner is a block band Toeplitz matrix with Toeplitz blocks, and therefore its inversion does not increase the total complexity of the PCG method. Preconditioning by block Toeplitz matrices has been treated in the literature in several papers. We compare our method with their results and we show the efficiency of our proposal through various numerical experiments.This research was co-funded by the European Union in the framework of the program “Pythagoras I” of the “Operational Program for Education and Initial Vocational Training” of the 3rd Community Support Framework of the Hellenic Ministry of Education, funded by national sources (25%) and by the European Social Fund - ESF (75%). The work of the second and of the third author was partially supported by MIUR (Italian Ministry of University and Research), grant number 2004015437.     

Block preconditioners for linear systems arising from multiscale collocation with compactly supported RBFs

Symmetric collocation methods with RBFs allow approximation of the solution of a partial differential equation, even if the right‐hand side is only known at scattered data points, without needing to generate a grid. However, the benefit of a guaranteed symmetric positive definite block system comes at a high computational cost. This cost can be alleviated somewhat by considering compactly supported RBFs and a multiscale technique. But the condition number and sparsity will still deteriorate with the number of data points. Therefore, we study certain block diagonal and triangular preconditioners. We investigate ideal preconditioners and determine the spectra of the preconditioned matrices before proposing more practical preconditioners based on a restricted additive Schwarz method with coarse grid correction. Numerical results verify the effectiveness of the preconditioners. Copyright © 2015 John Wiley & Sons, Ltd.     

Block and asynchronous two-stage methods for mildly nonlinear systems

Block parallel iterative methods for the solution of mildly nonlinear systems of equations of the form are studied. Two-stage methods, where the solution of each block is approximated by an inner iteration, are treated. Both synchronous and asynchronous versions are analyzed, and both pointwise and blockwise convergence theorems provided. The case where there are overlapping blocks is also considered. The analysis of the asynchronous method when applied to linear systems includes cases not treated before in the literature. Received June 5, 1997 / Revised version received December 29, 1997     

Block structured preconditioners in tensor form for the all-at-once solution of a finite volume fractional diffusion equation

We propose a tensor structured preconditioner for the tensor train GMRES algorithm (or TT-GMRES for short) to approximate the solution of the all-at-once formulation of time-dependent fractional partial differential equations discretized in time by linear multistep formulas used in boundary value form and in space by finite volumes.Numerical experiments show that the proposed preconditioner is efficient for very large problems and is competitive, in particular with respect to the AMEn algorithm.     

Block triangular preconditioners for linearization schemes of the Rayleigh–Bénard convection problem

In this paper, we compare two block triangular preconditioners for different linearizations of the Rayleigh–Bénard convection problem discretized with finite element methods. The two preconditioners differ in the nested or nonnested use of a certain approximation of the Schur complement associated to the Navier–Stokes block. First, bounds on the generalized eigenvalues are obtained for the preconditioned systems linearized with both Picard and Newton methods. Then, the performance of the proposed preconditioners is studied in terms of computational time. This investigation reveals some inconsistencies in the literature that are hereby discussed. We observe that the nonnested preconditioner works best both for the Picard and for the Newton cases. Therefore, we further investigate its performance by extending its application to a mixed Picard–Newton scheme. Numerical results of two‐ and three‐dimensional cases show that the convergence is robust with respect to the mesh size. We also give a characterization of the performance of the various preconditioned linearization schemes in terms of the Rayleigh number.     

Block factorized preconditioners for high‐order accurate in time approximation of the Navier‐Stokes equations

Computationally efficient solution methods for the unsteady Navier‐Stokes incompressible equations are mandatory in real applications of fluid dynamics. A typical strategy to reduce the computational cost is to split the original problem into subproblems involving the separate computation of velocity and pressure. The splitting can be carried out either at a differential level, like in the Chorin‐Temam scheme, or in an algebraic fashion, like in the algebraic reinterpretation of the Chorin‐Temam method, or in the Yosida scheme (see 1 and 19 ). These fractional step schemes indeed provide effective methods of solution when dealing with first order accurate time discretizations. Their extension to high order time discretization schemes is not trivial. To this end, in the present work we focus our attention on the adoption of inexact algebraic factorizations as preconditioners of the original problem. We investigate their properties and show that some particular choices of the approximate factorization lead to very effective schemes. In particular, we prove that performing a small number of preconditioned iterations is enough to obtain a time accurate solution, irrespective of the dimension of the system at hand. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 487–510, 2003     

BTTB preconditioners for BTTB systems

In this paper, we consider solving the BTTB system \({\cal T}_{m,n}[f] {\bf{x}} = {\bf{b}}\) by the preconditioned conjugate gradient (PCG) method, where \({\cal T}_{m,n}[f]\) denotes the m × m block Toeplitz matrix with n × n Toeplitz blocks (BTTB) generated by a (2π, 2π)-periodic continuous function f(x, y). We propose using the BTTB matrix \({\cal T}_{m,n}[1/f]\) to precondition the BTTB system and prove that only O(m)?+?O(n) eigenvalues of the preconditioned matrix \({\cal T}_{m,n}[1/f] {\cal T}_{m,n}[f]\) are not around 1 under the condition that f(x, y)?>?0. We then approximate 1/f(x, y) by a bivariate trigonometric polynomial, which can be obtained in O(m n log(m n)) operations by using the fast Fourier transform technique. Numerical results show that our BTTB preconditioner is more efficient than block circulant preconditioners.     

Circulant preconditioners for Toeplitz-block matrices

We propose two block preconditioners for Toeplitz-block matrices (i.e. each block is Toeplitz), intended to be used in conjunction with conjugate gradient methods. These preconditioners employ and extend existing circulant preconditioners for point Toeplitz matrices. The two preconditioners differ in whether the point circulant approximation is used once or twice, and also in the cost per step. We discuss efficient implementation of these two preconditioners, as well as some basic theoretical properties (such as preservation of symmetry and positive definiteness). We report results of numerical experiments, including an example from active noise control, to compare their performance.Research supported by SRI International and by the Army Research Office under contract DAAL03-91-G-0150 and by the Office of Naval Research under contract N00014-90-J-1695.     

Circulant preconditioners for pricing options

We use the normalized preconditioned conjugate gradient method with Strang’s circulant preconditioner to solve a nonsymmetric Toeplitz system A_nx=b, which arises from the discretization of a partial integro-differential equation in option pricing. By using the definition of family of generating functions introduced in [16], we prove that Strang’s circulant preconditioner leads to a superlinear convergence rate under certain conditions. Numerical results exemplify our theoretical analysis.     

Wavelet sparse approximate inverse preconditioners

We show how to use wavelet compression ideas to improve the performance of approximate inverse preconditioners. Our main idea is to first transform the inverse of the coefficient matrix into a wavelet basis, before applying standard approximate inverse techniques. In this process, smoothness in the entries ofA ⁻¹ are converted into small wavelet coefficients, thus allowing a more efficient approximate inverse approximation. We shall justify theoretically and numerically that our approach is effective for matrices with smooth inverses. Supported by grants from ONR: ONR-N00014-92-J-1890, and the Army Research Office: DAAL-03-91-C-0047 (Univ. of Tenn. subcontract ORA4466.04 Amendment 1 and 2). The first and the third author also acknowledge support from RIACS/NASA Ames NAS 2-96027 and the Alfred P. Sloan Foundation as Doctoral Dissertation Fellows, respectively. the work was supported by the Natural Sciences and Engineering Research Council of Canada, the Information Technology Research Centre (which is funded by the Province of Ontario), and RIACS/NASA Ames NAS 2-96027.     

Band-Toeplitz preconditioners for ill-conditioned Toeplitz systems

BIT Numerical Mathematics - Preconditioning for Toeplitz systems has been an active research area over the past few decades. Along this line of research, circulant preconditioners have been...     

Analysis of optimal preconditioners for CutFEM

In this article, we consider a class of unfitted finite element methods for scalar elliptic problems. These so-called CutFEM methods use standard finite element spaces on a fixed unfitted triangulation combined with the Nitsche technique and a ghost penalty stabilization. As a model problem we consider the application of such a method to the Poisson interface problem. We introduce and analyze a new class of preconditioners that is based on a subspace decomposition approach. The unfitted finite element space is split into two subspaces, where one subspace is the standard finite element space associated to the background mesh and the second subspace is spanned by all cut basis functions corresponding to nodes on the cut elements. We will show that this splitting is stable, uniformly in the discretization parameter and in the location of the interface in the triangulation. Based on this we introduce an efficient preconditioner that is uniformly spectrally equivalent to the stiffness matrix. Using a similar splitting, it is shown that the same preconditioning approach can also be applied to a fictitious domain CutFEM discretization of the Poisson equation. Results of numerical experiments are included that illustrate optimality of such preconditioners for the Poisson interface problem and the Poisson fictitious domain problem.     

Schur complement preconditioners for anisotropic problems

We present two new variants of Schur complement domain decompositionpreconditioners suitable for 2D anisotropic problems. Thesevariants are based on adaptations of the probing idea, describedby Chan et al (1992 Fifth Int. Symp. on Domain DecompositionMethods for Partial Differential Equations, Philadelphia: SIAM,pp 236-249), used in conjunction with a coarse grid approximationas introduced by Bramble et al (1986 Math. Comput. 47, 103-134).The new methods are specifically designed for situations wherethe coupling between neighbouring interfaces is stronger thanthe coupling within an interface. Taking into account this strongcoupling, one variant uses a multicolour probing technique toavoid distortion in the probe approximations that appear whenusing the method proposed by Chan et al. The second techniqueuses additional probe matrices to approximate not only the couplingwithin the interfaces but also the coupling between interfacepoints across the subdomains. This latter procedure looks somewhatlike an alternating line relaxation method for anisotropic problems,see Brandt (1977 Math. Comput.. 31, 333-390). To assess therelevance of the new preconditioners, we compare their numericalbehaviour with well known robust preconditioners such as thebalanced Neumann-Neumann method proposed by Mandel (1993 Commun.Numer. Methods Eng.. 9, 233-241).     

Diagonally-striped matrices and approximate inverse preconditioners

The inverse of a banded matrix is, in general, dense. If the structure of the original banded matrix is “striped”, that is, the non-zero diagonals are separated by one or more zero diagonals, the inverse may exhibit a similar striped structure. The motivation for studying inverses of striped matrices is to obtain efficient preconditioners for systems arising from radiation transport equations, whose matrices include dominant values along diagonal stripes. Linear systems whose system matrix has a striped inverse lend themselves to the use of a sparse approximate inverse (SPAI) preconditioner whose structure is derived from that of the actual inverse.     

Fast computation of two-level circulant preconditioners

In this paper we present an algorithm for the construction of the superoptimal circulant preconditioner for a two-level Toeplitz linear system. The algorithm is fast, in the sense that it operates in FFT time. Numerical results are given to assess its performance when applied to the solution of two-level Toeplitz systems by the conjugate gradient method, compared with the Strang and optimal circulant preconditioners.     

Approximate inverse-free preconditioners for Toeplitz matrices

In this paper, we propose approximate inverse-free preconditioners for solving Toeplitz systems. The preconditioners are constructed based on the famous Gohberg-Semencul formula. We show that if a Toeplitz matrix is generated by a positive bounded function and its entries enjoys the off-diagonal decay property, then the eigenvalues of the preconditioned matrix are clustered around one. Experimental results show that the proposed preconditioners are superior to other existing preconditioners in the literature.     

Wavelet-based preconditioners for boundary integral equations

We study simple preconditioners for the conjugate gradient method when used to solve matrix systems arising from some hypersingular and weakly singular integral equations. The preconditioners, which are of the type of hierarchical basis preconditioners, are based on the decomposition of the piecewise-linear (respectively piecewise-constant) functions as the sum of prewavelets (respectively derivatives of prewavelets). We prove that with these preconditioners the preconditioned systems have condition numbers uniformly bounded with respect to the degrees of freedom. Numerical experiments support our analysis. This revised version was published online in June 2006 with corrections to the Cover Date.     

A note on best conditioned preconditioners

We discuss the solution of Hermitian positive definite systemsAx=b by the preconditioned conjugate gradient method with a preconditionerM. In general, the smaller the condition number(M ^–1/2 AM ^–1/2 ) is, the faster the convergence rate will be. For a given unitary matrixQ, letM _Q = {Q* _N Q | _n is ann-by-n complex diagonal matrix} andM _Q ⁺ ={Q* _n Q | _n is ann-by-n positive definite diagonal matrix}. The preconditionerM _b that minimizes(M ^–1/2 AM ^–1/2 ) overM _Q ⁺ is called the best conditioned preconditioner for the matrixA overM _Q ⁺ . We prove that ifQAQ* has Young's Property A, thenM _b is nothing new but the minimizer of M –A _F overM _Q . Here · _F denotes the Frobenius norm. Some applications are also given here.