Fourier analysis of frequency filtering decomposition preconditioners

In this paper, frequency filtering decomposition (FFD) preconditioner is analyzed by the approach of Fourier analysis. The condition number estimation of a preconditioned 2-D model problem is presented. Analysis reveals that condition number of the preconditioned matrix grows like O(h^-1), with h be the mesh size. By using the framework of FFD, a stabilized frequency filtering decomposition (SFFD) method is proposed and analyzed by Fourier method. Results show that SFFD preconditioner is superior to FFD preconditioner in the sense that . Numerical tests are performed to illustrate the theoretical results and the superiority of SFFD preconditioner.     

Adaptive filtering

Summary. In this paper, the adaptive filtering method is introduced and analysed. This method leads to robust algorithms for the solution of systems of linear equations which arise from the discretisation of partial differential equations with strongly varying coefficients. These iterative algorithms are based on the tangential frequency filtering decompositions (TFFD). During the iteration with a preliminary preconditioner, the adaptive test vector method calculates new test vectors for the TFFD. The adaptive test vector iterative method allows the combination of the tangential frequency decomposition and other iterative methods such as multi-grid. The connection with the TFFD improves the robustness of these iterative methods with respect to varying coefficients. Interface problems as well as problems with stochastically distributed properties are considered. Realistic numerical experiments confirm the efficiency of the presented algorithms. Received June 26, 1996 / Revised version received October 7, 1996     

Fast Fourier Transform Solvers and Preconditioners for Quadratic Spline Collocation

Quadratic Spline Collocation (QSC) methods of optimal order of convergence have been recently developed for the solution of elliptic Partial Differential Equations (PDEs). In this paper, linear solvers based on Fast Fourier Transforms (FFT)are developed for the solution of the QSC equations. The complexity of the FFT solvers is O(N ² log N), where N is the gridsize in one dimension. These direct solvers can handle PDEs with coefficients in one variable or constant, and Dirichlet, Neumann, alternating Dirichlet-Neumann or periodic boundary conditions, along at least one direction of a rectangular domain. General variable coefficient PDEs are handled by preconditioned iterative solvers. The preconditioner is the QSC matrix arising from a constant coefficient PDE. The convergence analysis of the preconditioner is presented. It is shown that, under certain conditions, the convergence rate is independent of the gridsize. The preconditioner is solved by FFT techniques, and integrated with one-step or acceleration methods, giving rise to asymptotically almost optimal linear solvers, with complexity O(N ² log N). Numerical experiments verify the effectiveness of the solvers and preconditioners, even on problems more general than the analysis assumes. The development and analysis of FFT solvers and preconditioners is extended to QSC equations corresponding to systems of elliptic PDEs.     

Sine transform based preconditioners for elliptic problems

We consider applying the preconditioned conjugate gradient (PCG) method to solving linear systems Ax = b where the matrix A comes from the discretization of second-order elliptic operators with Dirichlet boundary conditions. Let (L + Σ)Σ⁻¹(L^t + Σ) denote the block Cholesky factorization of A with lower block triangular matrix L and diagonal block matrix Σ. We propose a preconditioner M = (Lˆ + Σˆ)Σˆ⁻¹(Lˆ^t + Σˆ) with block diagonal matrix Σˆ and lower block triangular matrix Lˆ. The diagonal blocks of Σˆ and the subdiagonal blocks of Lˆ are respectively the optimal sine transform approximations to the diagonal blocks of Σ and the subdiagonal blocks of L. We show that for two-dimensional domains, the construction cost of M and the cost for each iteration of the PCG algorithm are of order O(n² log n). Furthermore, for rectangular regions, we show that the condition number of the preconditioned system M⁻¹A is of order O(1). In contrast, the system preconditioned by the MILU and MINV methods are of order O(n). We will also show that M can be obtained from A by taking the optimal sine transform approximations of each sub-block of A. Thus, the construction of M is similar to that of Level-1 circulant preconditioners. Our numerical results on two-dimensional square and L-shaped domains show that our method converges faster than the MILU and MINV methods. Extension to higher-dimensional domains will also be discussed. © 1997 John Wiley & Sons, Ltd.     

Tangential frequency filtering decompositions for symmetric matrices

