Tangential frequency filtering decompositions for unsymmetric matrices

Summary. In this paper, tangential frequency filtering decompositions (TFFD) for unsymmetric matrices are introduced. Different algorithms for the construction of unsymmetric tangential frequency filtering decompositions are presented. These algorithms yield for a specified class of matrices equivalent decompositions. The convergence rates of an iterative scheme, which uses a sequence of TFFDs as preconditioners, are independent of the number of unknowns for this class of matrices. Several numerical experiments verify the efficiency of these methods for the solution of linear systems of equations which arise from the discretisation of convection-diffusion differential equations. Received April 1, 1996 / Revised version received July 4, 1996     

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     

Multilevel ILU decomposition

Summary. In this paper, the multilevel ILU (MLILU) decomposition is introduced. During an incomplete Gaussian elimination process new matrix entries are generated such that a special ordering strategy yields distinct levels. On these levels, some smoothing steps are computed. The MLILU decomposition exists and the corresponding iterative scheme converges for all symmetric and positive definite matrices. Convergence rates independent of the number of unknowns are shown numerically for several examples. Many numerical experiments including unsymmetric and anisotropic problems, problems with jumping coefficients as well as realistic problems are presented. They indicate a very robust convergence behavior of the MLILU method. Received June 13, 1997 / Revised version received March 17, 1998     

Modified tangential frequency filtering decomposition and its fourier analysis

In this paper, a modified tangential frequency filtering decomposition (MTFFD) preconditioner is proposed. The optimal order of the modification and the optimal relaxation parameter is determined by Fourier analysis. With the choice of optimal order of modification, the Fourier results show that the condition number of the preconditioned matrix is O(h^-\frac23){{\mathcal O}(h^{-\frac{2}{3}})}, and the spectrum distribution of the preconditioned matrix can be predicted by the Fourier results. The performance of MTFFD preconditioner is compared with tangential frequency filtering (TFFD) preconditioner on a variety of large sparse matrices arising from the discretization of PDEs with discontinuous coefficients. The numerical results show that the MTFFD preconditioner is much more efficient than the TFFD preconditioner.     

Domain decomposition iterative procedures for solving scalar waves in the frequency domain

The propagation of dispersive waves can be modeled relevantly in the frequency domain. A wave problem in the frequency domain is difficult to solve numerically. In addition to having a complex–valued solution, the problem is neither Hermitian symmetric nor coercive in a wide range of applications in Geophysics or Quantum–Mechanics. In this paper, we consider a parallel domain decomposition iterative procedure for solving the problem by finite differences or conforming finite element methods. The analysis includes the decomposition of the domain into either the individual elements or larger subdomains ( of finite elements). To accelerate the speed of convergence, we introduce relaxation parameters on the subdomain interfaces and an artificial damping iteration. The convergence rate of the resulting algorithm turns out to be independent on the mesh size and the wave number. Numerical results carried out on an nCUBE2 parallel computer are presented to show the effectiveness of the method. Received October 30, 1995 / Revised version received January 10, 1997     

Block filtering decomposition

This paper introduces a new preconditioning technique that is suitable for matrices arising from the discretization of a system of PDEs on unstructured grids. The preconditioner satisfies a so‐called filtering property, which ensures that the input matrix is identical with the preconditioner on a given filtering vector. This vector is chosen to alleviate the effect of low‐frequency modes on convergence and so decrease or eliminate the plateau that is often observed in the convergence of iterative methods. In particular, the paper presents a general approach that allows to ensure that the filtering condition is satisfied in a matrix decomposition. The input matrix can have an arbitrary sparse structure. Hence, it can be reordered using nested dissection, to allow a parallel computation of the preconditioner and of the iterative process. We show the efficiency of our preconditioner through a set of numerical experiments on symmetric and nonsymmetric matrices. Copyright © 2014 John Wiley & Sons, Ltd.     

Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems,part II: Convergence theory

Summary In this paper we discuss bounds for the convergence rates of several domain decomposition algorithms to solve symmetric, indefinite linear systems arising from mixed finite element discretizations of elliptic problems. The algorithms include Schwarz methods and iterative refinement methods on locally refined grids. The implementation of Schwarz and iterative refinement algorithms have been discussed in part I. A discussion on the stability of mixed discretizations on locally refined grids is included and quantiative estimates for the convergence rates of some iterative refinement algorithms are also derived.Department of Mathematics, University of Wyoming, Laramie, WY 82071-3036. This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003, while the author was a graduate student at New York University, and in part by NSF Grant ASC 9003002, while the author was a Visiting, Assistant Researcher at UCLA.     

The convergence rate of the minimal residual method for the Stokes problem

