Description
-------------------------

This package is a small, fast implementation of an algorithm for
finding extremal rays of a polyhedral cone, with filtering.  It is
intended for finding normal surfaces in triangulated 3-manifolds, and
therefore does not implement various features that might be useful for
general extremal ray problems.

The setup is this.  Define the support of a vector v in R^n to be the
set of indices i such that v_i is non-zero.  We are given an integer
matrix M, typically with many more columns than rows, and a list of
"illegal supports".  The support of a vector is illegal if its
support contains one of the illegal supports on the list.

We want to find all the extremal rays of the cone
    (Null space of M) intersect (positive orthant), 
which are generated by vectors with legal support.  (The restriction
to vector with legal support is what is meant by "filtering".) In the
3-manifold application the matrix describes the normal surface
equations in quad form, and the illegal supports include all pairs of
distinct quads in the same 3-simplex.  (They could also include
various types of "obvious compressions".)

The algorithm is due to Dave Letscher, and incorporates ideas of Komei
Fukuda's.  One constructs a sequence P_n of polyhedra as follows.

P_0 is the standard n-simplex.

Given P_n-1, construct P_n as follows.  
Take the hyperplane H_n defined by the nth row of the matrix M.
Divide the vertices of P_n-1 into three classes: positive, negative
and neutral, according to whether they lie on the positive side, the negative
side, or are contained in, H_n.  For each pair consisting of a positive
vertex v and a negative vertex w we intersect H with the segment joining
v to w.  The intersection point u will give rise to a vertex of P_n
if it satisfies two conditions: 

   1. the support of u is legal; and

   2. the submatrix of M_u of M has nullity 1, where M_u consists of
      elements of which are contained in the first n rows and in the
      columns which are indexed by the support of u.

If u satisfies these conditions then its smallest integral multiple is a
vertex of P_n.  The neutral vertices of P_n-1 are also vertices of P_n.

If M has k rows, then the vertices of P_k generate the set of extremal
rays of the cone which have legal supports.

Installation Instructions
-------------------------

This package can be built either as a standalone C module, which you
can link with your own C code, or as a python module.  The python
module is needed by t3m.

To build the C module type make in the distribution directory.  If
you happen to have gcc-3.2 then you should edit the Makefile to use it.
The code will run much faster.  The object file FXrays.o and a number
of test programs will be built.

To build the python module, if you have superuser privileges on your
UNIX system, type:

  python setup.py build
  python setup.py install

This will install FXrays in the site-packages directory of your
python installation.

If are not a superuser and wish to install the FXrays python module
in your home directory, type:

  python setup.py build
  python setup.py install --install-lib ~

This will create a subdirectory of your home directory named FXrays
containing the module.  In order for python to find the module you
must add this directory to your PYTHONPATH environment variable.  For
example:

export PYTHONPATH=$HOME

Bugs and Comments
-------------------------

Please email bugs, comments, or offers of assistance, to either or
both of:

culler@math.uic.edu
nathand@math.harvard.edu

Last Update
-------------------------

The date of the last update is contained in the file named timestamp
in the root directory of the distribution.