Two new variants of nonlinear inexact Uzawa algorithms for saddle-point problems

Summary. In this paper, we consider some nonlinear inexact Uzawa methods for iteratively solving linear saddle-point problems. By means of a new technique, we first give an essential improvement on the convergence results of Bramble-Paschiak-Vassilev for a known nonlinear inexact Uzawa algorithm. Then we propose two new algorithms, which can be viewed as a combination of the known nonlinear inexact Uzawa method with the classical steepest descent method and conjugate gradient method respectively. The two new algorithms converge under very practical conditions and do not require any apriori estimates on the minimal and maximal eigenvalues of the preconditioned systems involved, including the preconditioned Schur complement. Numerical results of the algorithms applied for the Stokes problem and a purely linear system of algebraic equations are presented to show the efficiency of the algorithms. Received December 8, 1999 / Revised version received September 8, 2001 / Published online March 8, 2002 RID="*" ID="*" The work of this author was partially supported by a grant from The Institute of Mathematical Sciences, CUHK RID="**" ID="**" The work of this author was partially supported by Hong Kong RGC Grants CUHK 4292/00P and CUHK 4244/01P     

Perturbation results for nearly uncoupled Markov chains with applications to iterative methods

Summary The standard perturbation theory for linear equations states that nearly uncoupled Markov chains (NUMCs) are very sensitive to small changes in the elements. Indeed, some algorithms, such as standard Gaussian elimination, will obtain poor results for such problems. A structured perturbation theory is given that shows that NUMCs usually lead to well conditioned problems. It is shown that with appropriate stopping, criteria, iterative aggregation/disaggregation algorithms will achieve these structured error bounds. A variant of Gaussian elimination due to Grassman, Taksar and Heyman was recently shown by O'Cinneide to achieve such bounds.Supported by the National Science Foundation under grant CCR-9000526 and its renewal, grant CCR-9201692. This research was done in part, during the author's visit to the Institute for Mathematics and its Applications, 514 Vincent Hall, 206 Church St. S.E., University of Minnesota, Minneapolis, MN 55455, USA     

Evaluation of the discrepancy of the linear congruential pseudo-random number sequencies

The discrepancy of a pseudo-random number (PRN) sequence has been defined as a quantity which measures the deviation of the sequence's distribution from the ideal uniform distribution. In this paper, we give three algorithms for computer evaluation of the discrepancy of PRN sequences. The computational results for the discrepancy of PRN sequences generated by a linear congruential method are included.This research is partially funded by Natural Sciences and Engineering Research Council of Canada, Grant No. 0GP00089. A research grant from IBM Canada through the Supercomputer Center, University of New Brunswick, is gratefully acknowledged.     

Sparse null basis computations in structural optimization

Summary We study the computation of sparse null bases of equilibrium matrices in the context of the force method in structural optimization. Two classes of structural problems are considered. For the class of rigid jointed skeletal structures, we use a partitioning method suggested by Henderson and Maunder to partition the problem into a set of independent null basis computations. For the class of structures represented by a continuum, we compute a sizable fraction of the null vectors in a basis from a consideration of the finite element formulation and the bipartite graph of the equilibrium matrix. The remaining null vectors are computed by the triangular algorithm in [6]. The new algorithms find sparser bases than the triangular algorithm and are also faster.This research was partially supported by NSF grant CCR-8701723 and AFOSR grant 88-0161     

An iterative substructuring algorithm for equilibrium equations

