A sharp convergence estimate for the method of subspace corrections for singular systems of equations

This paper is devoted to the convergence rate estimate for the method of successive subspace corrections applied to symmetric and positive semidefinite (singular) problems. In a general Hilbert space setting, a convergence rate identity is obtained for the method of subspace corrections in terms of the subspace solvers. As an illustration, the new abstract theory is used to show uniform convergence of a multigrid method applied to the solution of the Laplace equation with pure Neumann boundary conditions.

     

The method of alternating projections and the method of subspace corrections in Hilbert space

A new identity is given in this paper for estimating the norm of the product of nonexpansive operators in Hilbert space. This identity can be applied for the design and analysis of the method of alternating projections and the method of subspace corrections. The method of alternating projections is an iterative algorithm for determining the best approximation to any given point in a Hilbert space from the intersection of a finite number of subspaces by alternatively computing the best approximations from the individual subspaces which make up the intersection. The method of subspace corrections is an iterative algorithm for finding the solution of a linear equation in a Hilbert space by approximately solving equations restricted on a number of closed subspaces which make up the entire space. The new identity given in the paper provides a sharpest possible estimate for the rate of convergence of these algorithms. It is also proved in the paper that the method of alternating projections is essentially equivalent to the method of subspace corrections. Some simple examples of multigrid and domain decomposition methods are given to illustrate the application of the new identity.

     

CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm

The Generalized Minimal Residual (GMRES) method and the Quasi-Minimal Residual (QMR) method are two Krylov methods for solving linear systems. The main difference between these methods is the generation of the basis vectors for the Krylov subspace. The GMRES method uses the Arnoldi process while QMR uses the Lanczos algorithm for constructing a basis of the Krylov subspace. In this paper we give a new method similar to QMR but based on the Hessenberg process instead of the Lanczos process. We call the new method the CMRH method. The CMRH method is less expensive and requires slightly less storage than GMRES. Numerical experiments suggest that it has behaviour similar to GMRES. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multigrid preconditioned Krylov subspace methods for three-dimensional numerical solutions of the incompressible Navier–Stokes equations

We consider numerical methods for the incompressible Reynolds averaged Navier–Stokes equations discretized by finite difference techniques on non-staggered grids in body-fitted coordinates. A segregated approach is used to solve the pressure–velocity coupling problem. Several iterative pressure linear solvers including Krylov subspace and multigrid methods and their combination have been developed to compare the efficiency of each method and to design a robust solver. Three-dimensional numerical experiments carried out on scalar and vector machines and performed on different fluid flow problems show that a combination of multigrid and Krylov subspace methods is a robust and efficient pressure solver. This revised version was published online in June 2006 with corrections to the Cover Date.     

Augmented conjugate gradient. Application in an iterative process for the solution of scattering problems

We discuss the application of an augmented conjugate gradient to the solution of a sequence of linear systems of the same matrix appearing in an iterative process for the solution of scattering problems. The conjugate gradient method applied to the first system generates a Krylov subspace, then for the following systems, a modified conjugate gradient is applied using orthogonal projections on this subspace to compute an initial guess and modified descent directions leading to a better convergence. The scattering problem is treated via an Exact Controllability formulation and a preconditioned conjugate gradient algorithm is introduced. The set of linear systems to be solved are associated to this preconditioning. The efficiency of the method is tested on different 3D acoustic problems. This revised version was published online in August 2006 with corrections to the Cover Date.     

Convergence of the newton process to multiple solutions

In 1870, E.Schröder showed that the convergence of the Newton process of successive approximations to a multiple solution of a scalar equation was geometric in character, and that quadratic convergence could be restored by multiplying the ordinary corrections by a constant. Here, this result is extended to finite systems, and it is shown that there exist various subspaces of the given space in which the convergence is geometric with a rate characteristic of the given subspace. Quadratic convergence may be restored by applying a given fixed linear operator to the ordinary corrections. The conditions under which these results apply to equations in infinite-dimensional Banach spaces are given. Numerical examples involving scalar equations and a simple 2 × 2 system are presented.Sponsored by the Mathematics Research Center, United States Army, Madison, Wisconsin, under Contract No. DA-11-022-ORD-2059.     

