Local refinement techniques for elliptic problems on cell-centered grids

Summary Algebraic multilevel analogues of the BEPS preconditioner designed for solving discrete elliptic problems on grids with local refinement are formulated, and bounds on their relative condition numbers, with respect to the composite-grid matrix, are derived. TheV-cycle and, more generally,v-foldV-cycle multilevel BEPS preconditioners are presented and studied. It is proved that for 2-D problems theV-cycle multilevel BEPS is almost optimal, whereas thev-foldV-cycle algebraic multilevel BEPS is optimal under a mild restriction on the composite cell-centered grid. For thev-fold multilevel BEPS, the variational relation between the finite difference matrix and the corresponding matrix on the next-coarser level is not necessarily required. Since they are purely algebraically derived, thev-fold (v>1) multilevel BEPS preconditioners perform without any restrictionson the shape of subregions, unless the refinement is too fast. For theV-cycle BEPS preconditioner (2-D problem), a variational relation between the matrices on two consecutive grids is required, but there is no restriction on the method of refinement on the shape, or on the size of the subdomains.     

Some remarks on Legendrian rectifiable currents

A rectifiable current of dimension n−1 in the sphere bundle Sℝⁿ≃ℝⁿ×S ^{n −1} for euclidean space is Legendrian if it annihilates the contact 1-form α (i.e. T(α∧φ)=0 for all forms φ of degree n−2). Such a current may be naturally associated to any convex set or to any singular real analytic variety, and induces the curvature measures of such a set. We prove that the projection to ℝⁿ of a carrier of a general such T is C ²-rectifiable in the sense of Anzellotti–Serapioni. We deduce that the boundary of a set with positive reach, as well as its singular skeleta, are C ²-rectifiable. In case ∂T= 0 we prove also that the curvature measures associated to T satisfy the analogues of the classical variational formulas for curvature integrals. It follows that such formulas are valid for the curvature measures of subsets of space forms. Received: 3 December 1997/ Revised version: 25 May 1998     

Transpose-free Lanczos-type algorithms for nonsymmetric linear systems

The method of Lanczos for solving systems of linear equations is implemented by using recurrence relationships between formal orthogonal polynomials. A drawback is that the computation of the coefficients of these recurrence relationships usually requires the use of the transpose of the matrix of the system. Due to the indirect addressing, this is a costly operation. In this paper, a new procedure for computing these coefficients is proposed. It is based on the recursive computation of the products of polynomials appearing in their expressions and it does not involve the transpose of the matrix. Moreover, our approach allows to implement simultaneously and at a low price a Lanczos-type product method such as the CGS or the BiCGSTAB. This revised version was published online in June 2006 with corrections to the Cover Date.     

Parallel implementation of the p‐version of the finite element method for elliptic equations on a shared‐memory architecture

An implementation of the p‐version of the finite element method for solving two‐dimensional linear elliptic problems on a shared‐memory parallel computer is analyzed. The idea is to partition the problem among the available processors and perform computations corresponding to different elements in parallel. The parallelization is based on a domain decomposition technique using the Lagrange multipliers. The numerical experiments carried out on the Sequent system indicate very high performance of the mixed finite element algorithm in terms of attained speedups. This revised version was published online in August 2006 with corrections to the Cover Date.     

On the monotonity of incomplete factorization

Summary The Meijerink, van der Vorst type incomplete decomposition uses a position set, where the factors must be zero, but their product may differ from the original matrix. The smaller this position set is, the more the product of incomplete factors resembles the original matrix. The aim of this paper is to discuss this type of monotonity. It is shown using the Perron Frobenius theory of nonnegative matrices, that the spectral radius of the iteration matrix is a monotone function of the position set. On the other hand no matrix norm of the iteration matrix depends monotonically on the position set. Comparison is made with the modified incomplete factorization technique.     

Preconditionings and splittings for rectangular systems

Summary Recently Eiermann, Marek, and Niethammer have shown how to applysemiiterative methods to a fixed point systemx=Tx+c which isinconsistent or in whichthe powers of the fixed point operator T have no limit, to obtain iterative methods which converge to some approximate solution to the fixed point system. In view of their results we consider here stipulations on apreconditioning QAx=Qb of the systemAx=b and, separately, on asplitting A=M–N which lead to fixed point systems such that, with the aid of a semiiterative method, the iterative scheme converges to a weighted Moore-Penrose solution to the systemAx=b. We show in several ways that to obtain a meaningful limit point from a semiiterative method requires less restrictions on the splittings or the reconditionings than those which have been required in the classical Picard iterative method (see, e.g., the works of Berman and Plemmons, Berman and Neumann, and Tanabe).We pay special attention to the case when the weighted Moore-Penrose solution which is sought is the minimal norm least squares solution toAx=b.Research supported by the Deutsche ForschungsgemeinschaftPartially supported by AFOSR research grant 88-0047     

Commuting extensions and cubature formulae

Based on a novel point of view on 1-dimensional Gaussian quadrature, we present a new approach to d-dimensional cubature formulae. It is well known that the nodes of 1-dimensional Gaussian quadrature can be computed as eigenvalues of the so-called Jacobi matrix. The d-dimensional analog is that cubature nodes can be obtained from the eigenvalues of certain mutually commuting matrices. These are obtained by extending (adding rows and columns to) certain noncommuting matrices A₁,...,A_d, related to the coordinate operators x₁,...,x_d, in R^d. We prove a correspondence between cubature formulae and “commuting extensions” of A₁,...,A_d, satisfying a compatibility condition which, in appropriate coordinates, constrains certain blocks in the extended matrices to be zero. Thus, the problem of finding cubature formulae can be transformed to the problem of computing (and then simultaneously diagonalizing) commuting extensions. We give a general discussion of existence and of the expected size of commuting extensions and briefly describe our attempts at computing them.     

The proper L-S category of Whitehead manifolds

It is shown that the proper L-S category of an eventually end-irreducible, R²-irreducible Whitehead 3-manifold is 4. For this we prove, in the category of germs at infinity of proper maps, a partial analogue of the characterization by Eilenberg and Ganea of the L-S category of an aspherical space.     

Lower bounds for three-dimensional nonoverlapping domain decomposition algorithms

Summary. Lower bounds for the condition numbers of the preconditioned systems are obtained for the wire basket preconditioner and the Neumann-Neumann preconditioner in three dimensions. They show that the known upper bounds are sharp. Received January 28, 2001 / Revised version received September 3, 2001 / Published online January 30, 2002 This work was supported in part by the National Science Foundation under Grant Nos. DMS-9600133 and DMS-0074246     

A uniqueness result related to the stability of explicit Runge-Kutta methods

The polynomial associated with the largest disk of stability of anm-stage explict Runge-Kutta method of orderp is unique.