*********************************************************************
*         User's Manual: Preliminary Version of StartSystem         *
*                                                        2002/05/12 *
*********************************************************************

Yang Dai
Dept. of Bioengineering, University of Illinois at Chicago

Katsuki Fujisawa
Dept. of Architecture and Architectural Systems, Kyoto University

Takayuki Gunji, Masakazu Kojima and Tomohiko Mizutani
Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology 

Akiko Takeda
Corporate Research & Development Center, Toshiba Corporation

*****************
**   Caution   **
*****************

The software package StartSystem is still under development. 
Please report any trouble and bug that you may encounter to 

Tomohiko MIZUTANI 
mizutan8@is.titech.ac.jp


**********************************
**   Section 1. Introduction.   **
**********************************

When we solve a polynomial system by the polyhedral homotopy continuation method, 
the following four phases are necessary:

(1) Compute the mixed cells and construct a family of polyhedral homotopy equation 
systems.  
(2) Solve the starting binomial equation system of each polyhedral system.
(3) Balance the lifting power constants of the family of homotopy equation systems. 
(4) Trace the homotopy solution curves from the solutions of the binomial systems 
computed in (2). 

The software package StartSystem provides steps (1) - (3), while either of the MATLAB 
software packages CMPCm [1] and the C++ software package CMPSc [2] provide step (4). 
That is, the package StartSystem reads a data file which describes a polynomial system 
to be solved and output data files which are necessary for the packages CMPSm and 
CMPSc as their input files. 

More detailed information on this software package, CMPSm and CMPSc are available at 
http://www.is.titech.ac.jp/~kojima/polySys.html


**********************************************************************
**   Section 2. Compile and link (Compiler: c++  2.91.66 or later). **
**********************************************************************

Please extract the archive of StartSystem. 
If you want to install the archive to "/home/StartSystem",
please extract this at /home .

For example,

> tar zxvf StartSystem.tar.gz 

You can get the following subdirectory tree.

 /home/StartSystem/-------- simplexKoj/          (simplex method library 1)
                      +---- simplexTaki/         (simplex method library 2)
                      +---- makefile             (makefile)
                      +---- main.cpp             (Main program)
                      +---- inputDataExamples/  (some examples)
                      +---- ......
								
		   
First, go to the subdirectory "simplexKoj" and create the library "simplexKoj.a".  

> cd simplexKoj
> make all

Second, go to the subdirectory "simplexTaki" and create "simplexTaki.a".

> cd ../simplexTaki
> make all

Third, copy the "simplexKoj/simplexKoj.a" and "simplexTaki/simplexTaki.a" to the directory "StartSystem".

> cd ../ 
> cp simplexKoj/simplexKoj.a ../
> cp simplexTaki/simplexTaki.a ../

Finally, type "make all" in the directory "StartSystem".

> make all

Consequently you will get the binary executable file "StartSys".


***************************************************************
**   Section 3. 3 cyclic polynomial system --- an example.   **
***************************************************************

We will use the 3 cyclic polynomial system 

-x1x2x3 + 1 = 0,
x1x2 +x2x3 + x1x3 = 0,
x1 + x2 + x3 = 0.

to illustrate the input and output files of the StartSystem. 


*******************************
**   Section 4. Input file.  **
*******************************
 
The input data of the 3 cyclic polynomial system for the StartSys, which 
we have created in Section 3, is described as follows:

# 3cycC --- the name of this file
# 
# Any line starting "#" denotes a comment line, which is neglected by
# StartSys and CMPSc and CMPSm.
# 
# The 3 cyclic polynomial system: 
#
#    -x1x2x3 + 1 = 0
#    x1x2 +x2x3 + x1x3 = 0
#    x1 + x2 + x3 = 0
# 
# The keywords to denote the input data are :
#
#     "n = " 
#     "m = "
#     "ap.q = "
#     "coefp.qr = "
#     "coefp.qi = "
#
# Here p and q are positive integers which specify the qth term of the pth equation.
# 
# x1, x2, x3 are complex variables; hence 
#
#     n = 3
# 
# The 1st, 2nd and 3rd equations have 2, 3 and 3 terms.
# But 2nd and 3rd equations do not have a constant term, you add a constant term.
# Therefore, 2nd and 3rd equations have 4 terms.
#
#     m = 2 3 3
# 
# The 1st term -x1x2x3 of the 1st equation has the powers 1 for x1, 1 for x2 and 1 for x2
# hence,
#
#     a1.1 = 1 1 1 
#
# Similarly, 
#       
#     a2.1 = 1 1 0
#     a2.2 = 0 1 1
#     a2.3 = 1 0 1
#     a3.1 = 1 0 0
#     a3.2 = 0 1 0
#     a3.3 = 0 0 1
#
# The 1st term -x1x2x3 of the 1st equation has the coefficient -1; hence 
#
#    coef1.1r = -1 --- the real part
#    coef1.1i = 0  --- the imaginary part 
#  

# The dimension or the number of variables of the 3 cyclic polynomial system
n = 3

# The number of terms in each equation
m = 2 3 3 

