		Global Manifolds 1D
		===================

Global Manifolds 1D is a software package written by James England and
Hinke Osinga for the computation of one-dimensional stable or unstable
manifolds of discrete dynamical systems. 

This version, version 2, is an extension of the Global Manifolds 1D
software written by Hinke Osinga. If you already have the Global
Manifolds 1D package you should follow the instructions below how to
upgrade to version 2. 

======================================================================


The Global Manifolds 1D software package can be used with the software
package DsTool, developed at the Center for Applied Mathematics,
Cornell University. In order to use it, you should first download and
install the Tcl/Tk version of DsTool. 

DsTool can be obtained via anonymous ftp from

	ftp://cam.cornell.edu/pub/dstool/Version_tk

Alternatively, you can download the version which incorporates this
Global Manifolds 1D software package via

        http://www.enm.bris.ac.uk/staff/hinke/dss/ode/dstool.html

If you already have DsTool, or prefer to install the version from
Cornell, please follow the instructions below.


======================================================================


Instructions for upgrading the Global Manifolds 1D code
=======================================================

If you already have the Global Manifolds 1D software package, then you
can ugrade as follows: 

1) You installed the package in your $MY_DSTOOL directory:

   * Unpack gm1d_version2.tgz in your $MY_DSTOOL directory:

	    tar xvfz gm1d_version2.tgz

     All files in the directory $MY_DSTOOL/Man1D will be replaced by
     the new files. Note that there are four more files, namely

		 man1d_noinv_acc.c
		 man1d_noinv_build.c
		 man1d_help.txt
		 help_man1d.tk

   * The files $MY_DSTOOL/Man1D/man1d.tk and
     $MY_DSTOOL/Man1D/help_man1d.tk should move to 

	         $MY_DSTOOL/tcl/man1d.tk
	         $MY_DSTOOL/tcl/help_man1d.tk

     (overwrite the file man1d.tk already there)

   * You need to edit the Makefile in $MY_DSTOOL/tcl/ in order to let
     DsTool know about the file help_man1d.tk. In
     $MY_DSTOOL/tcl/Makefile, fill out: 
 
        TK_SRCS = man1d.tk help_man1d.tk
 
   * run "make all" in the $MY_DSTOOL directory.


2) The package is installed in the $DSTOOL directory (i.e. you did not
   install it yourself, or else you do not need to read these
   instructions). If you have writing permission in the $DSTOOL
   directory, then you can upgrade the Global Manifolds 1D package
   yourself, otherwise, you should ask your system administrator.

   * Unpack gm1d_version2.tgz in the directory $DSTOOL/src:

	    tar xvfz gm1d_version2.tgz

     The upgraded version is in the directory $DSTOOL/src/Man1D/. This
     directory must replace the directory $DSTOOL/src/man1d:

	    rm -r $DSTOOL/src/man1d
	    mv $DSTOOL/src/Man1D $DSTOOL/src/man1d

     Note that there are four more files, namely

		 man1d_noinv_acc.c
		 man1d_noinv_build.c
		 man1d_help.txt
		 help_man1d.tk

   * The files $DSTOOL/src/man1d/man1d.tk and
     $DSTOOL/src/man1d/help_man1d.tk should move to 

	         $DSTOOL/tcl/man1d.tk
	         $DSTOOL/tcl/help_man1d.tk

     (overwrite the file man1d.tk already there)

   * In $DSTOOL/tcl/Makefile, add the file 

	help_man1d.tk

     to TK_SRCS.
 
   * run "make World" in the $DSTOOL directory.


======================================================================


Instructions for adding the Global Manifolds 1D code to DsTool
==============================================================

Table of Contents:

I.    Motivation
II.   Adding the Global Manifolds 1D code to DsTool
    A.  How to start 
    B.  Linking the Global Manifolds 1D code to DsTool 
    C.  Linking man1d.tk to Tcl/Tk 
III.  Explanation of the parameters
IV.   Useful remarks




I. Motivation
-------------

