From the outset the dynamical systems community has been aware of these new opportunities for the expansion of its field. Since more than a decade the computer has been fruitfully applied to problems ranging from the analysis of equilibrium solutions and their bifurcations to the more global study of non-linear phenomena, like chaos and complex dynamics. Many interactive software tools have been developed to aid in the study of dynamical systems, like DsTool [BGM92], LOCBIF [KKLN93] and AUTO [DK86]. These tools can be used to compute and visualize equilibrium points and periodic solutions of dynamical systems.
The occurrence of non-linear phenomena, like chaos, in a dynamical system can often be detected by studying the `geometric layout' of its basins of attraction. These regions consist of all points whose evolution ends in a specific attractor. The dynamic information hidden in this geometric layout is often revealed, at least partially, by studying the invariant manifolds of the system. This observation illustrates the necessity to have fast algorithms available for the computation of these invariant manifolds. Existing tools, like those mentioned above, often have no, or only a limited, capability for performing such computations. Active research on extending these methods is carried out by several groups, as we indicate in the next section.
Although all these approaches widen the range of systems that can be successfully studied with the help of a computer, each of them has its limitations. In some cases the invariant manifold has to be of a special type (like a circle or a torus), or the dynamics on or near the invariant manifold should be of a special type (e.g. quasi periodic or normally attracting). For some methods the convergence of the numerical procedures has not been proven, or only under rather restrictive conditions. These limitations reveal the necessity of developing a general numerical algorithm, whose convergence can be established theoretically and checked computationally.
The central geometric concept is the graph transform, a contraction operator whose fixed point is the invariant manifold one wishes to compute. This operator is defined on an infinite dimensional complete metric space. One of the problems is to construct a suitable finite dimensional approximation of the domain of the graph transform. This has been achieved in [HOV95], where a simple, efficient algorithm is presented for the computation of the stable and unstable manifolds of a hyperbolic fixed point. In [BOV96] a general algorithm is presented for the computation of normally-hyperbolic invariant manifolds, especially suitable for discrete systems depending on a continuation parameter. The rigorous mathematical analysis yields a general proof for the convergence of the numerical algorithms in both papers, as has been shown in several case studies.
As mentioned above, a first approach is based on geometric ideas, that are already present in the early literature on invariant manifolds of fixed points. The most important problems have to do with numerical performance, and with efficiency of the algorithms with regard to both computation time and memory usage. These have to be solved in a satisfactory way, before the methods developed so far can be turned into sufficiently flexible and efficient general purpose algorithms.
A second approach is to start from the conditions expressing the invariance of the manifold. This idea, that has already been explored in special cases, seems competitive with our earlier work as far as computation time is concerned. We plan to transform this idea into a general mathematical framework, that can serve as a foundation for the development of efficient algorithms, whose convergence can be established theoretically and checked computationally.
Furthermore, general methods for the computation of invariant manifolds of continuous systems are still lacking. We plan to extend our algorithms in this direction. We also propose to develop methods for the computation of global invariant manifolds. It seems that new ideas, both from a mathematical and a computational point of view, need to be developed. Finally, the development of flexible visualization methods is an important part of the current project.
Below we describe some of these problems and goals in more detail.
Another approach to the discretization problem would be to start from the conditions expressing the invariance of the manifold. A suitably discretized version of these equations can subsequently be solved (cf [DLR91, DL95] for a similar approach in a restricted setting). It is conceivable that the problem can be `lifted' to the computation of a hyperbolic fixed point of a derived system on the space of splines approximating the invariant manifold. In this setting the methods of [HOV95] can be used to compute the normally hyperbolic manifold and its invariant manifolds, thereby offering an alternative to the approach in [BOV96]. Compare [PT93], Appendix 1, where a similar approach yields the existence of invariant foliations.
[BOV96] H.W. Broer, H.M. Osinga, and G. Vegter. On the computation of normally hyperbolic invariant manifolds. In H.W. Broer, S.A. van Gils, I. Hoveijn, and F. Takens, editors, Progress in Nonlinear Di erential Equations and Their Applications, volume 19, pages 423-447. Birkhauser Verlag, Basel / Switzerland, 1996.
[Bri93] E. Brisson. Representing geometric structures in d dimensions: topology and order. Discrete Comput. Geom., 9:387-426, 1993.
[DB94] L. Dieci and G. Bader. Solution of the systems associated with invariant tori approximation II: multigrid methods. SIAM J. Sci. Comput., 15(6):1375-1400, 1994.
[DK86] E.J. Doedel and J.P. Kernevez. AUTO: Software for continuation and bifurcation problems in ordinary differential equations. Technical report, California Institute of Technology, Pasadena, 1986. Applied Mathematics Report.
[DL95] Luca Dieci and Jens Lorenz. Computation of invariant tori by the method of characteristics. SIAM J. Numer. Anal., 32(5):1436-1474, 1995.
[DLR91] Luca Dieci, Jens Lorenz, and Robert D. Russell. Numerical calculation of invariant tori. SIAM J. Sci. Stat. Comput., 12(3):607-647, 1991.
[Ede94] H. Edelsbrunner. Modeling with simplicial complexes: Topology, geometry, and algorithms. In Proc. 6th Canad. Conf. Comput. Geom., pages 36-44, 1994.
[Far93] G. Farin. Curves and surfaces for Computer Aided Geometric Design. Academic Press, Boston, 1993.
[FD91] M.J. Friedman and E.J. Doedel. Numerical computation and continuation of invariant manifolds connecting fixed points. SIAM J. Numer. Anal., 28(3):789-808, 1991.
[GS85] L. J. Guibas and J. Stol . Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph., 4:74-123, 1985.
[Guc95] J. Guckenheimer. Phase portraits of planar vector fields: computer proofs. Experimental Mathematics, 4:153-165, 1995.
[Had01] J. Hadamard. Sur l'iteration et les solutions asymptotiques des equations differentielles. Bull. Soc. Math. France, 29:224-228, 1901.
[Hob93] D. Hobson. An efficient method for computing invariant manifolds of planar maps. J. Comput. Phys., 104(1):14-22, 1993.
[HOV95] A.J. Homburg, H.M. Osinga, and G. Vegter. On the computation of invariant manifolds of fixed points. Z. angew. Math. Phys., 46:171-187, 1995.
[HPS77] M.W. Hirsch, C. Pugh, and M. Shub. Invariant Manifolds, volume 583 of Lecture Notes in Mathematics. Springer, 1977.
[KKLN93] A.I. Khibnik, Yu.A. Kuznetsov, V.V. Levitin, and E.N. Nikolaev. Continuation techniques and interactive software for bifurcation analysis of ODE's and iterated maps. Physica D, 62:360-371, 1993.
[Ma83] M. Mantyla. Computational topology: A study of topological manipulations and interrogations in computer graphics and geometric modeling. Acta Polytechnica Scand., 37:1-49, 1983.
[MK94] F. Ma and T. Kupper. Numerical calculation of invariant manifolds for maps. J. Num. Lin. Alg. Appl., 1(2):141-150, 1994.
[NY89] H.E. Nusse and J.A. Yorke. A procedure for finding numerical trajectories on chaotic saddles. Physica D, 36:137-156, 1989.
[Per29] O. Perron. Uber stabilitat und asymptotisches Verhalten der Losungen eines Systemes endlicher Di erenzengleichungen. J. Reine Angew. Math., 161:41-46, 1929.
[PT93] J. Palis and F. Takens. Hyperbolicity & Sensitive Chaotic Dynamics at Homoclinic Bifurcations, volume 35 of Cambridge studies in advanced mathematics. Cambridge University Press, 1993.
[vV87] M. van Veldhuizen. A new algorithm for the numerical approximation of an invariant curve. SIAM Sci. Stat. Comp., 8:951-962, 1987.
[vV88] M. van Veldhuizen. Convergence results for invariant curve algorithms. Math. Comp., 51(184):677-697, 1988.