Summary. The tangential frequency filtering decomposition (TFFD) is introduced. The convergence theory of an iterative scheme based on the TFFD for symmetric matrices is the focus of this paper. The existence of the TFFD and the convergence of the induced iterative algorithm is shown for symmetric and positive definite matrices. Convergence rates independent of the number of unknowns are proven for a smaller class of matrices. Using this framework, the convergence independent of the number of unknowns is shown for Wittum's frequency filtering decomposition. Some characteristic properties of the TFFD are illustrated and results of several numerical experiments are presented. Received April 1, 1996 / Revised version July 4, 1996     

Special issue: recent progress on iterative methods for large systems of equations

Let A x = b be a large and sparse system of linear equations where A is a nonsingular matrix. An approximate solution is frequently obtained by applying preconditioned iterations. Consider the matrix B = A + P Q ^T where \(P, Q \in \mathbb {R}^{n \times k}\) are full rank matrices. In this work, we study the problem of updating a previously computed preconditioner for A in order to solve the updated linear system B x = b by preconditioned iterations. In particular, we propose a method for updating a Balanced Incomplete Factorization preconditioner. The strategy is based on the computation of an approximate Inverse Sherman-Morrison decomposition for an equivalent augmented linear system. Approximation properties of the preconditioned matrix and an analysis of the computational cost of the algorithm are studied. Moreover, the results of the numerical experiments with different types of problems show that the proposed method contributes to accelerate the convergence.     

Greville��s method for preconditioning least squares problems

In this paper, we propose a preconditioning algorithm for least squares problems $\displaystyle{\min_{x\in{{\mathbb{R}}}^n}}\|b-Ax\|_2$ , where A can be matrices with any shape or rank. The preconditioner is constructed to be a sparse approximation to the Moore?CPenrose inverse of the coefficient matrix A. For this preconditioner, we provide theoretical analysis to show that under our assumption, the least squares problem preconditioned by this preconditioner is equivalent to the original problem, and the GMRES method can determine a solution to the preconditioned problem before breakdown happens. In the end of this paper, we also give some numerical examples showing the performance of the method.     

Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations

The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients.     

Fast Construction of Optimal Circulant Preconditioners for Matrices from the Fast Dense Matrix Method

In this paper, we consider solving non-convolution type integral equations by the preconditioned conjugate gradient method. The fast dense matrix method is a fast multiplication scheme that provides a dense discretization matrix A approximating a given integral equation. The dense matrix A can be constructed in O(n) operations and requires only O(n) storage where n is the size of the matrix. Moreover, the matrix-vector multiplication A xcan be done in O(n log n) operations. Thus if the conjugate gradient method is used to solve the discretized system, the cost per iteration is O(n log n) operations. However, for some integral equations, such as the Fredholm integral equations of the first kind, the system will be ill-conditioned and therefore the convergence rate of the method will be slow. In these cases, preconditioning is required to speed up the convergence rate of the method. A good choice of preconditioner is the optimal circulant preconditioner which is the minimizer of C – A _F in Frobenius norm over all circulant matrices C. It can be obtained by taking arithmetic averages of all the entries of A and therefore the cost of constructing the preconditioner is of O(n ²) operations for general dense matrices. In this paper, we develop an O(n log n) method of constructing the preconditioner for dense matrices A obtained from the fast dense matrix method. Application of these ideas to boundary integral equations from potential theory will be given. These equations are ill-conditioned whereas their optimal circulant preconditioned equations will be well-conditioned. The accuracy of the approximation A, the fast construction of the preconditioner and the fast convergence of the preconditioned systems will be illustrated by numerical examples.     

Stable enrichment and local preconditioning in the particle-partition of unity method

