Algorithms for bound constrained quadratic programming problems

Summary We present an algorithm which combines standard active set strategies with the gradient projection method for the solution of quadratic programming problems subject to bounds. We show, in particular, that if the quadratic is bounded below on the feasible set then termination occurs at a stationary point in a finite number of iterations. Moreover, if all stationary points are nondegenerate, termination occurs at a local minimizer. A numerical comparison of the algorithm based on the gradient projection algorithm with a standard active set strategy shows that on mildly degenerate problems the gradient projection algorithm requires considerable less iterations and time than the active set strategy. On nondegenerate problems the number of iterations typically decreases by at least a factor of 10. For strongly degenerate problems, the performance of the gradient projection algorithm deteriorates, but it still performs better than the active set method.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38     

Coincidences of maps into homogeneous spaces

Let f,g:X→M be maps between two closed connected orientable n-manifolds where M=G/K is the homogeneous space of left cosets of a compact connected Lie group G by a finite subgroup K. In this note, we obtain a simple formula for the Lefschetz coincidence number L(f,g) in terms of topological degree, generalizing some previously known formulas for fixed points. Our approach, by means of Nielsen root theory, also allows us to give a simpler and more geometric proof of the fact that all coincidence classes of f and g have coincidence index of the same sign. Received: 3 March 1998 / Revised version: 29 June 1998     

Global convergence of the method of shortest residuals

Summary. The method of shortest residuals (SR) was presented by Hestenes and studied by Pytlak. If the function is quadratic, and if the line search is exact, then the SR method reduces to the linear conjugate gradient method. In this paper, we put forward the formulation of the SR method when the line search is inexact. We prove that, if stepsizes satisfy the strong Wolfe conditions, both the Fletcher-Reeves and Polak-Ribière-Polyak versions of the SR method converge globally. When the Wolfe conditions are used, the two versions are also convergent provided that the stepsizes are uniformly bounded; if the stepsizes are not bounded, an example is constructed to show that they need not converge. Numerical results show that the SR method is a promising alternative of the standard nonlinear conjugate gradient method. Received June 25, 1996 / Revised version received April 1, 1997 / Published online July 28, 1999     

The method of lines for Poisson's equation with nonlinear or free boundary conditions

Summary The method of lines is used to solve Poisson's equation on an irregular domain with nonlinear or free boundary conditions. The partial differential equation is approximated by a system of second order ordinary differential equations subject to multi-point boundary conditions. The system is solved with an SOR iteration which employs invariant imbedding for each one dimensional problem. An application of the method to a boundary control problem and to a free surface problem arising in electrochemical machining is described. Finally, some theoretical convergence results are presented for a model problem with radiative boundary conditions on fixed boundaries.This work was supported by the U.S. Army Research Office under Grant DA-AG29-76-G-0261     

Convergence properties of the Runge-Kutta-Chebyshev method

Summary The Runge-Kutta-Chebyshev method is ans-stage Runge-Kutta method designed for the explicit integration of stiff systems of ordinary differential equations originating from spatial discretization of parabolic partial differential equations (method of lines). The method possesses an extended real stability interval with a length proportional tos ². The method can be applied withs arbitrarily large, which is an attractive feature due to the proportionality of withs ². The involved stability property here is internal stability. Internal stability has to do with the propagation of errors over the stages within one single integration step. This internal stability property plays an important role in our examination of full convergence properties of a class of 1st and 2nd order schemes. Full convergence means convergence of the fully discrete solution to the solution of the partial differential equation upon simultaneous space-time grid refinement. For a model class of linear problems we prove convergence under the sole condition that the necessary time-step restriction for stability is satisfied. These error bounds are valid for anys and independent of the stiffness of the problem. Numerical examples are given to illustrate the theoretical results.Dedicated to Peter van der Houwen for his numerous contributions in the field of numerical integration of differential equations.Paper presented at the symposium Construction of Stable Numerical Methods for Differential and Integral Equations, held at CWI, March 29, 1989, in honor of Prof. Dr. P.J. van der Houwen to celebrate the twenty-fifth anniversary of his stay at CWI     

A convergence analysis of hopscotch methods for fourth order parabolic equations

Summary Consider the ODE (ordinary differential equation) that arises from a semi-discretization (discretization of the spatial coordinates) of a first order system form of a fourth order parabolic PDE (partial differential equation). We analyse the stability of the finite difference methods for this fourth order parabolic PDE that arise if one applies the hopscotch idea to this ODE.Often the error propagation of these methods can be represented by a three terms matrix-vector recursion in which the matrices have a certain anti-hermitian structure. We find a (uniform) expression for the stability bound (or error propagation bound) of this recursion in terms of the norms of the matrices. This result yields conditions under which these methods are strongly asymptotically stable (i.e. the stability is uniform both with respect to the spatial and the time stepsizes (tending to 0) and the time level (tending to infinity)), also in case the PDE has (spatial) variable coefficients. A convergence theorem follows immediately.     

