Skip to main content

Über dieses Buch

The articles collected in this volume represent the contributions presented at the IMA workshop on "Dynamics of Algorithms" which took place in November 1997. The workshop was an integral part of the 1997 -98 IMA program on "Emerging Applications of Dynamical Systems." The interaction between algorithms and dynamical systems is mutually beneficial since dynamical methods can be used to study algorithms that are applied repeatedly. Convergence, asymptotic rates are indeed dynamical properties. On the other hand, the study of dynamical systems benefits enormously from having efficient algorithms to compute dynamical objects.



Complexity and Applications of Parametric Algorithms of Computational Algebraic Geometry

This article has two main goals. The first goal is to give a tutorial introduction to certain common computations in algebraic geometry which arise in numerous contexts. No prior knowledge of algebraic geometry is assumed. The second goal is to introduce a software package, called CGBlisp which is capable of performing these computations. This exposition is enhanced with simple examples which illustrate the package’s usage. The package was developed as a tool to prove a particular theory in billiard theory, but its scope is very general, as our examples demonstrate. All examples of computations with CGBLisp discussed in this paper are included in the distribution of CGBLisp.
Marek Rychlik

Conservative and Approximately Conservative Algorithms on Manifolds

Algorithms for the numerical integration of initial value problems have traditionally been either very general or very specialized. That is, the algorithms have either been intended to perform well for most vector fields or optimized to perform very well for a specific differential equation. While some classes of general purpose algorithms, e.g. implicit methods, possess combinations of advantages and disadvantages that make them particularly appropriate for some applications and inappropriate for others, the methods are still applicable to a very broad range of initial value problems. In recent years, there has been increasing interest in algorithms for specific families of dynamical systems with some common features; algorithms have been developed to accurately capture these features even when the overall accuracy of the method is relatively low.
Debra Lewis

DAEs That Should Not Be Solved

The closing decades of the 20th century have seen many scientists recognize that their mathematical models are in fact instances of DAEs, or of ODEs with invariants. Such a recognition has often carried with it the benefit of affording a new, sometimes revealing, computational look at the old problem.
Uri M. Ascher

Continuous Orthonormalization for Linear Two-Point Boundary Value Problems Revisited

In this work we revisit the continuous orthonormalization technique for solving linear two-point boundary value problems and discuss a specific implementation of the method. We infer stability of the method by putting it in a multiple shooting—like framework. Numerical examples are given.
Luca Dieci, Erik S. van Vleck

Asymptotic Expansions and Backward Analysis for Numerical Integrators

For numerical integrators of ordinary differential equations we compare the theory of asymptotic expansions of the global error with backward error analysis. On a formal level both approaches are equivalent. If, however, the arising divergent series are truncated, important features such as the semigroup property, structure perservation and exponentially small estimates over long times are valid only for the backward error analysis. We consider one-step methods as well as multistep methods, and we illustrate the theoretical results on several examples. In particular, we study the preservation of weakly stable limit cycles by symmetric methods.
Ernst Hairer, Christian Lubich

Convergence Proofs for Numerical IVP Software

The study of the running times of algorithms in computer science can be broken down into two broad types: worst-case and average-case analyses. For many problems this distinction is very important as the orders of magnitude (in terms of some measure of the problem size) of the running times may differ significantly in each case, providing useful information about the merits of the algorithm. Historically average-case analyses were first done with respect to a measure on the input data; to counter the argument that it is often difficult to find a natural measure on the data, randomised algorithms were then developed.
In this paper similar questions are studied for adaptive software used to integrate initial value problems for ODEs. In worst case these algorithms may fail completely giving O (1) errors. We consider the probability of failure for generic vector fields with random initial data chosen from a ball and perform average-case and worst-case analyses.We then perform a different average-case analysis where, having fixed the initial data, it is the algorithm that is chosen at random from some suitable class.This last analysis suggests a modified deterministicalgorithm which cannot fail for generic vector fields.
Harbir Lamba, Andrew Stuart

Bifurcations of the Complex Henon Map

The complex Henon map H(z,ω) = (z 2 + c + , dz) is the complex version of the real map studied by Henon [H]. It is also the first interesting generalization of the quadratic polynomial P c (z) = z 2 + c to two complex variables. There are some essential differences between the one and two complex variables mappings. In particular, the bifurcation locus of the Henon map is not the connectivity locus of the Julia set as in the one-complex-variable case. We will relate the complex mapping to the mapping of two real variables and to one-complex-variable mappings. We will outline a computer assisted proof to compute the location of one particular type of bifurcation and describe its relationship with attracting orbits. The study of the bifurcation locus of the complex Henon map is particularly important because it gives insight into the chaotic behavior of the real Henon map.
Estela A. Gavosto


Weitere Informationen