Geometric Integration Methods that Preserve Lyapunov Functions

We consider ordinary differential equations (ODEs) with a known Lyapunov function V. To ensure that a numerical integrator reflects the correct dynamical behaviour of the system, the numerical integrator should have V as a discrete Lyapunov function. Only second-order geometric integrators of this type are known for arbitrary Lyapunov functions. In this paper we describe projection-based methods of arbitrary order that preserve any given Lyapunov function. AMS subject classification (2000) 65L05, 65L06, 65L20, 65P40     

Two-frequency decomposition

Summary. In this paper, we present a preconditioner for large systems of linear equations based on the block decomposition for block-tridiagonal matrices. This decomposition is in many respects similar to the frequency-filtering method of Wittum [18] and also to the frequency-filtering decomposition of Wagner [4]–[6]. In contrast to these methods, our approach requires no pointwise filtering conditions but, as in [1], only averaged ones; this simplifies the implementation without any loss of efficiency. Theoretical analysis of the model problem leads to the convergence rate . Numerical experiments demonstrate similar convergence behaviour for a wider class of problems.Mathematics Subject Classification (2000): 65F10, 65N22     

Global modified Hamiltonian for constrained symplectic integrators

Summary. We prove that the numerical solution of partitioned Runge-Kutta methods applied to constrained Hamiltonian systems (e.g., the Rattle algorithm or the Lobatto IIIA–IIIB pair) is formally equal to the exact solution of a constrained Hamiltonian system with a globally defined modified Hamiltonian. This property is essential for a better understanding of their longtime behaviour. As an illustration, the equations of motion of an unsymmetric top are solved using a parameterization with Euler parameters. Mathematics Subject Classification (2000):65L06, 65L80, 65P10     

Numerical integrators for quantum dynamics close to the adiabatic limit

Summary.  We study the numerical solution of singularly perturbed Schr?-dinger equations with time-dependent Hamiltonian. Based on a reformulation of the equations, we derive time-reversible numerical integrators which can be used with step sizes that are substantially larger than with traditional integration schemes. A complete error analysis is given for the adiabatic case. To deal with avoided crossings of energy levels, which lead to non-adiabatic behaviour, we propose an adaptive extension of the methods which resolves the sharp transients that appear in non-adiabatic state transitions. Received November 12, 2001 / Revised version received May 8, 2002 / Published online October 29, 2002 Mathematics Subject Classification (1991): 65L05, 65M15, 65M20, 65L70.     

Performance of ILU factorization preconditioners based on multisplittings

Summary. In this paper, we study the convergence of multisplitting methods associated with a multisplitting which is obtained from the ILU factorizations of a general H-matrix, and then we propose parallelizable ILU factorization preconditioners based on multisplittings for a block-tridiagonal H-matrix. We also describe a parallelization of preconditioned Krylov subspace methods with the ILU preconditioners based on multisplittings on distributed memory computers such as the Cray T3E. Lastly, parallel performance results of the preconditioned BiCGSTAB are provided to evaluate the efficiency of the ILU preconditioners based on multisplittings on the Cray T3E. Mathematics Subject Classification (2000):65F10, 65Y05, 65F50This work was supported by Korea Research Foundation Grant (KRF-2001-015-DP0051)     

On the asymptotic behaviour of some new gradient methods

The Barzilai-Borwein (BB) gradient method, and some other new gradient methods have shown themselves to be competitive with conjugate gradient methods for solving large dimension nonlinear unconstrained optimization problems. Little is known about the asymptotic behaviour, even when applied to n−dimensional quadratic functions, except in the case that n=2. We show in the quadratic case how it is possible to compute this asymptotic behaviour, and observe that as n increases there is a transition from superlinear to linear convergence at some value of n≥4, depending on the method. By neglecting certain terms in the recurrence relations we define simplified versions of the methods, which are able to predict this transition. The simplified methods also predict that for larger values of n, the eigencomponents of the gradient vectors converge in modulus to a common value, which is a similar to a property observed to hold in the real methods. Some unusual and interesting recurrence relations are analysed in the course of the study.This work was supported by the EPRSC in UK (no. GR/R87208/01) and the Chinese NSF grant (no. 10171104)     

Fast computation in adaptive tree approximation

Summary. Adaptive methods of approximation arise in many settings including numerical methods for PDEs and image processing. They can usually be described by a tree which records the adaptive decisions. This paper is concerned with the fast computation of near optimal trees based on n adaptive decisions. The best tree based on n adaptive decisions could be found by examining all such possibilities. However, this is exponential in n and could be numerically prohibitive. The main result of this paper is to show that it is possible to find near optimal trees using computations linear in n.Mathematics Subject Classification (2000): 65Y20, 65N50, 41A63, 41A15, 68W40, 68W25This work has been supported in part by the Office of Naval Research contracts 03-10051, (N00014-00-1-0470), the Army Research Office contract DAAD 19-02-1-0028, and the National Science Foundation grants DMS 9872890, DMS 0221642.     

Matrix-free preconditioning using partial matrix estimation