Kauffman bracket skein module of a connected sum of 3-manifolds

We show that for the Kauffman bracket skein module over the field of rational functions in variable A, the module of a connected sum of 3-manifolds is the tensor product of modules of the individual manifolds. Received: 12 January 1998 / Revised version: 15 September 1999     

A new class of particle methods

Summary. Particle methods are numerical methods designed to solve problems in fluid mechanics and related problems in continuum mechanics. A general approach to the construction of such particle methods is presented in this article. The particles are no mass points but possess a finite extension. They can rotate in space and have a spin. The conservation of mass is automatically guaranteed by the ansatz. The forces of interaction between the particles are derived in a canonical way from the force laws of continuum mechanics and are directly based on a regularized stress tensor. In the absence of external forces and of heat sources and sinks, momentum, angular momentum, and energy are conserved as in the continuum case. Received February 17, 1995 / Revised version received December 28, 1995     

New formulations of a Stokes type problem related to the primitive equations of the atmosphere and applications

Summary. The aim of this article is to propose new algorithms for a Stokes type system related to the primitive equations of atmosphere, which are the fundamental equations for the motion of the atmosphere [6]. We derive an equivalent formulation of these equations in which the natural constraint appearing in these equations is automatically satisfied without being explicitly imposed. Numerical algorithms based on the new formulation appeared to be very competitive compared to the Uzawa-Conjugate Gradient method. Received September 10, 1998 / Published online August 2, 2000     

Convergence of approximations to the primal problem in plasticity under conditions of minimal regularity

Summary. This work considers semi- and fully discrete approximations to the primal problem in elastoplasticity. The unknowns are displacement and internal variables, and the problem takes the form of an evolution variational inequality. Strong convergence of time-discrete, as well as spatially and fully discrete approximations, is established without making any assumptions of regularity over and above those established in the proof of well-posedness of this problem. Received June 8, 1998 / Published online July 12, 2000     

Numerical approximation of quadratic observables of Schrödinger-type equations in the semi-classical limit

We apply Wigner-transform techniques to the analysis of difference methods for Schr?dinger-type equations in the case of a small Planck constant. In this way we are able to obtain sharp conditions on the spatial-temporal grid which guarantee convergence for average values of observables as the Planck constant tends to zero. The theory developed in this paper is not based on local and global error estimates and does not depend on whether caustics develop or not. Numerical test examples are presented to help interpret the theory. Received April 17, 1997 / Revised version received February 23, 1998     

An improved error bound for a finite element approximation of a model for phase separation of a multi-component alloy with a concentration dependent mobility matrix

Summary. Using a slightly different discretization scheme in time and adapting the approach in Nochetto et al. (1998) for analysing the time discretization error in the backward Euler method, we improve on the error bounds derived in (i) Barrett and Blowley (1998) and (ii) Barrett and Blowey (1999c) for a fully practical piecewise linear finite element approximation of a model for phase separation of a multi-component alloy with a concentration dependent mobility matrix and (i) a logarithmic free energy, and (ii) a non-smooth free energy (the deep quench limit); respectively. Moreover, the improved error bound in the deep quench limit is optimal. Numerical experiments with three components illustrating the above error bounds are also presented. Received June 28, 1999 / Revised version received December 3, 1999 / Published online November 8, 2000     

Analysis of finite difference schemes for unsteady Navier-Stokes equations in vorticity formulation

Summary. In this paper, we provide stability and convergence analysis for a class of finite difference schemes for unsteady incompressible Navier-Stokes equations in vorticity-stream function formulation. The no-slip boundary condition for the velocity is converted into local vorticity boundary conditions. Thom's formula, Wilkes' formula, or other local formulas in the earlier literature can be used in the second order method; while high order formulas, such as Briley's formula, can be used in the fourth order compact difference scheme proposed by E and Liu. The stability analysis of these long-stencil formulas cannot be directly derived from straightforward manipulations since more than one interior point is involved in the formula. The main idea of the stability analysis is to control local terms by global quantities via discrete elliptic regularity for stream function. We choose to analyze the second order scheme with Wilkes' formula in detail. In this case, we can avoid the complicated technique necessitated by the Strang-type high order expansions. As a consequence, our analysis results in almost optimal regularity assumption for the exact solution. The above methodology is very general. We also give a detailed analysis for the fourth order scheme using a 1-D Stokes model. Received December 10, 1999 / Revised version received November 5, 2000 / Published online August 17, 2001     

