Next Previous Contents

9. Compute Engines

The following sections describe the usage of modules which may be utilized to extend bifurcation diagrams through the use of parameter continuation algorithms. These modules communicate with VBM through an interface described in Section.

All compute engines used within VBM utilize a single, coherent, interface. The actual details of the implementation are hidden, and, hence, the user does not need to learn the specifics of controlling the underlying algorithm. They only need to learn the VBM interface, and they are then able to use any algorithm which has been implemented as a compute engine.

This is the control panel for all compute engines in VBM.

This interface may be in four different states. The first state, namely the Off state, is simply when no work has yet been done in the process of creating the compute module. In general, its code has not yet been fully compiled. The compute engine is in this state before the dialog shown in Figure is created, and is never in this state while that dialog exists.

The Idle state is when enough is known about the problem to do some preliminary setup. For example, the equations of interest have been made available, so they may be compiled into an executable. In this state the "Start", "Setup", and "Quit" buttons are active. The "Quit" button kills the compute engine, returning it to the Off state. The "Setup" button allows the user to modify the parameters of the compute engine. What parameters are included in the dialog presented by this button are totally under the control of the compute engine, and differs from one compute engine to the next. Please see the documentation for the individual compute engine for more information. The "Start" button brings up a dialog (shown in Figure) which can be used to move the compute engine into the Active state.

This panel is used to start a new continuation calculation.

For each dimension of the continuation there will be a row with a "Parameter" label and a "Direction" label (e.g. for a two dimensional continuation, which creates a surface, there will be two rows). The "Parameter" typein is used to select which column of the VBM file to continue in, and the direction typein is used to tell the compute engine the direction in which to perform the continuation. Note that the "Parameter" typein is read-only and that you must use the small button to the right of the widget to select valid values. The actual interpretation of these values is up to the compute engine. For example, not all columns of the VBM file are valid for computation, and only those that are valid for the given compute engine will be displayed in the "Parameter" widget. The "Direction" value may be interpreted in several different ways depending on the compute engine. For example, there are compute engines which only look at the sign of this value and increase the parameter value if it is positive and decrease it if is negative. On the other hand there are modules which look at the sign of this value and continue going in the same direction if it is positive and go in the opposite direction if it is negative, regardless of whether the parameter is increasing or decreasing. Please see the individual compute engine documentation for more information.

The module achieves the Active state when the continuation problem has been fully defined. At this point a starting point has been chosen and the algebraic non-linear equations are fixed (e.g. a discretization has been chosen). In the Active state the "Extend" and "Reset" button are active. The "Reset" button simply returns the compute engine to the active state. Normally when the compute engine is reset some amount of information is discarded (e.g. for example the current computation direction). It is rarely the case that a "Start" followed by an "Extend" has the same effect as a "Start", followed by a "Reset", followed by a second "Start". The "Extend" button brings up the dialog in Figure.

This panel is used to extend an already started continuation calculation.

For each of the parameters selected in Figure, this dialog will have a row in which the user can enter a number of additional steps to compute. Note, the interpretation of this number of steps if up to the compute engine. For example, some compute engines may actually give more or less steps than requested.

All VBM compute engines are defined by using a data block in the VBM file with the tag VBM_Compute_module. Below is an example of such a data block.


##Begin VBM_Compute_Module 
lcvmsun1.epfl.ch lcvmsun2.epfl.ch
./r.strut
./strut_ivp.f
./work
VBM_1D_remote_AUTO
Continuation with IVP solver
##End

The first line of the block is either a list of computers on which to run the compute engine or "NULL". If this entry is "NULL" the compute engine may run on any machine on which it is able (in almost all cases this will be the same machine on which VBM is running). If it is a list of machine names then the compute engine may run on any or all of the listed machines. The second line is the name of the file to use for the "computational parameters". The third line is the name of the file to use for the "problem definition". The exact interpretation of each of the above three lines is strongly dependent on the specific compute engine you are using. Please see the documentation for the compute engines for more information. The fourth line is the name of a directory in which the compute engine may store temporary files. If this line is "NULL" then the compute engine will create a temporary directory itself. The fifth line is the name of the compute engine you wish to use, and the sixth line is a short description of what the compute engine does. The user may put anything in this line they like, and it is what will appear in the compute engine selection dialog in VBM.