DsTool offers the possibility to compute fixed points of a map and
their one-dimensional stable and unstable manifolds. The user
specifies how many points DsTool chooses along the eigendirection,
close to the fixed point, and DsTool computes the orbits of all these
points. This is a simple way to compute a stable or unstable manifold
for a map.

It would be nicer to have the points ordered (and hence plotted)
according to the arclength distance to the fixed point, i.e. similar
to the manifold for a vector field. Moreover, an equally accurate
solution can be found using much less points. The Global Manifolds 1D
code grows the manifolds by arclength distance to the fixed point, and
distributes the points according to the local curvature of the
manifolds. Furthermore, it offers the possibility to compute only one
side of the manifold.

This new upgraded version of the Global Manifolds 1D software package
is capable of computing one-dimensional stable manifolds of
two-dimensional discrete systems without requiring explicit or
approximate knowledge of the inverse map. The computations are done
using forward iterates only, so numerical inaccuracies due to
approximating the Jacobian matrix or using Newton's method are
avoided.  


II.   Adding the Global Manifolds 1D code to DsTool
---------------------------------------------------

Custom analysis code may be added to DsTool on a model-by-model basis
or on a general purpose basis. The Global Manifolds 1D code works for
maps only, and gives a message when it is used on a vector field. This
text describes how to install the Global Manifold 1D code on a general
purpose basis. If you prefer to have it on a model-by-model basis,
check the README file in the $DSTOOL/my_dstool directory.

II.A. How to start
------------------
 
When downloading the Global Manifolds 1D code, you got a tar-file
named gm1d_version2.tgz. Unpack gm1d_version2.tgz in your
$MY_DSTOOL directory:

	   tar xvfz gm1d_version2.tgz

A subdirectory is created called Man1D. The files in Man1D are:

	COPYRIGHT
	Makefile
	README
	man1d.h
	man1d.tk
	help_man1d.tk
	man1d_acc.c
	man1d_build.c
	man1d_compute.c
	man1d_funct.c
	man1d_funct.h
	man1d_install.c
	man1d_linear.c
	man1d_list.c
	man1d_list.h
	man1d_load.c
	man1d_noinv_acc.c
	man1d_noinv_build.c
	man1d_help.txt

The files man1d.tk and help_man1d.tk contain procedures called by
tcl_script. Both files must be moved to the directory $MY_DSTOOL/tcl/. 

The file man1d_linear.c uses an include file from DsTool that is not
in the $DSTOOL/include directory; on line 15 of man1d_linear.c:  

	#include "$DSTOOL/src/fixed/fixed_local.h

Unfortunately, the compiler does not recognize the alias $DSTOOL, so
that you have to replace $DSTOOL with its full address.


II.B. Linking the Global Manifolds 1D code to DsTool
----------------------------------------------------

The files in $MY_DSTOOL/Man1D compile into the library lib1dman.a when
you type "make" in this directory. DsTool can use this library when it
knows where to find it. The idea is to have a (permanent) new option
in the Panels list that, when chosen, causes a window to pop up for
the Global Manifolds 1D code for maps.

1) In order for DsTool to know of the existence of lib1dman.a, fill
   out in $MY_DSTOOL/Makefile: 
 
        SUBDIRS = tcl Man1D

   and

        USER_LIBS = Man1D/lib1dman.a
 
   Once you are done (after II.C.), you can also use the command "make
   all" in $MY_DSTOOL, which first creates the library lib1dman.a and
   then compiles your personal version of DsTool. Note that if you
   prefer a different name, say MY_NAME, for the directory Man1D, you
   should replace Man1D with MY_NAME in $MY_DSTOOL/Makefile, and also
   in $MY_DSTOOL/MY_NAME/Makefile.
 
2) Edit the file $MY_DSTOOL/user.c to include the installation
   procedure for the Global Manifold 1D code. The appropriate lines in
   user.c should look something like:

	/* ------------------------------------------------------
 	 *
 	 * INCLUDE USER COMPUTATIONAL MODULES HERE
 	 *
 	 * ------------------------------------------------------
	 */
 
	extern void man1d_install();
	 
	typedef void (*PFV)();
	 
	PFV user_install_procs[] = {
	   man1d_install,
	  (PFV) NULL
	};

   Be sure not to remove the "(PFV) NULL" entry.  DsTool uses this to signal 
   the end of the array.  The procedures in user_install_procs will be called
   when your custom version of DsTool starts up, installing the Global
   Manifold 1D code once and for all.


