Metadata-Version: 2.4
Name: FXrays
Version: 1.3.6
Summary: Computes extremal rays with filtering
Author-email: Marc Culler <culler@marc-culler.info>, "Nathan M. Dunfield" <nathan@dunfield.info>
License: GPLv2+
Project-URL: Homepage, https://github.com/3-manifolds/FXrays
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: GNU General Public License v2 or later (GPLv2+)
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: C
Classifier: Programming Language :: Cython
Classifier: Programming Language :: Python
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.7
Description-Content-Type: text/x-rst

FXrays
======


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. 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``, type::

    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
-----------------

To report bugs or provide comments please visit the
`FXrays issue page <https://github.com/3-manifolds/FXrays/issues>`_.


License
-------

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

     https://www.gnu.org/licenses/old-licenses/gpl-2.0.txt

for the complete license text. 