Summary The topic of iterative substructuring methods, and more generally domain decomposition methods, has been extensively studied over the past few years, and the topic is well advanced with respect to first and second order elliptic problems. However, relatively little work has been done on more general constrained least squares problems (or equivalent formulations) involving equilibrium equations such as those arising, for example, in realistic structural analysis applications. The potential is good for effective use of iterative algorithms on these problems, but such methods are still far from being competitive with direct methods in industrial codes. The purpose of this paper is to investigate an order reducing, preconditioned conjugate gradient method proposed by Barlow, Nichols and Plemmons for solving problems of this type. The relationships between this method and nullspace methods, such as the force method for structures and the dual variable method for fluids, are examined. Convergence properties are discussed in relation to recent optimality results for Varga's theory ofp-cyclic SOR. We suggest a mixed approach for solving equilibrium equations, consisting of both direct reduction in the substructures and the conjugate gradient iterative algorithm to complete the computations.Dedicated to R. S. Varga on the occasion of his 60th birthdayResearch completed while pursuing graduate studies sponsored by the Department of Mathematical Sciences, US Air Force Academy, CO, and funded by the Air Force Institute of Technology, WPAFB, OHResearch supported by the Air Force under grant no. AFOSR-88-0285 and by the National Science Foundation under grant no. DMS-89-02121     

The method of fractional steps for conservation laws

Summary The stability, accuracy, and convergence of the basic fractional step algorithms are analyzed when these algorithms are used to compute discontinuous solutions of scalar conservation laws. In particular, it is proved that both first order splitting and Strang splitting algorithms always converge to the unique weak solution satisfying the entropy condition. Examples of discontinuous solutions are presented where both Strang-type splitting algorithms are only first order accurate but one of the standard first order algorithms is infinite order accurate. Various aspects of the accuracy, convergence, and correct entropy production are also studied when each split step is discretized via monotone schemes, Lax-Wendroff schemes, and the Glimm scheme.Partially supported by an Alfred Sloan Foundation fellowship and N.S.F. grant MCS-76-10227Sponsored by US Army under contract No. DAA 629-75-0-0024     

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     

Reguläre Zerlegungen und Berechnung des Spektralradius nichtnegativer Matrizen

Summary On the basis of a Rayleigh Quotient Iteration method in [10] and a Maximal Quotient Iteration method in [5, 8] two algorithms for solving special eigenvalue problems are developed. The characteristic properties of these methods lie in the application of iterative linear methods to solving systems of linear equations. The convergence properties are investigated. We apply the algorithms to the computation of the spectralradius of a nonnegative irreducible matrix.

     

An algorithm to compute a sparse basis of the null space

Summary LetA be a realm×n matrix with full row rankm. In many algorithms in engineering and science, such as the force method in structural analysis, the dual variable method for the Navier-Stokes equations or more generally null space methods in quadratic programming, it is necessary to compute a basis matrixB for the null space ofA. HereB isn×r, r=n–m, of rankr, withAB=0. In many instancesA is large and sparse and often banded. The purpose of this paper is to describe and test a variation of a method originally suggested by Topcu and called the turnback algorithm for computing a banded basis matrixB. Two implementations of the algorithm are given, one using Gaussian elimination and the other using orthogonal factorization by Givens rotations. The FORTRAN software was executed on an IBM 3081 computer with an FPS-164 attached array processor at the Triangle Universities Computing Center and on a CYBER 205 vector computer. Test results on a variety of structural analysis problems including two- and three-dimensional frames, plane stress, plate bending and mixed finite element problems are discussed. These results indicate that both implementations of the algorithm yielded a well-conditioned, banded, basis matrixB whenA is well-conditioned. However, the orthogonal implementation yielded a better conditionedB for large, illconditioned problems.The research by these authors was supported by the U.S. Air Force under grant No. AFOSR-83-0255 and by the National Science Foundation under grant No. MCS-82-19500The research by these authors was supported by the Applied Mathematical Sciences Program of the U.S. Department of Energy, under contract to Martin Marietta Energy Systems, Inc.     

An algorithm for the fast solution of symmetric linear complementarity problems

This paper studies algorithms for the solution of mixed symmetric linear complementarity problems. The goal is to compute fast and approximate solutions of medium to large sized problems, such as those arising in computer game simulations and American options pricing. The paper proposes an improvement of a method described by Kocvara and Zowe (Numer Math 68:95–106, 1994) that combines projected Gauss–Seidel iterations with subspace minimization steps. The proposed algorithm employs a recursive subspace minimization designed to handle severely ill-conditioned problems. Numerical tests indicate that the approach is more efficient than interior-point and gradient projection methods on some physical simulation problems that arise in computer game scenarios. The research of J. L. Morales was supported by Asociación Mexicana de Cultura AC and CONACyT-NSF grant J110.388/2006. The research of J. Nocedal was supported by National Science Foundation grant CCF-0514772, Department of Energy grant DE-FG02-87ER25047-A004 and a grant from the Intel Corporation.     

