Algorithms for Invariant Manifolds: numerical and computational issues.


 
 

Synopsis of the project

Ongoing joint research in the dynamical systems and geometric computing groups at the Department of Mathematics and Computing Science, University of Groningen, concerns the computation and visualization of invariant manifolds in dynamical systems. Recent results are based on constructive geometric ideas like the graph transform, that are already present in the early literature on (un)stable manifolds of fixed points. The most important problems have to do with numerical performance and efficiency of the algorithms and geometric data structures with regard to both computation time and memory usage. Central topics in our research program are:

 

Description of the project

Background

The introduction of computers into the professional activities of scientists has triggered a large scale interest in the development of new scientific methods. New disciplines, like Computer Algebra and Scientific Computing, have expanded at a high pace during the last decade, and even found their way into curricula of many American and, more recently, European universities.

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.

Related work

A project, dealing with the development of software for continuation methods and bifurcation analysis, is carried out at the CWI in Amsterdam, see e.g. [KKLN93]. Other recent publications deal with the development of new numerical methods for the computation of invariant manifolds, see e.g. [DB94, DLR91, DL95, FD91, Hob93, MK94, NY89, vV87, vV88]. These new algorithms are no longer limited to the computation of invariant manifolds of equilibrium or periodic solutions. The scope is widened to the computation of normally hyperbolic invariant manifolds, which, in a certain sense, can be considered as higher dimensional counterparts of equilibrium points or periodic solutions.

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.

Related work in Groningen

During the past few years research by Broer, Osinga and Vegter has been focused on the development of a general algorithm for the computation of invariant manifolds. This work is based on geometric ideas that already exist in the work of Hadamard [Had01] and Perron [Per29] on the existence of invariant manifolds of hyperbolic fixed points, and the more general theory of normally hyperbolic invariant manifolds by Hirsch, Pugh and Shub [HPS77].

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.

Problems and goals

With regard to the computation of invariant manifolds there are two main approaches.

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.

Computational issues (data structures).

In our earlier work we were faced with the problem of approximating and representing the invariant manifolds in terms of  flexible data structures. In finite element analysis, grids are used to decompose surfaces to facilitate numerical analysis through approximation. The grid-cells are usually of a fixed type (like cubes), and constitute a regular packing. These structured grids are not very suitable for adaptive methods that require automatic refinement during the execution of a numerical algorithm. Our experience in computing invariant manifolds has made clear that such adaptive grids are crucial ingredients of high-speed and memory- saving algorithms. Especially in higher dimensions these problems are non-trivial, and their solution will involve the development of unstructured grids. The data structures presented in e.g. [Bri93, Ede94, GS85, Ma83] seem promising for the representation and manipulation of non-linear manifolds, based on simplicial complexes with special properties. They also seem suitable for the development of smooth approximation schemes, although it is not yet completely clear how to fine-tune them to the dynamical applications we have in mind.

Numerical issues (discretization).

The current implementation of the algorithms in [BOV96] use a linear approximation scheme, that currently only works for invariant manifolds of dimensions one and two. For 2D manifolds the algorithm computes a collection of triangles forming a piecewise linear simplicial (C-0 ) approximation. Yet the algorithm is sufficiently powerful to compute the tangent spaces at the vertices of these triangles as well. Therefore it seems possible to upgrade the method, so that it will compute a C-1 approximation, based on piecewise, low degree polynomial parametrizations (like splines). See e.g. [Far93] and reference therein. The geometric roots of our methods provide a starting point for an analysis of the numerical performance, both theoretically and experimentally. Since there are no off-the-shelf methods yet, further research in this direction is indispensable.

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.

Extension to continuous systems.

The methods developed in [HOV95] and [BOV96] only work in full generality for discrete dynamical systems. We have not yet succeeded in extending these methods to continuous systems. Boldly approximating the continuous system by its time-T-map, for some suitable T, turns out not to work. If T is too small, this map is too close to the identity map, which is not normally hyperbolic at all. On the other hand, one cannot take T arbitrarily large either, due to the build-up of numerical errors. Especially if the invariant manifold is of saddle type long term numerical integration is not robust. Further research in this direction is planned.

Globalization.

As has been said before, the quantitative study of nonlinear phenomena like homoclinic or heteroclinic chaos requires the computation of global stable and unstable manifolds of hyperbolic fixed points. Currently there are only special purpose methods for a limited class of low-dimensional problems. Obviously, algorithms like the one presented in [HOV95] can compute these global objects by forward or backward iteration of local invariant manifolds, but the numerical output is unreliable, regardless of the precision of the computations. The ideas described in e.g. [Guc95] seem to be a good starting point for research in this direction.

Visualization.

Finally, one of the goals is to develop suitable methods for the visualization of invariant manifolds. An implementation of these methods should provide a back-end to the algorithms that compute the invariant manifolds. This visualization software should be sufficiently exible to aid in the experimental study of non-linear phenomena in dynamical systems, possibly by integrating this software with existing packages like DsTool or LOCBIF.


 

References

[BGM92] A. Back, J. Guckenheimer, M.R. Myers, F.J. Wicklin, and P.A. Worfolk. DsTool: Computer assisted exploration of dynamical systems. Notices Amer. Math. Soc., 39(4):303-309, 1992.

[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.