On the convergence of the conjugate gradient method for singular capacitance matrix equations from the Neumann problem of the Poisson equation

Summary It is shown analytically in this work that the conjugate gradient method is an efficient means of solving the singular capacitance matrix equations arising from the Neumann problem of the Poisson equation. The total operation count of the algorithm does not exceed constant timesN ²logN(N=1/h) for any bounded domain with sufficiently smooth boundary.Sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and the National Science Foundation under Grant No. MCS75-17385. Also partially supported by the Energy Research and Development Administration     

A finite element — Capacitance method for elliptic problems on regions partitioned into subregions

Summary A method is given for the solution of linear equations arising in the finite element method applied to a general elliptic problem. This method reduces the original problem to several subproblems (of the same form) considered on subregions, and an auxiliary problem. Very efficient iterative methods with the preconditioning operator and using FFT are developed for the auxiliary problem.     

Improved difference schemes for the Dirichlet problem of Poisson's equation in the neighbourhood of corners

Summary The standard 5-point difference scheme for the model problem u=f on a special polygonal domain with given boundary values is modified at a few points in the neighbourhood of the corners in such a way that the order of convergence at interior points is the same as in the case of a smooth boundary. As a side result improved error bounds for the usual method in the neighbourhood of corners are given.     

A multidomain spectral collocation method for the Stokes problem

Summary We propose a multidomain spectral collocation scheme for the approximation of the two-dimensional Stokes problem. We show that the discrete velocity vector field is exactly divergence-free and we prove error estimates both for the velocity and the pressure.Deceased     

A note on the approximation of mildly nonlinear Dirichlet problems by finite differences

Summary In [9], Simpson proved some theorems concerning the approximation of mildly nonlinear Dirichlet problems –u=f (x, u) inD, u=0 on D by finite differences. The assumptionsf(x, 0)0 andf _u(x, u)>0 in [9] have turned out to be unnecessarily restrictive and are eliminated in this paper. On the other hand, we considered it necessary to make the smoothness conditions forD slightly more stringent irrespective of the conditions imposed onf.The results of this paper are already contained in the author's doctoral thesis [6]. Meanwhile, H.B. Keller (Math. Comp. 29, p. 464–476) has published a general theory on approximation methods for nonlinear problems which can be used for obtaining Theorem 1This work was performed under the terms of the agreement on association between the Max-Planck-Institut für Plasmaphysik and EURATOM     

The ordering of tridiagonal matrices in the cyclic reduction method for Poisson's equation

Summary Discretization of the Poisson equation on a rectangle by finite differences using the standard five-point stencil yields a linear system of algebraic equations, which can be solved rapidly by the cyclic reduction method. In this method a sequence of tridiagonal linear systems is solved. The matrices of these systems commute, and we investigate numerical aspects of their ordering. In particular, we present two new ordering schemes that avoid overflow and loss of accuracy due to underflow. These ordering schemes improve the numerical performance of the subroutine HWSCRT of FISHPAK. Our orderings are also applicable to the solution of Helmholtz's equation by cyclic reduction, and to related numerical schemes, such as FACR methods.Dedicated to the memory of Peter HenriciResearch supported in part by the National Science Foundation under Grant DMS-870416     

L 2 estimates for the finite element method for the Dirichlet problem with singular data

Summary In this paper we consider the approximation by the finite element method of second order elliptic problems on convex domains and homogeneous Dirichlet condition on the boundary. In these problems the data are Borel measures. Using a quasiuniform mesh of finite elements and polynomials of degree 1, we prove that in two dimensions the convergence is of orderh inL ² and in three dimensions of orderh ^1/2.     

The rate of convergence of an approximate matrix factorization semi-direct method

Summary The definition of acceleration parameters for the convergence of a sparseLU factorization semi-direct method is shown to be based on lower and upper bounds of the extreme eigevalues of the iteration matrix. Optimum values of these parameters are established when the eigenvalues of the iteration matrix are either real or complex. Estimates for the computational work required to reduce theL ₂ norm of the error by a specified factor are also given.     

A modified bisection algorithm for the determination of the eigenvalues of a symmetric tridiagonal matrix

Summary A modification to the well known bisection algorithm [1] when used to determine the eigenvalues of a real symmetric matrix is presented. In the new strategy the terms in the Sturm sequence are computed only as long as relevant information on the required eigenvalues is obtained. The resulting algorithm usingincomplete Sturm sequences can be shown to minimise the computational work required especially when only a few eigenvalues are required.The technique is also applicable to other computational methods which use the bisection process.     

Total flux estimates for a finite element approximation of the Dirichlet problem using the boundary penalty method