We consider matrix-free solver environments where information about the underlying matrix is available only through matrix vector computations which do not have access to a fully assembled matrix. We introduce the notion of partial matrix estimation for constructing good algebraic preconditioners used in Krylov iterative methods in such matrix-free environments, and formulate three new graph coloring problems for partial matrix estimation. Numerical experiments utilizing one of these formulations demonstrate the viability of this approach. AMS subject classification (2000) 65F10, 65F50, 49M37, 90C06     

A model for two coupled turbulent fluids Part III: Numerical approximation by finite elements

Summary. This paper introduces a scheme for the numerical solution of a model for two turbulent flows with coupling at an interface. We consider a variational formulation of the coupled model, where the turbulent kinetic energy equation is formulated by transposition. We prove the convergence of the approximation to this formulation for 2D flows by piecewise affine triangular elements. Our main contribution is to prove that the standard Galerkin - finite element approximation of the Laplace equation approximates in L² norm its solution by transposition, for data with low smoothness. We include some numerical tests for simple geometries that exhibit the behaviour predicted by our analysis.Mathematics Subject Classification (2000): 65 N30, 76M10Revised version received March 24, 2003This research was partially supported by Spanish Government REN2000-1162-C02-01 and REN2000-1168-C02-01 grants     

Stopping criteria for iterations in finite element methods

Summary. This work extends the results of Arioli [1], [2] on stopping criteria for iterative solution methods for linear finite element problems to the case of nonsymmetric positive-definite problems. We show that the residual measured in the norm induced by the symmetric part of the inverse of the system matrix is relevant to convergence in a finite element context. We then use Krylov solvers to provide alternative ways of calculating or estimating this quantity and present numerical experiments which validate our criteria.Mathematics Subject Classification (2000): 65N30, 65F10, 65F35     

Global and blow‐up solutions for non‐linear degenerate parabolic systems

In this paper the degenerate parabolic system u_t=u(u_xx+av). vt=v(v_xx+bu) with Dirichlet boundary condition is studied. For , the global existence and the asymptotic behaviour (α₁=α₂) of solution are analysed. For , the blow‐up time, blow‐up rate and blow‐up set of blow‐up solution are estimated and the asymptotic behaviour of solution near the blow‐up time is discussed by using the ‘energy’ method. Copyright © 2003 John Wiley & Sons, Ltd.     

Quadrature methods for highly oscillatory linear and nonlinear systems of ordinary differential equations: part I

This work presents methods of efficient numerical approximation for linear and nonlinear systems of highly oscillatory ordinary differential equations. We show how an appropriate choice of quadrature rule improves the accuracy of approximation as the frequency of oscillation grows. We present asymptotic and Filon-type methods to solve highly oscillatory linear systems of ODEs, and WRF method, representing a special combination of Filon-type methods and waveform relaxation methods, for nonlinear systems. Numerical examples support this paper. Dedicated to the memory of Rudolf Khanamiryan. AMS subject classification (2000)  65L05, 34E05, 34C15     

Boundary element tearing and interconnecting methods in unbounded domains

Finite element tearing and interconnecting (FETI) methods and boundary element tearing and interconnecting (BETI) methods are special iterative substructuring methods with Lagrange multipliers. For elliptic boundary value problems on bounded domains, the condition number of these methods can be rigorously bounded by C(1+log(H/h))², where H is the subdomain diameter and h the mesh size. The constant C is independent of H, h and possible jumps in the coefficients of the partial differential equation.In certain situations, e.g., in electromagnetic field computations, instead of imposing artificial boundary conditions one may be interested in modelling the real physical behaviour in an exterior domain with a radiation condition. In this work we analyze one-level BETI methods for such unbounded domains and show explicit condition number estimates similar to the one above. Our theoretical results are confirmed in numerical experiments.     

Heat equation on the arithmetic von Koch snowflake

We investigate the asymptotic behaviour of the heat content as the time t→ 0 for an s-adic von Koch snowflake generated by a square. We show that the heat content satisfies a functional equation which, after appropriate transformations, takes the form of an inhomogeneous renewal equation. We obtain the structure of the solution of this equation in the arithmetic case up to an exponentially small remainder in t. <!-ID="Mathematics Subject Classification (2000): 35K05, 60J65, 28A80--> <!-ID="Key words: Heat equation – Arithmetic – Snowflake--> Received: 24 March 1999 / Revised version: 14 October 1999 / Published online : 8 August 2000     

BiCGstab(l) and other hybrid Bi-CG methods

It is well-known that Bi-CG can be adapted so that the operations withA ^T can be avoided, and hybrid methods can be constructed in which it is attempted to further improve the convergence behaviour. Examples of this are CGS, Bi-CGSTAB, and the more general BiCGstab(l) method. In this paper it is shown that BiCGstab(l) can be implemented in different ways. Each of the suggested approaches has its own advantages and disadvantages. Our implementations allow for combinations of Bi-CG with arbitrary polynomial methods. The choice for a specific implementation can also be made for reasons of numerical stability. This aspect receives much attention. Various effects have been illustrated by numerical examples.     