Summary. Discretisation of the classical Stokes problem gives rise to symmetric indefinite matrices with eigenvalues which, in a precise way, are not symmetric about the origin, but which do depend on a mesh size parameter. Convergence estimates for the Conjugate Residual or Minimum Residual iterative solution of such systems are given by best minimax polynomial approximations on an inclusion set for the eigenvalues. In this paper, an analytic convergence estimate for such problems is given in terms of an asymptotically small mesh size parameter. Received November 16, 1993 / Revised version received August 2, 1994     

Nonstandard coarse spaces and Schwarz methods for elliptic problems with discontinuous coefficients using non-conforming elements

Summary. Two-level domain decomposition methods are developed for a simple nonconforming approximation of second order elliptic problems. A bound is established for the condition number of these iterative methods, that grows only logarithmically with the number of degrees of freedom in each subregion. This bound holds for two and three dimensions and is independent of jumps in the value of the coefficients and number of subregions. We introduce face coarse spaces, and isomorphisms to map between conforming and nonconforming spaces. ReceivedMarch 1, 1995 / Revised version received January 16, 1996     

Preconditioned conjugate gradient methods for large-scale fluid flow applications

The simulation of large-scale fluid flow applications often requires the efficient solution of extremely large nonsymmetric linear and nonlinear sparse systems of equations arising from the discretization of systems of partial differential equations. While preconditioned conjugate gradient methods work well for symmetric, positive-definite matrices, other methods are necessary to treat large, nonsymmetric matrices. The applications may also involve highly localized phenomena which can be addressed via local and adaptive grid refinement techniques. These local refinement methods usually cause non-standard grid connections which destroy the bandedness of the matrices and the associated ease of solution and vectorization of the algorithms. The use of preconditioned conjugate gradient or conjugate-gradient-like iterative methods in large-scale reservoir simulation applications is briefly surveyed. Then, some block preconditioning methods for adaptive grid refinement via domain decomposition techniques are presented and compared. These techniques are being used efficiently in existing large-scale simulation codes.     

Using approximate inverses in algebraic multilevel methods

Summary. This paper deals with the iterative solution of large sparse symmetric positive definite systems. We investigate preconditioning techniques of the two-level type that are based on a block factorization of the system matrix. Whereas the basic scheme assumes an exact inversion of the submatrix related to the first block of unknowns, we analyze the effect of using an approximate inverse instead. We derive condition number estimates that are valid for any type of approximation of the Schur complement and that do not assume the use of the hierarchical basis. They show that the two-level methods are stable when using approximate inverses based on modified ILU techniques, or explicit inverses that meet some row-sum criterion. On the other hand, we bring to the light that the use of standard approximate inverses based on convergent splittings can have a dramatic effect on the convergence rate. These conclusions are numerically illustrated on some examples Received March 3, 1997 / Revised version received July 16, 1997     

An incomplete-factorization preconditioning using repeated red-black ordering

Summary The convergence of the conjugate gradient method for the iterative solution of large systems of linear equations depends on proper preconditioning matrices. We present an efficient incomplete-factorization preconditioning based on a specific, repeated red-black ordering scheme and cyclic reduction. For the Dirichlet model problem, we prove that the condition number increases asymptotically slower with the number of equations than for usual incomplete factorization methods. Numerical results for symmetric and non-symmetric test problems and on locally refined grids demonstrate the performance of this method, especially for large linear systems.     

A note on conjugate gradient convergence

Summary. The one-dimensional discrete Poisson equation on a uniform grid with points produces a linear system of equations with a symmetric, positive-definite coefficient matrix. Hence, the conjugate gradient method can be used, and standard analysis gives an upper bound of ) on the number of iterations required for convergence. This paper introduces a systematically defined set of solutions dependent on a parameter , and for several values of , presents exact analytic expressions for the number of steps ) needed to achieve accuracy . The asymptotic behavior of these expressions has the form )} as and )} as . In particular, two choices of corresponding to nonsmooth solutions give , i.e., iteration counts independent of ; this is in contrast to the standard bounds. The standard asymptotic convergence behavior, , is seen for a relatively smooth solution. Numerical examples illustrate and supplement the analysis. Received August 30, 1995 / Revised version received January 23, 1996     

Complex conjugate gradient methods

