Multirate finite step methods

Numerical Algorithms - Many physical phenomena contain different scales. These phenomena can be modeled using partial differential equations (PDEs). Often, these PDEs can be split additively in a...     

Multirate finite step methods with varying step sizes

Many partial differential equations consist of slow and fast scales. Often, the right hand side of semidiscretized PDEs can be split additively in corresponding fast and slow parts. Many methods utilise the additive splitting of these equations, like generalized additive Runge-Kutta (GARK) methods or multirate infinitesimal step methods. The latter one treat the slow part with macro step sizes, whereas the fast part is integrated a ODE solver. The corresponding order conditions assume the exact solution of the auxiliary ODE, i.e. assume an infinite number of small steps. We extend the MIS approach by fixing the number of steps, which leads to the multirate finite steps (MFS) method. The order conditions are derived, such that the order is independent in the number of small steps in each stage. Finally, we confirm the theoretical results by numerical experiments. (© 2017 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Multirate linear multistep methods

The design of a code which uses different stepsizes for different components of a system of ordinary differential equations is discussed. Methods are suggested which achieve moderate efficiency for problems having some components with a much slower rate of variation than others. Techniques for estimating errors in the different components are analyzed and applied to automatic stepsize and order control. Difficulties, absent from non-multirate methods, arise in the automatic selection of stepsizes, leading to a suggested organization of the code that is counter-intuitive. An experimental code and some initial experiments are described.Dedicated to Professor Germund Dahlquist on the occasion of his 60th birthdaySupported in part by the Department of Energy under grant DOE DEAC0276ERO2383.Work done while attending the University of Illinois.     

Multirate infinitesimal step methods for atmospheric flow simulation

The numerical solution of the Euler equations requires the treatment of processes in different temporal scales. Sound waves propagate fast compared to advective processes. Based on a spatial discretisation on staggered grids, a multirate time integration procedure is presented here generalising split-explicit Runge-Kutta methods. The advective terms are integrated by a Runge-Kutta method with a macro stepsize restricted by the CFL number. Sound wave terms are treated by small time steps respecting the CFL restriction dictated by the speed of sound.Split-explicit Runge-Kutta methods are generalised by the inclusion of fixed tendencies of previous stages. The stability barrier for the acoustics equation is relaxed by a factor of two.Asymptotic order conditions for the low Mach case are given. The relation to commutator-free exponential integrators is discussed. Stability is analysed for the linear acoustic equation. Numerical tests are executed for the linear acoustics and the nonlinear Euler equations.     

Single step methods for linear differential equations

Summary A single step process of Runge-Rutta type is examined for a linear differential equation of ordern. Conditions are derived which constrain the parameters of the process and which are necessary to give methods of specified order. A simple set of sufficient conditions is obtained.     

Dual coordinate step methods for linear network flow problems

We review a class of recently-proposed linear-cost network flow methods which are amenable to distributed implementation. All the methods in the class use the notion of-complementary slackness, and most do not explicitly manipulate any global objects such as paths, trees, or cuts. Interestingly, these methods have stimulated a large number of newserial computational complexity results. We develop the basic theory of these methods and present two specific methods, the-relaxation algorithm for the minimum-cost flow problem, and theauction algorithm for the assignment problem. We show how to implement these methods with serial complexities of O(N ³ logNC) and O(NA logNC), respectively. We also discuss practical implementation issues and computational experience to date. Finally, we show how to implement-relaxation in a completely asynchronous, chaotic environment in which some processors compute faster than others, some processors communicate faster than others, and there can be arbitrarily large communication delays.Supported by Grant NSF-ECS-8217668 and by the Army Research Office under grant DAAL03-86-K-0171. Thanks are due to David Castañon, Paul Tseng, and Jim Orlin for their helpful comments.     

On mixed finite element methods for linear elastodynamics

Summary We construct and analyze finite element methods for approximating the equations of linear elastodynamics, using mixed elements for the discretization of the spatial variables. We consider two different mixed formulations for the problem and analyze semidiscrete and up to fourth-order in time fully discrete approximations.L ² optimal-order error estimates are proved for the approximations of displacement and stress.Work supported in part by the Hellenic State Scholarship Foundation     

Coupling of boundary integral equation and finite element methods for transmission problems in acoustics

Numerical Algorithms - In this paper, we propose a coupling of finite element method (FEM) and boundary integral equation (BIE) method for solving acoustic transmission problems in two dimensions....     

Discontinuous Galerkin finite element methods for linear elasticity and quasistatic linear viscoelasticity

Summary. We consider a finite-element-in-space, and quadrature-in-time-discretization of a compressible linear quasistatic viscoelasticity problem. The spatial discretization uses a discontinous Galerkin finite element method based on polynomials of degree r—termed DG(r)—and the time discretization uses a trapezoidal-rectangle rule approximation to the Volterra (history) integral. Both semi- and fully-discrete a priori error estimates are derived without recourse to Gronwall's inequality, and therefore the error bounds do not show exponential growth in time. Moreover, the convergence rates are optimal in both h and r providing that the finite element space contains a globally continuous interpolant to the exact solution (e.g. when using the standard ^k polynomial basis on simplicies, or tensor product polynomials, ^k, on quadrilaterals). When this is not the case (e.g. using ^k on quadri-laterals) the convergence rate is suboptimal in r but remains optimal in h. We also consider a reduction of the problem to standard linear elasticity where similarly optimal a priori error estimates are derived for the DG(r) approximation. Mathematics Subject Classification (2000):65N36Shaw and Whiteman would like to acknowledge the support of the US Army Research Office, Grant #DAAD19-00-1-0421, and the UK EPSRC, Grant #GR/R10844/01. Whiteman would also like to acknowledge support from TICAM in the form of Visiting Research Fellowships.     

Adaptive space-time finite element methods for dynamic linear thermoelasticity

This article focuses on goal oriented error control for dynamic linear thermoelastic problems. To this end, we present a space-time formulation of this problem class. The corresponding space-time Galerkin discretization is the basis for the derivation of the error estimator using the dual weighted residual (DWR) method. A numerical example substantiates the accuracy and efficiency of the presented approach. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Constant coefficient linear multistep methods with step density control

In linear multistep methods with variable step size, the method's coefficients are functions of the step size ratios. The coefficients therefore need to be recomputed on every step to retain the method's proper order of convergence. An alternative approach is to use step density control to make the method adaptive. If the step size sequence is smooth, the method can use constant coefficients without losing its order of convergence. The paper introduces this new adaptive technique and demonstrates its feasibility with a few test problems.     

General linear methods: connection to one step methods and invariant curves

Summary We generalize a result of Kirchgraber (1986) on multistep methods. We show that every strictly stable general linear method is essentially conjugate to a one step method of the same order. This result may be used to show that general properties of one step methods carry over to general linear methods. As examples we treat the existence of invariant curves and the construction of attracting sets.     

Multirate methods for the transient analysis of electrical circuits

Multirate integration is an important tool to increase the speed of the transient analysis of circuits. This paper shows an approach for the “Compound-Fast” multirate algorithm how to control the errors at the coarse and the refined time-grid by means of the independent stepsizes of these grids. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Piecewise linear finite element methods are not localized

Recent results of Schatz show that standard Galerkin finite element methods employing piecewise polynomial elements of degree two and higher to approximate solutions to elliptic boundary value problems are localized in the sense that the global dependence of pointwise errors is of higher order than the overall order of the error. These results do not indicate that such localization occurs when piecewise linear elements are used. We show via simple one-dimensional examples that Schatz's estimates are sharp in that localization indeed does not occur when piecewise linear elements are used.

     

Mixed finite element methods for linear elasticity with weakly imposed symmetry

In this paper, we construct new finite element methods for the approximation of the equations of linear elasticity in three space dimensions that produce direct approximations to both stresses and displacements. The methods are based on a modified form of the Hellinger-Reissner variational principle that only weakly imposes the symmetry condition on the stresses. Although this approach has been previously used by a number of authors, a key new ingredient here is a constructive derivation of the elasticity complex starting from the de Rham complex. By mimicking this construction in the discrete case, we derive new mixed finite elements for elasticity in a systematic manner from known discretizations of the de Rham complex. These elements appear to be simpler than the ones previously derived. For example, we construct stable discretizations which use only piecewise linear elements to approximate the stress field and piecewise constant functions to approximate the displacement field.

     

Discontinuous Galerkin finite element methods for dynamic linear solid viscoelasticity problems

We consider the usual linear elastodynamics equations augmented with evolution equations for viscoelastic internal stresses. A fully discrete approximation is defined, based on a spatially symmetric or non‐symmetric interior penalty discontinuous Galerkin finite element method, and a displacement‐velocity centred difference time discretisation. An a priori error estimate is given but only the main ideas in the proof of the error estimate are reported here due to the large number of (mostly technical) estimates that are required. The full details are referenced to a technical report. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Nonconforming finite element methods for eigenvalue problems in linear plate theory

The paper deals with nonconforming finite element methods for approximating fourth order eigenvalue problems of type ² w=w. The methods are handled within an abstract Hilbert space framework which is a special case of the discrete approximation schemes introduced by Stummel and Grigorieff. This leads to qualitative spectral convergence under rather weak conditions guaranteeing the basic properties of consistency and discrete compactness for the nonconforming methods. Further asymptotic error estimates for eigenvalues and eigenfunctions are derived in terms of the given orders of approximability and nonconformity. These results can be applied to various nonconforming finite elements used by Adini, Morley, Zienkiewicz, de Veubeke e.a. This is carried out for the simple elements of Adini and Morley and is illustrated by some numerical results at the end.