II.C. Linking man1d.tk to Tcl/Tk 
--------------------------------

When executing DsTool a new menu entry should appear in the Panels
list. This is done by using tcl_script.

1) You need to edit the Makefile in $MY_DSTOOL/tcl/ in order to let DsTool 
   know about the man1d.tk file. In $MY_DSTOOL/tcl/Makefile, fill out:
 
        TK_SRCS = man1d.tk help_man1d.tk
 

2) Edit the file $MY_DSTOOL/tcl/my_app_init.tcl to make the menu option 
   appear.  This should look something like:

	proc my_app_init {} {
	    global COLOR FONT EXT
 
	    # Add changes to colors and fonts here

	    window(open) cmd

	    # Add new panel items here
    	    cmd(add_to_panels) "" ""
            cmd(add_to_panels) "One-D Manifolds... Discrete" \
		"window(open) man1d"
	}

   This will cause a new option to appear in the Panels list. The
   option "One-D Manifolds... Discrete" is separated from the other 
   options by a horizontal line (cmd(add_to_panels) "" ""). If you
   choose the new option, the command "window(open) man1d" is
   executed, which opens the window "man1d". Note that these commands
   must go after the line "window(open) cmd", since you are changing
   entries in the Command window. 

3) Recompile your personal version of DsTool with the command "make
   all" and see if it works!


III. Explanation of the parameters
----------------------------------

When you run DsTool and choose the "One-D Manifolds... Discrete"
option in the Panels list, a window pops up that allows you to compute
one-dimensional stable and unstable manifolds for maps by using the
technique of Bernd Krauskopf and Hinke Osinga, described in

   "Growing 1D and quasi 2D unstable manifolds of maps",
   Journal of Computational Physics 146(1): 404-419, 1998.

and

   "Investigating torus bifurcations in the forced Van der Pol
   oscillator", 
   in E.J. Doedel and L.S. Tuckerman (Eds.) "Numerical Methods for
   Bifurcation Problems and Large-Scale Dynamical Systems," 
   IMA Vol. Math. Appl. 119, pp. 199-208, Springer-Verlag 2000.

Version 2 of the Global Manifold 1D code also allows you to compute
the stable manifold using the Search Circle algorithm of James
England, Bernd Krauskopf and Hinke Osinga. The algorithm only works
for two-dimensional maps and does not use the inverse. The method is
described in   

   J.P. England, B. Krauskopf and H.M. Osinga,
   "Computing one-dimensional stable manifolds of planar maps without
    the inverse",
   Bristol Centre for Applied Nonlinear Mathematics 
   preprint #2003.02, April 2003
   (http://www.enm.bris.ac.uk/anm/preprints/2003r02.html).

In the above papers you can find a detailed explanation of how the
algorithms work. However, in order to make this README file
self-contained, this section should give you some idea what the
parameters stand for.

1) The Global Manifold 1D code gives you the option to compute either
   "both sides," the "positive side," or the "negative side" of the
   manifolds. Which side is positive or negative depends on how DsTool
   computes the corresponding eigenvector of the fixed point. 

2) The algorithm starts with a point on the respective eigendirection. 
   The initial step is specified in the next column

	               initial step: 0.001
	  arclength stable manifold: 10
	arclength unstable manifold: 10

   By default, the first point is found at distance 0.001 of the fixed
   point. You can think of this point as being the last point of a
   fundamental domain for one side of the manifold. The algorithm adds
   points to a list of points that approximate the manifold, until the
   specified arclength (10 is the default) is exceeded. The length of
   the computed arclength, which is then slightly larger than what you
   specified, is reported in a message.

   You can now compute the stable and unstable manifolds separately by 
   clicking on the appropriate button. Hence, in order to compute only
   one manifold, you no longer need to set the arclength of the other
   manifold to zero.