9.1 VBM_1D_AUTO

The VBM_1D_AUTO module is a VBM compute engine based on AUTO94 by Doedel, et. al.. AUTO is a large program, written in Fortran, which implements parameter continuation methods for solving problems in ordinary differential equations. It has proven useful in our work, and we have no desire to reinvent the functionality that it provides. Our desire, then, is to take AUTO and use it within VBM with as little modification as possible. Note, the newest version of AUTO is AUTO97. This module has been modified to work with AUTO97, but this interface has not been tested. For general usage we recommend that AUTO94 be used with the current version of VBM.

On the other hand, if you are an AUTO and/or Python expert you are welcome to give AUTO97 a try! If there are any problems a good place to look would be python_script/continuation_modules/Parse8.py, since this is the Python object which parses the AUTO fort.8 files. We would appreciate feedback on any modifications you find necessary.

The main hurdle that we must overcome is to make AUTO94 function within the compute engine framework. Fortunately, Python makes this procedure quite straight forward. A small Python program may be written which acts as an adapter, changing AUTO's native interface into the interface defined for VBM compute engines. Basically, there are two ways in which one may proceed. First, AUTO may be called directly from Python. Second, AUTO may be run as a separate process and communicate with VBM using standard inter-process communication protocols. We have chosen the second method because, even though it is somewhat slower, it is more portable than the first method. In simple terms, Python can only call C or C++ directly and calling Fortran from either of these languages is notoriously difficult to do, in a portable way. We also note that, for most applications, the added cost of the inter-process communication is negligible compared to the amount of time AUTO spends performing its computations.

Whenever this module is used some number of columns in the bifurcation diagram must be reserved to represent the values of the equations at some fixed point, usually one end-point. This module then uses these values to reconstruct an initial guess, using an initial value problem solver, so that it may start its continuation procedure.

A postscript version of the AUTO 94 manual is accessible at http://lcvmwww.epfl.ch/VBM/auto.ps and should be consulted for additional further information on AUTO.