Concerning closed invariant subspaces for endomorphisms of the space (s)

We show that every (continuous) endomorphism of the complex space (s) has a proper closed invariant subspace which is either of dimension one or of codimension one. We give also a related result for the real space (s). This revised version was published online in June 2006 with corrections to the Cover Date.     

Spectral division methods for block generalized Schur decompositions

We provide a different perspective of the spectral division methods for block generalized Schur decompositions of matrix pairs. The new approach exposes more algebraic structures of the successive matrix pairs in the spectral division iterations and reveals some potential computational difficulties. We present modified algorithms to reduce the arithmetic cost by nearly 50%, remove inconsistency in spectral subspace extraction from different sides (left and right), and improve the accuracy of subspaces. In application problems that only require a single-sided deflating subspace, our algorithms can be used to obtain a posteriori estimates on the backward accuracy of the computed subspaces with little extra cost.

     

Factorised Preconditionings of Successive Approximations in Finite Precision

This paper examines the possibility of using the method of successive approximations for the approximate solution of a large system of linear equations with a dense, noncontraction, and ill-conditioned matrix. Using Krasnosel'skii's method of transformation of linear operator equations and functional calculi, the procedure of factorised preconditionings of successive approximations is developed and analysed in the finite precision arithmetic. Numerical results of computational experiments are presented to demonstrate the practicability of the proposed approach.This revised version was published online in October 2005 with corrections to the Cover Date.     

A nonstandard multigrid method with flexible multiple semicoarsening for the numerical solution of the pressure equation in a Navier-Stokes solver

Numerical methods for the incompressible Reynolds-averaged Navier-Stokes equations discretized by finite difference techniques on collocated cell-centered structured grids are considered in this paper. A widespread solution method to solve the pressure-velocity coupling problem is to use a segregated approach, in which the computational work is deeply controlled by the solution of the pressure problem. This pressure equation is an elliptic partial differential equation with possibly discontinuous or anisotropic coeffficients. The resulting singular linear system needs efficient solution strategies especially for 3-dimensional applications. A robust method (close to MG-S [22,34]) combining multiple cell-centered semicoarsening strategies, matrix-independent transfer operators, Galerkin coarse grid approximation is therefore designed. This strategy is both evaluated as a solver or as a preconditioner for Krylov subspace methods on various 2- or 3-dimensional fluid flow problems. The robustness of this method is shown. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the convergence of Ritz pairs and refined Ritz vectors for quadratic eigenvalue problems

For a given subspace, the Rayleigh-Ritz method projects the large quadratic eigenvalue problem (QEP) onto it and produces a small sized dense QEP. Similar to the Rayleigh-Ritz method for the linear eigenvalue problem, the Rayleigh-Ritz method defines the Ritz values and the Ritz vectors of the QEP with respect to the projection subspace. We analyze the convergence of the method when the angle between the subspace and the desired eigenvector converges to zero. We prove that there is a Ritz value that converges to the desired eigenvalue unconditionally but the Ritz vector converges conditionally and may fail to converge. To remedy the drawback of possible non-convergence of the Ritz vector, we propose a refined Ritz vector that is mathematically different from the Ritz vector and is proved to converge unconditionally. We construct examples to illustrate our theory.     

Greedy and randomized versions of the multiplicative Schwarz method

We consider sequential, i.e., Gauss–Seidel type, subspace correction methods for the iterative solution of symmetric positive definite variational problems, where the order of subspace correction steps is not deterministically fixed as in standard multiplicative Schwarz methods. Here, we greedily choose the subspace with the largest (or at least a relatively large) residual norm for the next update step, which is also known as the Gauss–Southwell method. We prove exponential convergence in the energy norm, with a reduction factor per iteration step directly related to the spectral properties, e.g., the condition number, of the underlying space splitting. To avoid the additional computational cost associated with the greedy pick, we alternatively consider choosing the next subspace randomly, and show similar estimates for the expected error reduction. We give some numerical examples, in particular applications to a Toeplitz system and to multilevel discretizations of an elliptic boundary value problem, which illustrate the theoretical estimates.     

