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:
- the support of u is legal; and
- 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.
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. 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 install
This will install FXrays in the site-packages directory of your python installation.
If you are not a superuser and wish to install the FXrays python module into your user site-packages (as described in https://docs.python.org/2.7/library/site.html) do
python setup.py build --user
NOTE: On Windows, FXrays does not build correctly with mingw64. There are segfaults caused by linking with msvcrt instead of msvcr90. However, building a 64 bit FXrays with the default msvc compiler (in the Microsoft Visual C++ for Python 2.7 package) works.
Bugs and Comments
Please email bugs, comments, or offers of assistance, to either or both of:
Copyright (C) 2000-present by Marc Culler and others.
This program is released under the GNU General Public License version 2 or (at your option) any later version as published by the Free Software Foundation. See
for the complete license text.