KAM theorem of symplectic algorithms for Hamiltonian systems

Summary. In this paper we prove that an analog of the celebrated KAM theorem holds for symplectic algorithms, which Channel and Scovel (1990), Feng Kang (1991) and Sanz-Serna and Calvo (1994) suggested a few years ago. The main results consist of the existence of invariant tori, with a smooth foliation structure, of a symplectic numerical algorithm when it applies to a generic integrable Hamiltonian system if the system is analytic and the time-step size of the algorithm is s ufficiently small. This existence result also implies that the algorithm, when it is applied to a generic integrable system, possesses n independent smooth invariant functions which are in involution and well-defined on the set filled by the invariant tori in the sense of Whitney. The invariant tori are just the level sets of these functions. Some quantitative results about the numerical invariant tori of the algorithm approximating the exact ones of the system are also given. Received December 27, 1997 / Revised version received July 15, 1998 / Published online: July 7, 1999     

Orthosymplectic integration of linear Hamiltonian systems

Summary. The authors describe a continuous, orthogonal and symplectic factorization procedure for integrating unstable linear Hamiltonian systems. The method relies on the development of an orthogonal, symplectic change of variables to block triangular Hamiltonian form. Integration is thus carried out within the class of linear Hamiltonian systems. Use of an appropriate timestepping strategy ensures that the symplectic pairing of eigenvalues is automatically preserved. For long-term integrations, as are needed in the calculation of Lyapunov exponents, the favorable qualitative properties of such a symplectic framework can be expected to yield improved estimates. The method is illustrated and compared with other techniques in numerical experiments on the Hénon-Heiles and spatially discretized Sine-Gordon equations. Received December 11, 1995 / Revised version received April 18, 1996     

Stability analysis and fast algorithms for triangularization of Toeplitz matrices

Summary. A new algorithm for triangularizing an Toeplitz matrix is presented. The algorithm is based on the previously developed recursive algorithms that exploit the Toeplitz structure and compute each row of the triangular factor via updating and downdating steps. A forward error analysis for this existing recursive algorithm is presented, which allows us to monitor the conditioning of the problem, and use the method of corrected semi-normal equations to obtain higher accuracy for certain ill-conditioned matrices. Numerical experiments show that the new algorithm improves the accuracy significantly while the computational complexity stays in . Received April 30, 1995 / Revised version received February 12, 1996     

On higher-order semi-explicit symplectic partitioned Runge-Kutta methods for constrained Hamiltonian systems

Summary. In this paper we generalize the class of explicit partitioned Runge-Kutta (PRK) methods for separable Hamiltonian systems to systems with holonomic constraints. For a convenient analysis of such schemes, we first generalize the backward error analysis for systems in to systems on manifolds embedded in . By applying this analysis to constrained PRK methods, we prove that such methods will, in general, suffer from order reduction as well-known for higher-index differential-algebraic equations. However, this order reduction can be avoided by a proper modification of the standard PRK methods. This modification increases the number of projection steps onto the constraint manifold but leaves the number of force evaluations constant. We also give a numerical comparison of several second, fourth, and sixth order methods. Received May 5, 1995 / Revised version received February 7, 1996     

Extrapolation techniques for ill-conditioned linear systems

Summary. In this paper, the regularized solutions of an ill–conditioned system of linear equations are computed for several values of the regularization parameter . Then, these solutions are extrapolated at by various vector rational extrapolations techniques built for that purpose. These techniques are justified by an analysis of the regularized solutions based on the singular value decomposition and the generalized singular value decomposition. Numerical results illustrate the effectiveness of the procedures. Received June 23, 1997 / Revised version received October 24, 1997     

Computation of orthonormal factors for fundamental solution matrices

Summary. In this work, we introduce and analyze two new techniques for obtaining the Q factor in the QR factorization of some (or all) columns of a fundamental solution matrix Y of a linear differential system. These techniques are based on elementary Householder and Givens transformations. We implement and compare these new techniques with existing approaches on some examples. Received October 27, 1997 / Revised version received September 21, 1998 / Published online August 19, 1999     

A class of ABS algorithms for Diophantine linear systems