In order for AUTO based compute module to run, you must have the following files in the directory you run from, where `problem' can be any word you like to describe your problem:

One important thing to note is that the problem.f file used for VBM_1D_AUTO us not exactly the same as the one used for AUTO94. VBM_1D_AUTO uses an IVP solver to start the calculation and communicates with the rest of AUTO94 through the use of the STPNT function. Normally, the STPNT function is defined in problem.f when it is used with AUTO, but it MUST BE COMMENTED OUT when you use VBM_1D_AUTO. Otherwise, VBM will not be able to use the file.

Here's a sample problem.r file followed by an explanation of what you generally need to change from run to run. Note that some of the values are automatically modified by VBM. Those values are noted below.


15 4 0 0                      NDIM,IPS,IRS,ILP
1  3                        NICP,(ICP(I),I=1 NICP)
10 4 0 2 -1 0 15 0              NTST,NCOL,IAD,ISP,ISW,IPLT,NBC,NINT
4 -20.0 5.0 -500.0 500.0     NMX,RL0,RL1,A0,A1
4 10 0 8 5 3 0             NPR,MXBF,IID,ITMX,ITNW,NWTN,JAC
1.e-6 1.e-6 1.e-6            EPSL,EPSU,EPSS
-0.001 0.00001 0.1  1             DS,DSMIN,DSMAX,IADS
0                             NTHL,(/,I,THL(I)),I=1,NTHL)
0                            NTHU,(/,I,THU(I)),I=1,NTHU)
2                            NUZR,(/,I,PAR(I)),I=1,NUZR)
3   -2.0
7    1.0

To set up the AUTO based compute module for your problem, you must create a file problem.f. The file problem.f contains two crucial subroutines which you must provide:

Associated with this compute engine are three global tags, two of which are required and one of which is optional.

The two required tags are:

AUTO_EQ

This tag defines which columns of the VBM file should be used as initial values to the IVP solver to create the required starting solution for AUTO94. It is followed by two integers which give the first and last columns (inclusive) that are used. If x is the first number and y is the second number, then they must obey the relation y-x+1=NDIM. Note, the first column is 0.

AUTO_PAR

This tag defines which columns of the VBM file should be used as parameters in the construction of the initial solution for AUTO94, using an IVP solver. It is followed by two integers which give the first and last columns (inclusive) that should be used.

The one optional tag is:

AUTO_EXTRA_DATA_REPORT

This tag defines which columns of the VBM file should be used to report values at some intermediate value of the solution. It is followed by two integers which give the first and last columns (inclusive) that should be used and a floating point number which designates the intermediate value at which to report. If x is the first number and y is the second number, then they must obey the relation y-x+1=NDIM. Note, the first column is 0.

Here is a sample vbm file.


# AUTO_EQ 0 6
# AUTO_PAR 7 26
# AUTO_EXTRA_DATA_REPORT 27 33 1.0
N1;N3;phi;m2;r1;r3;s;lambda;nu;uhat2;kappa;par4;par5;par6;par7;par8;par9;par10;par11;par12;par13;par14;par15;par16;par17;par18;par19;eN1;eN3;ephi;em2;er1;er3;es
34
0 1
1
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
##Begin VBM_Compute_Module 
NULL
./r.strut
./strut_ivp.f
./work
VBM_1D_AUTO
Continuation with IVP solver
##End

For this module the first line of the "VBM_Compute_Module" data block is ignored. The second line is the path to the AUTO94 problem.r file, and the third line in the path to the AUTO94 problem.f file.

In the start dialog Figure only the sign of the value entered in the "Direction" typein is used. In fact, this widget is read only and you must choose either "-1" or "1". If the direction is positive then the first step increases the parameter, and if the direction is negative then the first step decreases the parameter. In the extend dialog Figure the value entered in the "Number of Steps" typein is used for two purposes.

First, the sign of the value determines the direction of the continuation. If it is positive then continuation occurs in the same direction as the parameter increasing direction at the starting point, and if it is negative then continuation occurs in the same direction as the parameter decreasing direction at the starting point. Please see Figure for an example. Note, if the continuation procedure has passed over any folds, entering a positive value into the "Number of Steps" may actually decrease the parameter value, and entering a negative value may actually increase the parameter value.


This figure gives an example of the definition of directions in the AUTO based compute engines. "E" is a point which has been computed by a continuation starting at "S". At "S" the arrow marked with a "+" points in the direction of increasing parameter value. The definition of the continuation directions at "E" are a continuous translation, along the curve, of those at "S".

Second, the absolute value of the number in the "Number of Steps" typein is multiplied by the "NPR" value in the input defaults file and AUTO94 is asked to compute that number of steps by setting the automatically setting the "NMX" parameter.

The "Setup" dialog for this module presents a copy of the "problem.r" file which the user may edit. Note, the edits are saved internally, and are recovered from one call of the setup dialog to the next. The original "problem.r" file may always be recovered by pressing the "Reload" button on the setup dialog. The current configuration can be saved in the "problem.r" file by pressing the "Save" button, otherwise this file is not modified by the changes.

This module also uses two environment variables to define how it interacts with AUTO94. The first is VBM_1D_AUTO_HOME which must be set to the directory in which AUTO94 is installed. The second is VBM_1D_AUTO_FORTRAN_COMPILER which must be set to a command line which can be used to compile AUTO. It allows you to give any additional flags needed for your problem and compiler. The default value is f77 -O. If this is inappropriate for your system this module will fail.

9.2 VBM_1D_AUTO_FORT8

The VBM_1D_AUTO_FORT8 module is a VBM compute engine based on AUTO94 by Doedel, et. al.. AUTO is a large program, written in Fortran, which implements parameter continuation methods for solving problems in ordinary differential equations. It has proven useful in our work, and we have no desire to reinvent the functionality that it provides. Our desire, then, is to take AUTO and use it within VBM with as little modification as possible. Note, the newest version of AUTO is AUTO97. This module has been modified to work with AUTO97, but this interface has not been tested. For general usage we recommend that AUTO94 be used with the current version of VBM.

On the other hand, if you are an AUTO and/or Python expert you are welcome to give AUTO97 a try! If there are any problems a good place to look would be python_script/continuation_modules/Parse8.py, since this is the Python object which parses the AUTO fort.8 files. We would appreciate feedback on any modifications you found necessary.

The main hurdle that we must overcome is to make AUTO94 function within the compute engine framework. Fortunately, Python makes this procedure quite straight forward. A small Python program may be written which acts as an adapter, changing AUTO's native interface into the interface defined for VBM compute engines. Basically, there are two ways in which one may proceed. First, AUTO may be called directly from Python. Second, AUTO may be run as a separate process and communicate with VBM using standard inter-process communication protocols. We have chosen the second method because, even though it is somewhat slower, it is more portable than the first method. In simple terms, Python can only call C or C++ directly and calling Fortran from either of these languages is notoriously difficult to do, in a portable way. We also note that, for most applications, the added cost of the inter-process communication is negligible compared to the amount of time AUTO spends performing its computations.

VBM_1D_AUTO_FORT8 uses the tag structure to start its continuation computations. For a point of the bifurcation diagram to be a valid starting point for this compute engine, it must have the tag "AUTOFort8_file". This tag informs the compute engine of the name of a file where the full solution, as originally generated by AUTO, is stored. This solution can then be used as the starting point for further continuations.

A postscript version of the AUTO94 manual is accessible at http://lcvmwww.epfl.ch/VBM/auto.ps and should be consulted for additional further information on AUTO.

In order for AUTO based compute module to run, you must have the following files in the directory you run from, where `problem' can be any word you like to describe your problem:

The problem.f file that is used for VBM_1D_AUTO_FORT8 is exactly the same as the one used in AUTO94. No modification is necessary.

Here's a sample problem.r file followed by an explanation of what you generally need to change from run to run. Note that some of the values are automatically modified by VBM. Those values are noted below.


15 4 0 0                      NDIM,IPS,IRS,ILP
1  3                        NICP,(ICP(I),I=1 NICP)
10 4 0 2 -1 0 15 0              NTST,NCOL,IAD,ISP,ISW,IPLT,NBC,NINT
4 -20.0 5.0 -500.0 500.0     NMX,RL0,RL1,A0,A1
4 10 0 8 5 3 0             NPR,MXBF,IID,ITMX,ITNW,NWTN,JAC
1.e-6 1.e-6 1.e-6            EPSL,EPSU,EPSS
-0.001 0.00001 0.1  1             DS,DSMIN,DSMAX,IADS
0                             NTHL,(/,I,THL(I)),I=1,NTHL)
0                            NTHU,(/,I,THU(I)),I=1,NTHU)
2                            NUZR,(/,I,PAR(I)),I=1,NUZR)
3   -2.0
7    1.0

To set up the AUTO based compute module for your problem, you must create a file problem.f. The file problem.f contains three crucial subroutines which you must provide:

Associated with this compute engine are four global tags, three of which are required and one of which is optional. There is also one required pointwise tag.

The three required tags are:

AUTO_EQ

This tag defines which columns of the VBM file are used in the construction of the initial solution for AUTO94, using an IVP solver. It is followed by two integers which give the first and last columns (inclusive) that should be used. If x is the first number and y is the second number, then they must obey the relation y-x+1=NDIM. Note, the first column is 0.

AUTO_PAR

This tag defines which columns of the VBM file should be used as parameters in the construction of the initial solution for AUTO94, using an IVP solver. It is followed by two integers which give the first and last columns (inclusive) that should be used.

AUTO_BVP

This tag defines the default name for the file in which to store the full solutions from AUTO. Note, the first column is 0.

The one optional tag is:

AUTO_EXTRA_DATA_REPORT