The modified method of characteristics with adjusted advection

Summary. The MMOC procedure for approximating the solutions of transport-dominated diffusion problems does not automatically preserve integral conservation laws, leading to (mass) balance errors in many kinds of flow problems. The variant, called the MMOCAA, discussed herein preserves the conservation law at a minor additional computational cost. It is shown that its solution, in either Galerkin or finite difference form, converges at the same rates as were proved earlier by Dougl as and Russell for the standard MMOC procedure. Received June 25, 1997 / Revised version received October 6, 1998 / Published online: July 7, 1999     

Accuracy and conservation properties in numerical integration: the case of the Korteweg-de Vries equation

Summary. When numerically integrating time-dependent differential equations, it is often recommended to employ methods that preserve some of the invariant quantities (mass, energy, etc.) of the problem being considered. This recommendation is usually justified on the grounds that conservation of invariant quantities may ensure that the numerical solution possesses some important qualitative features. However there are cases where schemes that preserve invariants are also advantageous in that they possess favourable error propagation mechanisms that render them superior from a quantitative point of view. In the present paper we consider the Korteweg-de Vries equation as a case study. We show rigorously that, for soliton problems and at leading order, the error of conservative schemes consists of a phase error that grows linearly with time plus a complementary term that is bounded in the norm uniformly in time. For ‘general’, nonconservative schemes the error involves a linearly growing amplitude error, a quadratically growing phase error and a complementary term that grows linearly in the norm. Numerical experiments are presented. Received November 21, 1994 / Revised version received July 17, 1995     

Finite elements for parabolic equations backwards in time

Summary Several regularization methods for parabolic equations backwards in time together with the usual additional constraints for their solution are considered. The error of the regularization is estimated from above and below. For a boundary value problem in time-method, finite elements as well as a time discretization are introduced and the error with respect to the regularized solution is estimated, thus giving an overall error of the discrete regularized problem. The algorithm is tested in simple numerical examples.     

On the stability of the unsmoothed Fourier method for hyperbolic equations

Summary. It has been a long open question whether the pseudospectral Fourier method without smoothing is stable for hyperbolic equations with variable coefficients that change signs. In this work we answer this question with a detailed stability analysis of prototype cases of the Fourier method. We show that due to weighted -stability, the -degree Fourier solution is algebraically stable in the sense that its amplification does not exceed . Yet, the Fourier method is weakly -unstable in the sense that it does experience such amplification. The exact mechanism of this weak instability is due the aliasing phenomenon, which is responsible for an amplification of the Fourier modes at the boundaries of the computed spectrum. Two practical conclusions emerge from our discussion. First, the Fourier method is required to have sufficiently many modes in order to resolve the underlying phenomenon. Otherwise, the lack of resolution will excite the weak instability which will propagate from the slowly decaying high modes to the lower ones. Second -- independent of whether smoothing was used or not, the small scale information contained in the highest modes of the Fourier solution will be destroyed by their amplification. Happily, with enough resolution nothing worse can happen. Received December 14, 1992/Revised version received March 1, 1993     

Algebraic derivation of discrete absorbing boundary conditions for the wave equation

Summary. We introduce a new algebraic framework to derive discrete absorbing boundary conditions for the wave equation in the one-dimensional case. The idea is to factor directly the discrete wave operator and then use one of the factors as boundary condition. We also analyse the stability of the schemes obtained this way and perform numerical simulations to estimate their practical value. Received June 14, 1997 / Revised version received September 15, 1997     

Regions of stability,equivalence theorems and the Courant-Friedrichs-Lewy condition

Summary The celebrated CFL condition for discretizations of hyperbolic PDEs is shown to be equivalent to some results of Jeltsch and Nevanlinna concerning regions of stability ofk-step,m-stage linear methods for the integration of ODEs. We characterize the methods for the numerical integration of the model equation,u _t=u _x which are weakly stable when the mesh-ratio takes the maximum value allowed by the CFL condition. We provide new equivalence theorems between stability and convergence, which improve on the classical results.     

Convergence of finite volume monotone schemes for scalar conservation laws on bounded domains

Summary. This paper is devoted to the study of the finite volume methods used in the discretization of conservation laws defined on bounded domains. General assumptions are made on the data: the initial condition and the boundary condition are supposed to be measurable bounded functions. Using a generalized notion of solution to the continuous problem (namely the notion of entropy process solution, see [9]) and a uniqueness result on this solution, we prove that the numerical solution converges to the entropy weak solution of the continuous problem in for every . This also yields a new proof of the existence of an entropy weak solution. Received May 18, 2000 / Revised version received November 21, 2000 / Published online June 7, 2001