Extending Independent Sets to Bases and the Axiom of Choice

We show that the both assertions “in every vector space B over a finite element field every subspace V ? B has a complementary subspace S” and “for every family ?? of disjoint odd sized sets there exists a subfamily ?={F_j:j ?ω} with a choice function” together imply the axiom of choice AC. We also show that AC is equivalent to the statement “in every vector space over ? every generating set includes a basis”.     

Successive continuation for locating connecting orbits

A successive continuation method for locating connecting orbits in parametrized systems of autonomous ODEs is considered. A local convergence analysis is presented and several illustrative numerical examples are given. This revised version was published online in June 2006 with corrections to the Cover Date.     

Extracting partial canonical structure for large scale eigenvalue problems

We present methods for computing a nearby partial Jordan-Schur form of a given matrix and a nearby partial Weierstrass-Schur form of a matrix pencil. The focus is on the use and the interplay of the algorithmic building blocks – the implicitly restarted Arnoldi method with prescribed restarts for computing an invariant subspace associated with the dominant eigenvalue, the clustering method for grouping computed eigenvalues into numerically multiple eigenvalues and the staircase algorithm for computing the structure revealing form of the projected problem. For matrix pencils, we present generalizations of these methods. We introduce a new and more accurate clustering heuristic for both matrices and matrix pencils. Particular emphasis is placed on reliability of the partial Jordan-Schur and Weierstrass-Schur methods with respect to the choice of deflation parameters connecting the steps of the algorithm such that the errors are controlled. Finally, successful results from computational experiments conducted on problems with known canonical structure and varying ill-conditioning are presented. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Black-Box Multigrid Preconditioner for the Biharmonic Equation

We examine the convergence characteristics of a preconditioned Krylov subspace solver applied to the linear systems arising from low-order mixed finite element approximation of the biharmonic problem. The key feature of our approach is that the preconditioning can be realized using any “black-box” multigrid solver designed for the discrete Dirichlet Laplacian operator. This leads to preconditioned systems having an eigenvalue distribution consisting of a tightly clustered set together with a small number of outliers. Numerical results show that the performance of the methodology is competitive with that of specialized fast iteration methods that have been developed in the context of biharmonic problems. This revised version was published online in July 2006 with corrections to the Cover Date.     

关于子空间的和的推广的注记

对向量空间的子空间的和的概念不能推广到无限多个子空间的情形进行了讨论.     

Dimension Reduction in Nonparametric Kernel Discriminant Analysis

This article develops a dimension-reduction method in kernel discriminant analysis, based on a general concept of separation of populations. The ideas we present lead to a characterization of the central subspace that does not impose restrictions on the marginal distribution of the feature vector. We also give a new procedure for estimating relevant directions in the central subspace. Comparisons to other procedures are studied and examples of application are discussed.     

A discrete divergence-free basis for finite element methods

The divergence-free finite element method (DFFEM) is a method to find an approximate solution of the Navier–Stokes equations in a divergence-free space. That is, the continuity equation is satisfied a priori. DFFEM eliminates the pressure from the calculations and significantly reduces the dimension of the system to be solved at each time step. For the standard 9-node velocity and 4-node pressure DFFEM, a basis for the weakly divergence-free subspace is constructed such that each basis function has nonzero support on at most 4 contiguous elements. Given this basis, weakly divergence-free macroelements are constructed. This revised version was published online in August 2006 with corrections to the Cover Date.     

On the best parametrization

The numerical solution to a system of nonlinear algebraic or transcendental equations with several parameters is examined in the framework of the parametric continuation method. Necessary and sufficient conditions are proved for choosing the best parameters, which provide the best condition number for the system of linear continuation equations. Such parameters have to be sought in the subspace tangent to the solution space of the system of nonlinear equations. This subspace is obtained if the original system of nonlinear equations is solved at the various parameter values from a given set. The parametric approximation of curves and surfaces is considered.