Summary. Systems of integer linear (Diophantine) equations arise from various applications. In this paper we present an approach, based upon the ABS methods, to solve a general system of linear Diophantine equations. This approach determines if the system has a solution, generalizing the classical fundamental theorem of the single linear Diophantine equation. If so, a solution is found along with an integer Abaffian (rank deficient) matrix such that the integer combinations of its rows span the integer null space of the cofficient matrix, implying that every integer solution is obtained by the sum of a single solution and an integer combination of the rows of the Abaffian. We show by a counterexample that, in general, it is not true that any set of linearly independent rows of the Abaffian forms an integer basis for the null space, contrary to a statement by Egervary. Finally we show how to compute the Hermite normal form for an integer matrix in the ABS framework. Received July 9, 1999 / Revised version received May 8, 2000 / Published online May 4, 2001     

Stability of Runge-Kutta methods for linear delay differential equations

Summary. This paper investigates the stability of Runge-Kutta methods when they are applied to the complex linear scalar delay differential equation . This kind of stability is called stability. We give a characterization of stable Runge-Kutta methods and then we prove that implicit Euler method is stable. Received November 3, 1998 / Revised version received March 23, 1999 / Published online July 12, 2000     

Fast algorithms for high-order spline collocation systems

Summary. In this paper, we present a complete eigenvalue analysis for arbitrary order -spline collocation methods applied to the Poisson equation on a rectangular domain with Dirichlet boundary conditions. Based on this analysis, we develop some fast algorithms for solving a class of high-order spline collocation systems which arise from discretizing the Poisson equation. Received April 8, 1997 / Revised version received August 29, 1997     

Constraint preserving integrators for general nonlinear higher index DAEs

Summary. In the last few years there has been considerable research on numerical methods for differential algebraic equations (DAEs) where is identically singular. The index provides one measure of the singularity of a DAE. Most of the numerical analysis literature on DAEs to date has dealt with DAEs with indices no larger than three. Even in this case, the systems were often assumed to have a special structure. Recently a numerical method was proposed that could, in principle, be used to integrate general unstructured higher index solvable DAEs. However, that method did not preserve constraints. This paper will discuss a modification of that approach which can be used to design constraint preserving integrators for general nonlinear higher index DAEs. Received August 25, 1993 / Revised version received April 7, 1994     

Hybrid procedures for solving linear systems

Summary. In this paper, we introduce the notion of hybrid procedures for solving a system of linear equations. A hybrid procedure consists in a combination of two arbitrary approximate solutions with coefficients summing up to one. Thus the combination only depends on one parameter whose value is chosen in order to minimize the Euclidean norm of the residual vector obtained by the hybrid procedure. Properties of such procedures are studied in detail. The two approximate solutions which are combined in a hybrid procedure are usually obtained by two iterative methods. Several strategies for combining these two methods together or with the previous iterate of the hybrid procedure itself are discussed and their properties are analyzed. Numerical experiments illustrate the various procedures. Received October 21, 1992/Revised version received May 28, 1993     

New look-ahead Lanczos-type algorithms for linear systems

Summary. A breakdown (due to a division by zero) can arise in the algorithms for implementing Lanczos' method because of the non-existence of some formal orthogonal polynomials or because the recurrence relationship used is not appropriate. Such a breakdown can be avoided by jumping over the polynomials involved. This strategy was already used in some algorithms such as the MRZ and its variants. In this paper, we propose new implementations of the recurrence relations of these algorithms which only need the storage of a fixed number of vectors, independent of the length of the jump. These new algorithms are based on Horner's rule and on a different way for computing the coefficients of the recurrence relationships. Moreover, these new algorithms seem to be more stable than the old ones and they provide better numerical results. Numerical examples and comparisons with other algorithms will be given. Received September 2, 1997 / Revised version received July 24, 1998     

Higher order numerical schemes for affinely controlled nonlinear systems

Summary. A systematic method for the derivation of high order schemes for affinely controlled nonlinear systems is developed. Using an adaptation of the stochastic Taylor expansion for control systems we construct Taylor schemes of arbitrary high order and indicate how derivative free Runge-Kutta type schemes can be obtained. Furthermore an approximation technique for the multiple control integrals appearing in the schemes is proposed. Received February 17, 2000 / Revised version received September 18, 2000 / Published online April 5, 2001     

Numerical solution of constant coefficient linear delay differential equations as abstract Cauchy problems