This tag defines which columns of the VBM file should be used to report values at some intermediate value of the solution. It is followed by two integers which give the first and last columns (inclusive) that should be used and a floating point number which designates the intermediate value at which to report. If x is the first number and y is the second number, then they must obey the relation y-x+1=NDIM. Note, the first column is 0.

The required pointwise tag is:

AUTOFort8_file

This tag defines the name of the file in which the full solution, as computed by AUTO94, can be found. It has two arguments. The first is the filename (with path) in which the solutions are stored, and the second is a integer which is the label of the desired solution in the file (AUTO94 can store more than one solution in a single file). Note, if the filename already exists this module will not overwrite it. It will generate a new name by adding an integer onto the filename given here, so that the filename does not exist.

Here is a sample vbm file.


# AUTO_BVP /foo/new.fort.8
# AUTO_EQ 0 6
# AUTO_PAR 7 26
# AUTO_EXTRA_DATA_REPORT 27 33 1.0
N1;N3;phi;m2;r1;r3;s;lambda;nu;uhat2;kappa;par4;par5;par6;par7;par8;par9;par10;par11;par12;par13;par14;par15;par16;par17;par18;par19;eN1;eN3;ephi;em2;er1;er3;es
34
0 1
1
# AUTOFort8_file /foo/old.fort.8 57
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 
##Begin VBM_Compute_Module 
NULL
./r.strut
./strut_ivp.f
./work
VBM_1D_AUTO_FORT8
Continuation with IVP solver
##End

For this module the first line of the "VBM_Compute_Module" data block is ignored. The second line is the path to the AUTO94 problem.r file, and the third line in the path to the AUTO94 problem.f file.

This module has a special feature that is currently not available in other compute engines. It is able to start a calculation from an otherwise valid VBM file which contains no data (the number of branches is 0). It will use the solution in the STPNT function of the "problem.f" file as the starting point for its continuation.

In the start dialog Figure only the sign of the value entered in the "Direction" typein is used. In fact, this widget is read only and you must choose either "-1" or "1". In AUTO94 fort.8 files a tangent direction is stored based upon the manner in which the solution is computed. If the direction is positive then the first step moves in the direction of the stored tangent vector, and if the direction is negative then the first step moves in the opposite direction as the stored tangent vector.

In the extend dialog Figure the value entered in the "Number of Steps" typein is used for two purposes.

First, the sign of the value determines the direction of the continuation. If it is positive then continuation occurs in the same direction as the stored tangent vector at the previous point, and if it is negative then continuation occurs in the opposite direction of the tangent vector stored at the previous point. Please see Figure for an example.


This figure gives an example of the definition of directions in the AUTO based compute engines. "E" is a point which has been computed by a continuation starting at "S". The stored tangent at the point "S" points in the direction shown by te arrow marker with a "+". The definition of the continuation directions at "E" are a continuous translation, along the curve, of those at "S".

Second, the absolute value of the number in the "Number of Steps" typein is multiplied by the "NPR" value in the input defaults file and AUTO94 is asked to compute that number of steps by setting the automatically setting the "NMX" parameter.

The "Setup" dialog for this module presents a copy of the "problem.r" file which the user may edit. Note, the edits are saved internally, and are recovered from one call of the setup dialog to the next. The original "problem.r" file may always be recovered by pressing the "Reload" button on the setup dialog. The current configuration can be saved in the "problem.r" file by pressing the "Save" button, otherwise this file is not modified by the changes.

This module also uses two environment variables to define how it interacts with AUTO94. The first is VBM_1D_AUTO_HOME which must be set to the directory in which AUTO94 is installed. The second is VBM_1D_AUTO_FORTRAN_COMPILER which must be set to a command line which can be used to compile AUTO. It allows you give any additional flags needed for your problem and compiler. The default value is f77 -O. If this is inappropriate for your system this module will fail.

9.3 VBM_1D_to_nD_base