# The powers of each term
a1.1 = 1 1 1 
a1.2 = 0 0 0 
a2.1 = 1 1 0 
a2.2 = 0 1 1 
a2.3 = 1 0 1 
a3.1 = 1 0 0 
a3.2 = 0 1 0 
a3.3 = 0 0 1

# The coefficient of each term
coef1.1r = -1
coef1.1i = 0
coef1.2r = 1
coef1.2i = 0
coef2.1r = 1
coef2.1i = 0
coef2.2r = 1
coef2.2i = 0
coef2.3r = 1
coef2.3i = 0
coef3.1r = 1
coef3.1i = 0
coef3.2r = 1
coef3.2i = 0
coef3.3r = 1
coef3.3i = 0


<<< Remark >>>
When we solve a polynomial system of equations which does not have a 
constant term in each equation, we may need to have a constant term in each 
equation in general; if an equation does not have a constant term, add a 
constant term ap.q = 0 0 ... 0 with coefp.qi = 0.0 and coefp.qi = 0.0. 
See [3] for more details on the polyhedral homotopy continuation method. 
The 3 cyclic polynomial example above does not follow this general rule. 

**********************************
**   Section 5. Output files.   **
**********************************

The StartSys creates 5 types of output files: 
*.dat2, *.lp, *.out, *.coef and "mixed cell files", 
among which the last two types of files are necessary for CMPSm and CMPSc 
as their input. In the case of the 3 cyclic polynomial system, we have 
the 3cycC.dat2, 3cycC.lp, 3cycC.out, 3cycC.coef and 3cycC1 and 3cycC2 files; 
the latter two are "mixed cell files". 

The 3cycC.coef file includes the coefficients of the starting binomial system, which 
depend on a random number seed to be specified when the StartSys is executed,
in addition to the information described in 3cycC.dat. For example, they are: 

Rcoef1.1r = 7.009763693
Rcoef1.1i = 8.096763491
Rcoef1.2r = 0.8879545521
Rcoef1.2i = 1.214791905
Rcoef2.1r = 3.483067552
Rcoef2.1i = 4.219620016
Rcoef2.2r = 6.998054984
Rcoef2.2i = 0.6638433648
Rcoef2.3r = 5.874823525
Rcoef2.3i = 6.429663057
Rcoef3.1r = 2.713367107
Rcoef3.1i = 0.69655987
Rcoef3.2r = 9.49639379
Rcoef3.2i = 3.821752264
Rcoef3.3r = 3.227100961
Rcoef3.3i = 9.883655114

On the other hand, the 3cycC1 and 3cycC2 files include the initial point information 
of the binomial system associated with each mixed cell (Two mixed cells are 
obtained in the case of the 3 cyclic polynomial system, but this number depends on 
not only the problem but also the random number seed). They also include information 
on the lifting power constants of each polyhedral homotopy function. The content of 
the 3cycC1 is as follows:

NumOfSols = 3

# Root information
sol1 = -0.594228568938181
-1.31174259369598
0.208223110773241
0.334588425690058
-0.120083263652344
-0.216504123287918

sol2 = 1.4331166938359
0.141254260493053
-0.393873631846453
0.0130322907396191
0.247539702617587
0.00425690475168446

sol3 = -0.838888124897718
1.17048833320293
0.185650521073211
-0.347620716429677
-0.127456438965243
0.212247218536233


# Power information
=  0 0 
=  0 1 0 1 
=  0 0 1 1 


**************************************************
**   Section 6. Execution of the "StartSys".   **
**************************************************

When you try to solve the 3cycC.dat which is contained in the directory "StartSystem"

Type

> StartSys 3cycC.dat 1

Here "3cycC.dat" is a polynomial data (see Section 3), and "1" is a seed number 
for generating a random lifting values and coefficients. You can choose a natural 
number (1,2,...) for a seed number.

if you can execute this command without trouble, you will get five types of files.

3cycC.coef
3cycC.dat2
3cycC.lp
3cycC.out
3cycC1 - 3cycC{# mixed cells}

To execute the CMPSc, 3cycC.coef and 3cycC1 - 3cycC{# mixed cells} are necessary; 
hence you need copy these files to the directory of the CMPSc.

<<< Acknowledgement >>> 
The authors are grateful to Mr. Jun Takikawa for providing us 
with his C++ codes of the simplex method for linear programs, 
which is in the directory ``simpleTaki.'' 

<<< References --- [1] and [2] are available at 
                   http://www.is.titech.ac.jp/~kojima/polySys.html >>>

[1] S. Kim and M. Kojima,  CMPSm: A Continuation Method for Polynomial Systems 
(MATLAB version), B-376, Dept. of Math. and Comp. Sciences, Tokyo Inst. of Tech., 
January 2002.

[2] S. Kim and M. Kojima,  CMPSc: A Continuation Method for Polynomial Systems 
(C++ version), B-378, Dept. of Math. and Comp. Sciences, Tokyo Inst. of Tech., 
March 2002. Revised April 2002. 

[3] T. Y. Li, Solving Polybimial Systems by Polyhedral Homotopies, Taiwan 
Journal of Mathematics 3 (1999) 251-279.