On the spectra of sums of orthogonal projections with applications to parallel computing

Many parallel iterative algorithms for solving symmetric, positive definite problems proceed by solving in each iteration, a number of independent systems on subspaces. The convergence of such methods is determined by the spectrum of the sums of orthogonal projections on those subspaces, while the convergence of a related sequential method is determined by the spectrum of the product of complementary projections. We study spectral properties of sums of orthogonal projections and in the case of two projections, characterize the spectrum of the sum completely in terms of the spectrum of the product.This work was supported in part by the Norwegian Research Council for Science and the Humanities under grant D.01.08.054 and by The Royal Norwegian Council for Scientific and Industrial Research under grant IT2.28.28484; also supported in part by the Air Force Office of Scientific Research under grant AFOSR-86-0126 and by the National Science Foundation under grant DMS-8704169.     

On the finite volume element method

Summary The finite volume element method (FVE) is a discretization technique for partial differential equations. It uses a volume integral formulation of the problem with a finite partitioning set of volumes to discretize the equations, then restricts the admissible functions to a finite element space to discretize the solution. this paper develops discretization error estimates for general selfadjoint elliptic boundary value problems with FVE based on triangulations with linear finite element spaces and a general type of control volume. We establishO(h) estimates of the error in a discreteH ¹ semi-norm. Under an additional assumption of local uniformity of the triangulation the estimate is improved toO(h ²). Results on the effects of numerical integration are also included.This research was sponsored in part by the Air Force Office of Scientific Research under grant number AFOSR-86-0126 and the National Science Foundation under grant number DMS-8704169. This work was performed while the author was at the University of Colorado at Denver     

Local convergence analysis for partitioned quasi-Newton updates

Summary This paper considers local convergence properties of inexact partitioned quasi-Newton algorithms for the solution of certain non-linear equations and, in particular, the optimization of partially separable objective functions. Using the bounded deterioration principle, one obtains local and linear convergence, which impliesQ-superlinear convergence under the usual conditions on the quasi-Newton updates. For the optimization case, these conditions are shown to be satisfied by any sequence of updates within the convex Broyden class, even if some Hessians are singular at the minimizer. Finally, local andQ-superlinear convergence is established for an inexact partitioned variable metric method under mild assumptions on the initial Hessian approximations.Work supported by a research grant of the Deutsche Forschungsgemeinschaft, Bonn and carried out at the Department of Applied Mathematics and Theoretical Physics Cambridge (United Kingdom)     

Rate of Convergence for some constraint decomposition methods for nonlinear variational inequalities

Summary. Some general subspace correction algorithms are proposed for a convex optimization problem over a convex constraint subset. One of the nontrivial applications of the algorithms is the solving of some obstacle problems by multilevel domain decomposition and multigrid methods. For domain decomposition and multigrid methods, the rate of convergence for the algorithms for obstacle problems is of the same order as the rate of convergence for jump coefficient linear elliptic problems. In order to analyse the convergence rate, we need to decompose a finite element function into a sum of functions from the subspaces and also satisfying some constraints. A special nonlinear interpolation operator is introduced for decomposing the functions. Received December 13, 2001 / Revised version received February 19, 2002 / Published online June 17, 2002 This work was partially supported by the Norwegian Research Council under projects 128224/431 and SEP-115837/431.     

Stability of explicit time discretizations for solving initial value problems

Summary Stability regions of explicit linear time discretization methods for solving initial value problems are treated. If an integration method needsm function evaluations per time step, then we scale the stability region by dividing bym. We show that the scaled stability region of a method, satisfying some reasonable conditions, cannot be properly contained in the scaled stability region of another method. Bounds for the size of the stability regions for three different purposes are then given: for general nonlinear ordinary differential systems, for systems obtained from parabolic problems and for systems obtained from hyperbolic problems. We also show how these bounds can be approached by high order methods.This research has been supported by the Swiss National Foundation, grant No. 82-524.077     