Summary. In this paper we present an approach for the numerical solution of delay differential equations where , and , different from the classical step-by-step method. We restate (1) as an abstract Cauchy problem and then we discretize it in a system of ordinary differential equations. The scheme of discretization is proved to be convergent. Moreover the asymptotic stability is investigated for two significant classes of asymptotically stable problems (1). Received May 4, 1998 / Revised version received January 25, 1999 / Published online November 17, 1999     

Invariant manifolds and global error estimates of numerical integration schemes applied to stiff systems of singular perturbation type -- Part I: RK-methods

Summary. For implicit RK-methods applied to singularly perturbed systems of ODEs it is shown that the resulting discrete systems preserve the geometric properties of the underlying ODE. This invariant manifold result is used to derive sharp bounds on the global error of RK-solutions. Received August 26, 1993 / Revised version received May 10, 1994     

Simulating digital circuits numerically – a charge-oriented ROW approach

A ROW type approach is considered for integral form DAEs arising in charge-oriented nodal analysis of digital networks. These network equations define very special index-2 systems that can be solved by Rosenbrock-Wanner (ROW) methods suitable for semi-explicit index-1 systems without order reduction. To obtain charge conservation, the charge variables are projected on the linear charge constraint. In contrast to the semi-explicit index-1 case, all order conditions for the algebraic variables up to order have to be fulfilled for a method of order . CHORAL, an embedded charge-oriented method of order (2)3, is introduced and compared with DASSL and RODAS for two industrial applications, the NAND gate and the two-bit adding unit. Received January 22, 1996 / Revised version received January 28, 1997     

Invariant manifolds and global error estimates of numerical integration schemes applied to stiff systems of singular perturbation type – Part II: Linear multistep methods

Summary. It is shown that appropriate linear multi-step methods (LMMs) applied to singularly perturbed systems of ODEs preserve the geometric properties of the underlying ODE. If the ODE admits an attractive invariant manifold so does the LMM. The continuous as well as the discrete dynamical system restricted to their invariant manifolds are no longer stiff and the dynamics of the full systems is essentially described by the dynamics of the systems reduced to the manifolds. These results may be used to transfer properties of the reduced system to the full system. As an example global error bounds of LMM-approximations to singularly perturbed ODEs are given. Received May 5, 1995 / Revised version received August 18, 1995     

Integration methods based on canonical coordinates of the second kind

Summary.   We present a new class of integration methods for differential equations on manifolds, in the framework of Lie group actions. Canonical coordinates of the second kind is used for representing the Lie group locally by means of its corresponding Lie algebra. The coordinate map itself can, in many cases, be computed inexpensively, but the approach also involves the inversion of its differential, a task that can be challenging. To succeed, it is necessary to consider carefully how to choose a basis for the Lie algebra, and the ordering of the basis is important as well. For semisimple Lie algebras, one may take advantage of the root space decomposition to provide a basis with desirable properties. The problem of ordering leads us to introduce the concept of an admissible ordered basis (AOB). The existence of an AOB is established for some of the most important Lie algebras. The computational cost analysis shows that the approach may lead to more efficient solvers for ODEs on manifolds than those based on canonical coordinates of the first kind presented by Munthe-Kaas. Numerical experiments verify the derived properties of the new methods. Received April 2, 1999 / Revised version received January 18, 2000 / Published online August 2, 2000     

Rigorous computational shadowing of orbits of ordinary differential equations

Summary. The existence of a true orbit near a numerically computed approximate orbit -- shadowing -- of autonomous system of ordinary differential equations is investigated. A general shadowing theorem for finite time, which guarantees the existence of shadowing in ordinary differential equations and provides error bounds for the distance between the true and the approximate orbit in terms of computable quantities, is proved. The practical use and the effectiveness of this theorem is demonstrated in the numerical computations of chaotic orbits of the Lorenz equations. Received December 15, 1993     

The NGP-stability of Runge-Kutta methods for systems of neutral delay differential equations

Summary. This paper deals with the stability analysis of implicit Runge-Kutta methods for the numerical solutions of the systems of neutral delay differential equations. We focus on the behavior of such methods with respect to the linear test equations where ,L, M and N are complex matrices. We show that an implicit Runge-Kutta method is NGP-stable if and only if it is A-stable. Received February 10, 1997 / Revised version received January 5, 1998