This is a module which takes a one parameter compute engine and uses the SPWS algorithm to create a multidimensional compute engine. Details of the SPWS algorithm can be found in the doctoral thesis of Randy Paffenroth on http://lcvmwww.epfl.ch/~redrod (Note: as of March 8th, 1999 the thesis has not yet been added to the web page). This documentation will not cover the details of the algorithm, but only how it is used within the VBM framework.

This module is an example of a layered module in that it does not do computations on its own, but forwards all the computations to some underlying one parameter compute engine, then it uses the results of the one parameter computations, within the framework of the SPWS algorithm, to create a multidimensional manifold. Those one parameter compute engines onto which this module has been layered are listed in Section.

The required tags and setup of the "VBM_Compute_Engine" data block are exactly the same for this module as they are for the underlying one dimensional module except that the name of the module is normally different. For example, if the name of the one parameter module is VBM_1D_AUTO, then the layer version is called VBM_2D_AUTO or VBM_3D_AUTO.

This compute engine returns connectivity, so it is important that the VBM file you are computing with already have a "VBM_Connectivity" data block in it before you start your computation.

9.4 VBM_remote_base

A module which takes any VBM compute engine and gives it the ability to run on a machine other than the one VBM is running on, by communicating over a socket.

This module is an example of a layered module in that it does not do computations on its own but forwards all the computations to some underlying compute engine. It transmits all of the arguments to the compute engine methods from the machine on which the VBM Core is running to the machine on which the compute engine is running. It then packages and transmits the results of the underlying compute engine back to the machine on which VBM Core is running. All VBM compute engines may be run remotely by being layered with this module and those that are currently implemented may be found in Section.

The required tags and setup of the "VBM_Compute_Engine" data block are exactly the same for this module as they are for the underlying compute engine, except that the name of the module is normally different and the first line of the "VBM_Compute_Engine" block may be interpreted differently.

The name of the compute engine is modified to denote the fact that it is now remotely executable. For example, if the name of the module is VBM_1D_AUTO then the name of the layered compute engine would be VBM_1D_remote_AUTO.

The first line of the "VBM_Compute_Engine" block is interpreted as a list of machines on which to run the computation. A machine may be listed more than once, and this module will run one copy of the computation on the machine for each time it is listed. Note, this module does not currently start the compute server on the remote machines automatically. It must be started by hand. The compute server may be started using a command similar to the one below (assuming that the environment variable $VBM is set to be the VBM installation directory.


cd $VBM/python_script/continuation_modules;VBM_remote_base.py

The "VBM_remote_base" module can detect if it has been called as a stand-alone program or as part of VBM. If it is called as part of VBM it functions as a client, and if it is called as a stand-alone program it functions as the server.

9.5 VBM_2D_Rheinboldt

This compute engine is an implementation of Rheinboldt's Moving Frame algorithm in Matlab (references to the paper from which this algorithm is derived can be found in the doctoral thesis of Randy Paffenroth on http://lcvmwww.epfl.ch/~redrod (Note: as of March 8th, 1999 the thesis has not yet been added to the web page)).

An example defaults file for this compute engine can be found below.


steps = 3;
step_size1 = 0.2;
step_size2 = 0.2;
vbm_filename = 'fubar.vbm';
names = 'x;y;z';

The "steps" option defines how large the initial manifold should be when you hit the "Start" button. The "step_size1" and "step_size2" options define the length of the steps in each of the two continuation directions. The "vbm_filename" tells Matlab the name of the file in which it can store its temporary VBM files (there is no need to change this option for most purposes). Finally, the "names" option tells Matlab what are the names it should use when it makes a new VBM file.

An example problem file for this compute engine can be found below.


function x = func(a)
% This function takes a column vector y
% This function returns a column vector x
x = [a(1)*a(1)+a(2)*a(2)+a(3)*a(3)-1];

Basically, this compute engine uses a Matlab "m" file in which the desired function is defined. For more information on Matlab "m" files you may see the Matlab documentation.

This compute engine returns connectivity, so it is important that the VBM file you are computing with already have a "VBM_Connectivity" data block in it before you start your computation. Also, Matlab must be in your path when you start VBM for this module to function.


Next Previous Contents