Fast conservative and entropic numerical methods for the Boson Boltzmann equation

Summary. In this paper we derive accurate numerical methods for the quantum Boltzmann equation for a gas of interacting bosons. The schemes preserve the main physical features of the continuous problem, namely conservation of mass and energy, the entropy inequality and generalized Bose-Einstein distributions as steady states. These properties are essential in order to develop schemes that are able to capture the energy concentration behavior of bosons. In addition we develop fast algorithms for the numerical evaluation of the resulting quadrature formulas which allow the final schemes to be computed only in O(N² log ₂N) operations instead of O(N³).Mathematics Subject Classification (2000):82C10, 76P05, 65D32, 65T50This work was supported by the WITTGENSTEIN AWARD 2000 of Peter Markowich, financed by the Austrian Research Fund FWF and by the European network HYKE, funded by the EC as contract HPRN-CT-2002-00282.     

Approximate compositions of a near identity map by multi-revolution Runge-Kutta methods

Summary. The so-called multi-revolution methods were introduced in celestial mechanics as an efficient tool for the long-term numerical integration of nearly periodic orbits of artificial satellites around the Earth. A multi-revolution method is an algorithm that approximates the map _T^N of N near-periods T in terms of the one near-period map _T evaluated at few s << N selected points. More generally, multi-revolution methods aim at approximating the composition ^N of a near identity map . In this paper we give a general presentation and analysis of multi-revolution Runge-Kutta (MRRK) methods similar to the one developed by Butcher for standard Runge-Kutta methods applied to ordinary differential equations. Order conditions, simplifying assumptions, and order estimates of MRRK methods are given. MRRK methods preserving constant Poisson/symplectic structures and reversibility properties are characterized. The construction of high order MRRK methods is described based on some families of orthogonal polynomials.Mathematics Subject Classification (1991): 65L05, 65L06This material is based upon work supported by the National Science Foundation Grant No. 9983708 and by the DGI Grant BFM2001–2562     

Analysis of a family of discontinuous Galerkin methods for elliptic problems: the one dimensional case

Summary. In this paper we analyze a family of discontinuous Galerkin methods, parameterized by two real parameters, for elliptic problems in one dimension. Our main results are: (1) a complete inf-sup stability analysis characterizing the parameter values yielding a stable scheme and energy norm error estimates as a direct consequence thereof, (2) an analysis of the error in L² where the standard duality argument only works for special parameter values yielding a symmetric bilinear form and different orders of convergence are obtained for odd and even order polynomials in the nonsymmetric case. The analysis is consistent with numerical results and similar behavior is observed in two dimensions.Mathematics Subject Classification (2000): 65M60, 65M15Research supported by: The Swedish Foundation for International Cooperation in Research and Higher Education     

New Cartesian grid methods for interface problems using the finite element formulation

Summary New finite element methods based on Cartesian triangulations are presented for two dimensional elliptic interface problems involving discontinuities in the coefficients. The triangulations in these methods do not need to fit the interfaces. The basis functions in these methods are constructed to satisfy the interface jump conditions either exactly or approximately. Both non-conforming and conforming finite element spaces are considered. Corresponding interpolation functions are proved to be second order accurate in the maximum norm. The conforming finite element method has been shown to be convergent. With Cartesian triangulations, these new methods can be used as finite difference methods. Numerical examples are provided to support the methods and the theoretical analysis. Mathematics Subject Classification (2000):65L10, 65L60, 65L70In this research, Zhilin Li is supported in part by USA ARO grants, 39676-MA and 43751-MA, USA NSF grants DMS-0073403 and DMS-0201094; USA North Carolina State University FR&PD grant; Tao Lin is supported in part a USA NSF grant DMS-97-04621. Special thanks to Thomas Hou for his participation and contribution to this project. We are also grateful to R. LeVeque, K. Bube, and T. Chan for useful discussions.     

Preconditioners Based on Fit Techniques for the Iterative Regularization in the Image Deconvolution Problem

For large-scale image deconvolution problems, the iterative regularization methods can be favorable alternatives to the direct methods. We analyze preconditioners for regularizing gradient-type iterations applied to problems with 2D band Toeplitz coefficient matrix. For problems having separable and positive definite matrices, the fit preconditioner we have introduced in a previous paper has been shown to be effective in conjunction with CG. The cost of this preconditioner is of O(n²) operations per iteration, where n² is the pixels number of the image, whereas the cost of the circulant preconditioners commonly used for this type of problems is of O(n² log n) operations per iteration. In this paper the extension of the fit preconditioner to more general cases is proposed: namely the nonseparable positive definite case and the symmetric indefinite case. The major difficulty encountered in this extension concerns the factorization phase, where a further approximation is required. Three approximate factorizations are proposed. The preconditioners thus obtained have still a cost of O(n²) operations per iteration. A numerical experimentation shows that the fit preconditioners are competitive with the regularizing Chan preconditioner, both in the regularizing efficiency and the computational cost. AMS subject classification (2000) 65F10, 65F22.Received October 2003. Accepted December 2004. Communicated by Lars Eldén.