This paper is concerned with the stability and approximation properties of enriched meshfree and generalized finite element methods. In particular we focus on the particle-partition of unity method (PPUM) yet the presented results hold for any partition of unity based enrichment scheme. The goal of our enrichment scheme is to recover the optimal convergence rate of the uniform h-version independent of the regularity of the solution. Hence, we employ enrichment not only for modeling purposes but rather to improve the approximation properties of the numerical scheme. To this end we enrich our PPUM function space in an enrichment zone hierarchically near the singularities of the solution. This initial enrichment however can lead to a severe ill-conditioning and can compromise the stability of the discretization. To overcome the ill-conditioning of the enriched shape functions we present an appropriate local preconditioner which yields a stable and well-conditioned basis independent of the employed initial enrichment. The construction of this preconditioner is of linear complexity with respect to the number of discretization points. We obtain optimal error bounds for an enriched PPUM discretization with local preconditioning that are independent of the regularity of the solution globally and within the employed enrichment zone we observe a kind of super-convergence. The results of our numerical experiments clearly show that our enriched PPUM with local preconditioning recovers the optimal convergence rate of O(h ^p ) of the uniform h-version globally. For the considered model problems from linear elastic fracture mechanics we obtain an improved convergence rate of O(h ^p+δ ) with d 3 \frac12{\delta\geq\frac{1}{2}} for p = 1. The convergence rate of our multilevel solver is essentially the same for a purely polynomial approximation and an enriched approximation.     

Preconditioning of elliptic problems by approximation in the transform domain

Preconditioned conjugate gradient method is applied for solving linear systemsAx=b where the matrixA is the discretization matrix of second-order elliptic operators. In this paper, we consider the construction of the trnasform based preconditioner from the viewpoint of image compression. Given a smooth image, a major portion of the energy is concentrated in the low frequency regions after image transformation. We can view the matrixA as an image and construct the transform based preconditioner by using the low frequency components of the transformed matrix. It is our hope that the smooth coefficients of the given elliptic operator can be approximated well by the low-rank matrix. Numerical results are reported to show the effectiveness of the preconditioning strategy. Some theoretical results about the properties of our proposed preconditioners and the condition number of the preconditioned matrices are discussed.     

Low regularity solution for a nonlocal perturbation of KdV equation

The Cauchy problem for a nonlocal perturbation of KdV equation is considered by the Fourier restriction norm method. Local well-posedness for initial data in $H^s({\mathbb{R}})(s > -\frac{3}{4})$H^s({\mathbb{R}})(s > -\frac{3}{4}) and global results for data in L²(\mathbbR)L^2({\mathbb{R}}) are obtained.     

Low frequency tangential filtering decomposition

For block‐tridiagonal systems of linear equations arising from the discretization of partial differential equations, a composite preconditioner is proposed and tested. It combines a classical ILU0 factorization for high frequencies with a tangential filtering preconditioner. The choice of the filtering vector is important: the test‐vector is the Ritz eigenvector corresponding to the approximate lowest eigenvalue, obtained after a limited number of iterations of a ILU0 preconditioned Krylov method. Numerical tests are carried out for this method. Copyright © 2006 John Wiley & Sons, Ltd.     

Analysis of a novel preconditioner for a class of p‐level lower rank extracted systems

This paper proposes and studies the performance of a preconditioner suitable for solving a class of symmetric positive definite systems, Âx=b, which we call p‐level lower rank extracted systems (p‐level LRES), by the preconditioned conjugate gradient method. The study of these systems is motivated by the numerical approximation of integral equations with convolution kernels defined on arbitrary p‐dimensional domains. This is in contrast to p‐level Toeplitz systems which only apply to rectangular domains. The coefficient matrix, Â, is a principal submatrix of a p‐level Toeplitz matrix, A, and the preconditioner for the preconditioned conjugate gradient algorithm is provided in terms of the inverse of a p‐level circulant matrix constructed from the elements of A. The preconditioner is shown to yield clustering in the spectrum of the preconditioned matrix which leads to a substantial reduction in the computational cost of solving LRE systems. Copyright © 2006 John Wiley & Sons, Ltd.     

BCCB preconditioners for systems of BVM‐based numerical integrators

Boundary value methods (BVMs) for ordinary differential equations require the solution of non‐symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A block‐circulant preconditioner with circulant blocks (BCCB preconditioner) is proposed to speed up the convergence rate of the GMRES method. The BCCB preconditioner is shown to be invertible when the BVM is A_k1,k2‐stable. The spectrum of the preconditioned matrix is clustered and therefore, the preconditioned GMRES method converges fast. Moreover, the operation cost in each iteration of the preconditioned GMRES method by using our BCCB preconditioner is less than that required by using block‐circulant preconditioners proposed earlier. In numerical experiments, we compare the number of iterations of various preconditioners. Copyright © 2003 John Wiley & Sons, Ltd.     