Summary This paper considers a fully practical piecewise linear finite element approximation of the Dirichlet problem for a second order self-adjoint elliptic equation,Au=f, in a smooth region< ⁿ (n=2 or 3) by the boundary penalty method. Using an unfitted mesh; that is ^h , an approximation of with dist (, ^h )Ch ² is not in general a union of elements; and assuminguH ⁴ () we show that one can recover the total flux across a segment of the boundary of with an error ofO(h ²⁾. We use these results to study a fully practical piecewise linear finite element approximation of an elliptic equation by the boundary penalty method when the prescribed data on part of the boundary is the total flux.Supported by a SERC research studentship     

On the condition number of boundary integral operators for the exterior Dirichlet problem for the Helmholtz equation

Summary Brakhage and Werner, Leis and Panich suggested to reduce the exterior Dirichlet boundary value problem for the Helmholtz equation to an integral equation of the second kind which is uniquely solvable for all frequencies by seeking the solution in the form of a combined double- and single-layer potential. We present an analysis of the appropriate choice of the parameter coupling the double- and single-layer potential in order to minimize the condition number of the integral operator.This research was carried out while the second author was visiting the University of Göttingen on a DAAD-stipendium     

A factorization method for the solution of constrained linear least squares problems allowing subsequent data changes

Summary In this paper we describe how to use Gram-Schmidt factorizations of Daniel et al. [1] to realize the method of [8] for solving linearly constrained linear least squares problems. The main advantage of using these factorizations is that it is relatively easy to take data changes into account, if necessary.The algorithm is compared numerically with two other codes, one of them published by Lawson and Hanson [3]. Further computational tests show the efficiency of the proposed methods, if a few data of the original problem are changed subsequently.This paper was sponsored by Deutsche Forschungsgemeinschaft, Bonn-Bad Godesberg     

A class of iterative methods for solving saddle point problems

Summary We consider the numerical solution of indefinite systems of linear equations arising in the calculation of saddle points. We are mainly concerned with sparse systems of this type resulting from certain discretizations of partial differential equations. We present an iterative method involving two levels of iteration, similar in some respects to the Uzawa algorithm. We relate the rates of convergence of the outer and inner iterations, proving that, under natural hypotheses, the outer iteration achieves the rate of convergence of the inner iteration. The technique is applied to finite element approximations of the Stokes equations.The work of this author was supported by the Office of Naval Research under contract N00014-82K-0197, by Avions Marcel Dassault, 78 Quai Marcel Dassault, 92214 St Cloud, France, and by Direction des Recherches Etudes et Techniques, 26 boulevard Victor, F-75996 Paris Armées, FranceThe work of this author was supported by Avions Marcel Daussault-Breguet Aviation, 78 quai Marcel Daussault, F-92214 St Cloud, France and by Direction des Recherches Etudes et Techniques, 26 boulevard Victor, F-75996 Paris Armées, FranceThe work of this author was supported by Konrad-Zuse-Zentrum für Informationstechnik Berlin, Federal Republic of Germany     

A stable Richardson iteration method for complex linear systems

Summary The Richardson iteration method is conceptually simple, as well as easy to program and parallelize. This makes the method attractive for the solution of large linear systems of algebraic equations with matrices with complex eigenvalues. We change the ordering of the relaxation parameters of a Richardson iteration method proposed by Eiermann, Niethammer and Varga for the solution of such problems. The new method obtained is shown to be stable and to have better convergence properties.Research supported by the National Science Foundation under Grant DMS-8704196     

Strong underrelaxation in Kaczmarz's method for inconsistent systems

Summary We investigate the behavior of Kaczmarz's method with relaxation for inconsistent systems. We show that when the relaxation parameter goes to zero, the limits of the cyclic subsequences generated by the method approach a weighted least squares solution of the system. This point minimizes the sum of the squares of the Euclidean distances to the hyperplanes of the system. If the starting point is chosen properly, then the limits approach the minimum norm weighted least squares solution. The proof is given for a block-Kaczmarz method.     

The hierarchical basis multigrid method

Summary We derive and analyze the hierarchical basis-multigrid method for solving discretizations of self-adjoint, elliptic boundary value problems using piecewise linear triangular finite elements. The method is analyzed as a block symmetric Gauß-Seidel iteration with inner iterations, but it is strongly related to 2-level methods, to the standard multigridV-cycle, and to earlier Jacobi-like hierarchical basis methods. The method is very robust, and has a nearly optimal convergence rate and work estimate. It is especially well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes.     

A finite element method for the Tricomi problem

Summary We consider the numerical solution of the Tricomi problem. Using a weak formulation based on different spaces of test and trial functions, we construct a new Galerkin procedure for the Tricomi problem. Existence, uniqueness, and uniform stability of the approximate solution is proven, and a priori error bounds are given.Research supported in part by the Department of Energy under contract DOE E(40-1)3443     

A finite element method for the nonlinear Tricomi problem

Summary We consider a finite element procedure for numerical solution of the nonlinear problem:L[u]=yu _xx +u _yy +r(x,y)u=f(x, y, u) in a simply connected regionG in thex-y plane. The boundary ofG consists of ₀, ₁, and ₂ and we impose the boundary condition . ₀ is assumed to be a piecewises smooth curve lying in the half-planey>0 with endpointsA(–1, 0) andB(0, 0). ₁ and ₂ are characteristics of the operatorL issued fromA andB which intersect at the pointC(–1/2,y _c). An error analysis of the method is also given.     

Parallel QR decomposition of a rectangular matrix

Summary We show that the greedy algorithm introduced in [1] and [5] to perform the parallel QR decomposition of a dense rectangular matrix of sizem×n is optimal. Then we assume thatm/n ² tends to zero asm andn go to infinity, and prove that the complexity of such a decomposition is asymptotically2n, when an unlimited number of processors is available.     

Precise domains of convergence for the block SSOR method associated withp-cyclic matrices

We apply Rouché's theorem to the functional equation relating the eigenvalues of theblock symmetric successive overrelaxation (SSOR) matrix with those of the block Jacobi iteration matrix found by Varga, Niethammer, and Cai, in order to obtain precise domains of convergence for the block SSOR iteration method associated withp-cyclic matricesA, p3. The intersection of these domains, taken over all suchp's, is shown to coincide with the exact domain of convergence of thepoint SSOR iteration method associated withH-matricesA. The latter domain was essentially discovered by Neumaier and Varga, but was recently sharpened by Hadjidimos and Neumann.Research supported in part by NSF Grant DMS 870064.