3) The parameters for the accuracy of the approximation are specified 
   in the next column:

		alpha_min: 0.20000000000000001
	        alpha_max: 0.29999999999999999
	(Delta alpha)_min: 9.9999999999999995e-07
	(Delta alpha)_max: 1.0000000000000001e-05
	        Delta_min: 0.0001
		  epsilon: 0.20000000000000001
	      convergence: 1e-08

   In fact, the numbers were meant to be alpha_min = 0.2, alpha_max =
   0.3, (Delta alpha)_min = 10^-6, (Delta alpha)_max = 10^-5,
   Delta_min = 10^-4, epsilon = 0.2, and convergence = 10^-8. The
   round-offs are shown so that you see how DsTool treats these
   numbers. 

   The accuracy constraints are primarily controlled by alpha_min,
   alpha_max, (Delta alpha)_min, and (Delta alpha)_max. The parameters
   epsilon and convergence are discussed below.

   The parameter alpha denotes an approximation of the angle between
   the lines given by three successive points. If the angle is very
   small, the three points almost lie on a straight line. On the other
   hand, if the angle is large, the three points should be thought of
   as being on a sharp fold, and more points are needed to approximate
   the manifold properly. Recall that the parameter Delta is the
   distance between two successive points. The value (Delta alpha)
   denotes the product of the distance between the last two points and
   the angle between the last three points. The algorithm checks
   whether   

	        alpha_min <    alpha    < alpha_max,
	(Delta alpha)_min < Delta alpha < (Delta alpha)_max.

   A point at distance Delta from the last point with alpha <
   alpha_max such that (Delta alpha) < (Delta alpha)_max, is accepted
   as being accurate enough. If also alpha < alpha_min and 
   (Delta alpha) < (Delta alpha)_min, then the next point is searched
   at distance 2 * Delta from the last point, because the computation
   was extremely accurate, i.e. more accurate than specified by the
   user. 

   If the manifold folds sharply, it may happen that the algorithm
   tries to find a point at distance Delta from the last one, with
   Delta approximately 0. It is desirable to force the algorithm to
   accept a point when Delta is smaller than Delta_min even though the
   accuracy constraints are violated, so that the computation time is 
   bounded. If this happens, an error message is given, showing you
   exactly what accuracy constraint is violated. 

   If you want to compute your manifold with higher accuracy, you
   typically decrease the initial step, the parameter Delta_min and
   the choices for (Delta alpha)_min and (Delta alpha)_max. The values
   for alpha_min and alpha_max have less effect. 

4) If the manifold converges to a fixed point, it may have a shorter 
   arclength than what you specified. The parameter convergence is
   used to detect this. The algorithm stops when two successive point
   on the manifold are only convergence (10^-8 is the default) away
   from each other, and prints the length of the computed arclength.
   Note that convergence must always be smaller than Delta_min. 

   The parameter epsilon is only used in the algorithm for computing
   the unstable manifold and for computing the stable manifold as the
   unstable manifold of the inverse map. That is, it is ignored if the
   "Way to calculate the stable manifold" is set to "Search Circle"
   and only has meaning with the "Explicit/Approx Inverse" or "Monte
   Carlo" method; see below for more details on these methods. The
   algorithm produces a sequence of points on the manifold that are
   roughly distance Delta away from each other, where Delta varies
   according to the curvature of the manifold. Since it is
   computationally expensive to find points at exactly distance Delta,
   points are accepted when the distance to the last point is in the
   interval  

	[(1 - epsilon) * Delta, (1 + epsilon) * Delta].

   The choice for Delta is automatically generated each time by the
   algorithm.