A comparison of abstract versions of deflation,balancing and additive coarse grid correction preconditioners

In this paper we consider various preconditioners for the conjugate gradient (CG) method to solve large linear systems of equations with symmetric positive definite system matrix. We continue the comparison between abstract versions of the deflation, balancing and additive coarse grid correction preconditioning techniques started in (SIAM J. Numer. Anal. 2004; 42 :1631–1647; SIAM J. Sci. Comput. 2006; 27 :1742–1759). There the deflation method is compared with the abstract additive coarse grid correction preconditioner and the abstract balancing preconditioner. Here, we close the triangle between these three methods. First of all, we show that a theoretical comparison of the condition numbers of the abstract additive coarse grid correction and the condition number of the system preconditioned by the abstract balancing preconditioner is not possible. We present a counter example, for which the condition number of the abstract additive coarse grid correction preconditioned system is below the condition number of the system preconditioned with the abstract balancing preconditioner. However, if the CG method is preconditioned by the abstract balancing preconditioner and is started with a special starting vector, the asymptotic convergence behavior of the CG method can be described by the so‐called effective condition number with respect to the starting vector. We prove that this effective condition number of the system preconditioned by the abstract balancing preconditioner is less than or equal to the condition number of the system preconditioned by the abstract additive coarse grid correction method. We also provide a short proof of the relationship between the effective condition number and the convergence of CG. Moreover, we compare the A‐norm of the errors of the iterates given by the different preconditioners and establish the orthogonal invariants of all three types of preconditioners. Copyright © 2008 John Wiley & Sons, Ltd.     

A parallel block overlap preconditioning with inexact submatrix inversion for linear elasticity problems

We present a parallel preconditioned iterative solver for large sparse symmetric positive definite linear systems. The preconditioner is constructed as a proper combination of advanced preconditioning strategies. It can be formally seen as being of domain decomposition type with algebraically constructed overlap. Similar to the classical domain decomposition technique, inexact subdomain solvers are used, based on incomplete Cholesky factorization. The proper preconditioner is shown to be near optimal in minimizing the so‐called K‐condition number of the preconditioned matrix. The efficiency of both serial and parallel versions of the solution method is illustrated on a set of benchmark problems in linear elasticity. Copyright © 2002 John Wiley & Sons, Ltd.     

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.     

Additive Schwarz Method for Mortar Discretization of Elliptic Problems with <Emphasis Type="Italic">P</Emphasis><Subscript>1</Subscript> Nonconforming Finite Elements

An additive Schwarz preconditioner for nonconforming mortar finite element discretization of a second order elliptic problem in two dimensions with arbitrary large jumps of the discontinuous coefficients in subdomains is described. An almost optimal estimate of the condition number of the preconditioned problem is proved. The number of preconditioned conjugate gradient iterations is independent of jumps of the coefficients and is proportional to (1+log(H/h)), where H,h are mesh sizes. AMS subject classification (2000) 65N55, 65N30, 65N22     

Inverse product Toeplitz preconditioners for non-Hermitian Toeplitz systems

In this paper, we first propose product Toeplitz preconditioners (in an inverse form) for non-Hermitian Toeplitz matrices generated by functions with zeros. Our inverse product-type preconditioner is of the form T_F T_L^-1 T_U^-1T_F T_L^{-1} T_U^{-1} where T _F , T _L , and T _U are full, band lower triangular, and band upper triangular Toeplitz matrices, respectively. Our basic idea is to decompose the generating function properly such that all factors T _F , T _L , and T _U of the preconditioner are as well-conditioned as possible. We prove that under certain conditions, the preconditioned matrix has eigenvalues and singular values clustered around 1. Then we use a similar idea to modify the preconditioner proposed in Ku and Kuo (SIAM J Sci Stat Comput 13:1470–1487, 1992) to handle the zeros in rational generating functions. Numerical results, including applications to the computation of the stationary probability distribution of Markovian queuing models with batch arrival, are given to illustrate the good performance of the proposed preconditioners.