Parallel algorithms for maximal monotone operators of local type

Summary. This paper presents general algorithms for the parallel solution of finite element problems associated with maximal monotone operators of local type. The latter concept, which is also introduced here, is well suited to capture the idea that the given operator is the discretization of a differential operator that may involve nonlinearities and/or constraints as long as those are of a local nature. Our algorithms are obtained as a combination of known algorithms for possibly multi-valued maximal monotone operators with appropriate decompositions of the domain. This work extends a method due to two of the authors in the single-valued and linear case. Received April 25, 1994     

A finite volume method based on the Crouzeix–Raviart element for elliptic PDE's in two dimensions

We introduce and analyse a finite volume method for the discretization of elliptic boundary value problems in . The method is based on nonuniform triangulations with piecewise linear nonconforming spaces. We prove optimal order error estimates in the –norm and a mesh dependent –norm. Received September 10, 1997 / Revised version received March 18, 1998     

Two-grid finite volume element method for linear and nonlinear elliptic problems

Two-grid finite volume element discretization techniques, based on two linear conforming finite element spaces on one coarse and one fine grid, are presented for the two-dimensional second-order non-selfadjoint and indefinite linear elliptic problems and the two-dimensional second-order nonlinear elliptic problems. With the proposed techniques, solving the non-selfadjoint and indefinite elliptic problem on the fine space is reduced into solving a symmetric and positive definite elliptic problem on the fine space and solving the non-selfadjoint and indefinite elliptic problem on a much smaller space; solving a nonlinear elliptic problem on the fine space is reduced into solving a linear problem on the fine space and solving the nonlinear elliptic problem on a much smaller space. Convergence estimates are derived to justify the efficiency of the proposed two-grid algorithms. A set of numerical examples are presented to confirm the estimates. The work is supported by the National Natural Science Foundation of China (Grant No: 10601045).     

A domain decomposition algorithm for elliptic problems in three dimensions

Summary Most domain decomposition algorithms have been developed for problems in two dimensions. One reason for this is the difficulty in devising a satisfactory, easy-to-implement, robust method of providing global communication of information for problems in three dimensions. Several methods that work well in two dimension do not perform satisfactorily in three dimensions.A new iterative substructuring algorithm for three dimensions is proposed. It is shown that the condition number of the resulting preconditioned problem is bounded independently of the number of subdomains and that the growth is quadratic in the logarithm of the number of degrees of freedom associated with a subdomain. The condition number is also bounded independently of the jumps in the coefficients of the differential equation between subdomains. The new algorithm also has more potential parallelism than the iterative substructuring methods previously proposed for problems in three dimensions.This work was supported in part by the National Science Foundation under grant NSF-CCR-8903003 and by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Extrapolation methods for dynamic partial differential equations

Summary Several extrapolation procedures are presented for increasing the order of accuracy in time for evolutionary partial differential equations. These formulas are based on finite difference schemes in both the spatial and temporal directions. One of these schemes reduces to a Runge-Kutta type formula when the equations are linear. On practical grounds the methods are restricted to schemes that are fourth order in time and either second, fourth or sixth order in space. For hyperbolic problems the second order in space methods are not useful while the fourth order methods offer no advantage over the Kreiss-Oliger method unless very fine meshes are used. Advantages are first achieved using sixth order methods in space coupled with fourth order accuracy in time. The averaging procedure advocated by Gragg does not increase the efficiency of the scheme. For parabolic problems severe stability restrictions are encountered that limit the applicability to problems with large cell Reynolds number. Computational results are presented confirming the analytic discussions.This report was prepared as a result of work performed under NASA Contract No. NAS1-14101 while the author was in residence at ICASE, NASA Langley Research Center, Hampton, VA 23665, USA, and under ERDA Grant No. E(11-1)-3077-III while he was at Courant Institute of Mathematical Sciences, New York, NY 10012, USA