5) New to version 2 of the Global Manifold 1D code is the ability
   to select which method is used to compute the stable manifold. A
   drop-down box allows you to choose the preferred method. The options
   are "Explicit/Approximate Inverse", "Monte Carlo" or "Search Circle".
   If either of the first two options are chosen, then the stable
   manifold will be computed as the unstable manifold of the inverse
   map. The option "Explicit/Approximate Inverse" uses the inverse
   specified in the file that defines the model. If only an
   approximate inverse is specified, then this will be used as a seed
   for Newton's method. The option "Explicit/Approximate Inverse" will
   not appear in the drop-down menu if no explicit or approximate
   inverse is defined. The option "Monte Carlo" forces the algorithm
   to use random seeds for Newton's method in order to find the
   inverse, even if an inverse is specified in the model definition.

   The option "Search Circle" only appears when the map is
   two-dimensional. The method has not yet been implemented for higher 
   dimensions. If the option "Search Circle" is selected, then two
   extra parameters need to be taken into account:

   	bisection error:   9.9999999999995e-07
    	iteration max  :   1

   The Search Circle algorithm works be finding new points that map
   back onto a previously computed segment of manifold. The bisection
   error is the maximum distance that an image of the next point found
   can be away from a segment on the previously computed manifold. The
   global accuracy of the computation will not be affected by this
   bisection error if it is of the same order as the interpolation
   error. As a rule of thumb, we choose it of a similar order as 
   (Delta alpha)_max.

   The parameter iteration max is only relevant if the system does not
   have a unique inverse. For noninvertible maps the next point on a
   branch of the manifold may map to the other branch of the manifold,
   which has not been computed yet. This problem can be overcome by
   trying a higher iterate of the map; this is a similar trick as is
   used when the eigenvalue corresponding to the manifold is negative.
   The parameter iteration max specifies the maximum number of 
   iterations that are tried to find a point that maps onto the
   computed manifold. Note that iteration max refers to iterates of
   the map as defined in the model file. That is, if you are using the
   second iterate already, because the eigenvalue is negative, then a
   warning will be printed, but iteration max remains equal to 1. In
   this situation, for iteration max to have any effect, you need to
   change it to at least 3. If the eigenvalue is positive, then
   setting iteration max to 2 will already have an effect. 

6) The stable manifold in noninvertible systems may consist of several
   (sometimes infinitely many) disjoint branches. The Search Circle
   algorithm can compute such a disjoint branch if one point on it is
   known. This point must be saved in the DsTool `Selected' window and
   the "Try to extend manifold from selected point?" must be set to
   "Yes." 

   Typical first points on a disjoint branch are pre-images of the
   fixed point. These can be found by computing the backward orbit of
   the fixed point using Newton's method for finding the inverse and
   Monte Carlo points as seeds. This step must be done by hand.


IV. Useful remarks
---------------------

The Global Manifold 1D code should work for any map with
one-dimensional stable or unstable manifolds. The following remarks may 
help to enjoy the code.

1) The manifolds are saved in the same format as if they were
   computed with the original manifold computation of DsTool. This
   means that you can clear them by pressing "Clear manifolds" in
   either the Global Manifold 1D window, or in the Fixed Point window. 

2) As is also done in the original manifold computation of DsTool,
   Global Manifolds 1D computes each branch of the manifolds entirely
   before it is saved. Saving points may take a long time when a
   branch consists of a lot of points. 

3) DsTool does not draw lines between successive points on the
   manifold (not even for the manifold of a vector field). However,
   you can port the manifolds to Geomview (for two-dimensional systems
   just take "0" for the z-coordinate) and choose to connect the dots
   before sending them. 

4) It is possible that the Global Manifold 1D code tries to find a
   pre-image in an interval whose image gets stretched so much that
   even points that differ only in the last digit get mapped too far
   apart. When this happens, the computation stops and an error
   message is given: 

      Preimages are equal, yet no point found
      ERROR: manifold stretches too much!

   This typically happens for unbounded manifolds at a long arclength
   distance away from the fixed point. 

5) The Global Manifold 1D code is not well designed for a PERIODIC
   phase space. If the code does not behave properly, it is best to
   change the manifold type in the model definition to EUCLIDEAN and
   define auxiliary functions to divide out the periodicity. The
   manifolds will then be computed in the covering space, but can be
   projected to the proper phase space using these auxiliary functions
   as the variables.