Linear systems with complex coefficients arise from various physical problems. Examples are the Helmholtz equation and Maxwell equations approximated by finite difference or finite element methods, that lead to large sparse linear systems. When the continuous problem is reduced to integral equations, after discretization, one obtains a dense linear system. The resulting matrices are generally non-Hermitian but, most of the time, symmetric and consequently the classical conjugate gradient method cannot be directly applied. Usually, these linear systems have to be solved with a large number of unknowns because, for instance, in electromagnetic scattering problems the mesh size must be related to the wave length of the incoming wave. The higher the frequency of the incoming wave, the smaller the mesh size must be. When one wants to solve 3D-problems, it is no longer practical to use direct method solvers, because of the huge memory they need. So iterative methods are attractive for this kind of problems, even though their convergence cannot be always guaranteed with theoretical results. In this paper we derive several methods from a unified framework and we numerically compare these algorithms on some test problems.     

An accelerated domain decomposition procedure based on robin transmission conditions

A domain decomposition procedure based on Robin transmission conditions applicable to elliptic boundary problems was first introduced by P. L. Lions and later discussed by a number of authors. In all of these discussions, the weighting of the flux and the trace of the solution were independent of the iterative step number. For some model problems we introduce a cycle of weights and prove that an acceleration of the convergence rate similar to that occurring for alternating-direction iteration using a cycle of pseudo-time steps results. In some discrete cases, the cycle length can be taken to be independent of the mesh spacing.     

Nonlinear Galerkin method in the finite difference case and wavelet-like incremental unknowns

Summary The IMG algorithm (Inertial Manifold-Multigrid algorithm) which uses the first-order incremental unknowns was introduced in [20]. The IMG algorithm is aimed at numerically implementing inertial manifolds (see e.g. [19]) when finite difference discretizations are used. For that purpose it is necessary to decompose the unknown function into its long wavelength and its short wavelength components; (first-order) Incremental Unknowns (IU) were proposed in [20] as a means to realize this decomposition. Our aim in the present article is to propose and study other forms of incremental unknowns, in particular the Wavelet-like Incremental Unknowns (WIU), so-called because of their oscillatory nature.In this report, we first extend the general convergence results in [20] by proving them under slightly weaker conditions. We then present three sets of incremental unknowns (i.e. the first-order as in [20], the second-order and wavelet-like incremental unknowns). We show that these incremental unknown can be used to construct convergent IMG algorithms. Special stress is put on the wavelet-like incremental unknowns since this set of unknowns has theL ² orthogonality property between different levels of unknowns and this should make them particularly appropriate for the approximation of evolution equations by inertial algorithms.     

Convergence of block iterative methods for linear systems arising in the numerical solution of Euler equations

Summary We discuss block matrices of the formA=[A _ij ], whereA _ij is ak×k symmetric matrix,A _ij is positive definite andA _ij is negative semidefinite. These matrices are natural block-generalizations of Z-matrices and M-matrices. Matrices of this type arise in the numerical solution of Euler equations in fluid flow computations. We discuss properties of these matrices, in particular we prove convergence of block iterative methods for linear systems with such system matrices.     

Convergence theorems for block splitting iterative methods for linear systems

In this paper, we will present the block splitting iterative methods with general weighting matrices for solving linear systems of algebraic equations Ax=b$\mathit{Ax}=b$ when the coefficient matrix A is symmetric positive definite of block form, and establish the convergence theories with respect to the general weighting matrices but special splittings. Finally, a numerical example shows the advantage of this method.     

Conditioning analysis of block incomplete factorizations and its application to elliptic equations

Summary. The paper deals with eigenvalue estimates for block incomplete factorization methods for symmetric matrices. First, some previous results on upper bounds for the maximum eigenvalue of preconditioned matrices are generalized to each eigenvalue. Second, upper bounds for the maximum eigenvalue of the preconditioned matrix are further estimated, which presents a substantial improvement of earlier results. Finally, the results are used to estimate bounds for every eigenvalue of the preconditioned matrices, in particular, for the maximum eigenvalue, when a modified block incomplete factorization is used to solve an elliptic equation with variable coefficients in two dimensions. The analysis yields a new upper bound of type for the condition number of the preconditioned matrix and shows clearly how the coefficients of the differential equation influence the positive constant . Received March 27, 1996 / Revised version received December 27, 1996     

The Convergence of Multigrid Methods for Solving Finite Element Equations in the Presence of Singularities

1.IntroductionMultigridMethodsprovideoptimalordersolversforlinearsysternsoffiniteele-mentequationsarisingfromellipticboundaryvalueproblems.Theconvergenceofmultigridmethodswasprovedbymanya.tho.s[2-6,9-12l.AlltheseproofS,requirestrongregularitiesandquasi-uniformityofgridsl',,']-Forexample,assumingH1+oregularityandquasi-uniformtriangulations,Bank&Dupollt[3]showedaconvergencerateofo(mY),foragrowingnumbermofsmoothingstepsperlevel.Intheoptimalcasecr=1,theproblemhastobeH'-regUlar.Whentheregionhas…