Return to READ_ME CVS log

Up to [local] / OpenXM_contrib / PHC / Ada / Math_Lib / Supports

Import the second public release of PHCpack.

OKed by Jan Verschelde.

Support sets, polytopes, and feasibility of linear-inequality systems in PHCv2.

New in this release is the usage of Ada 95 concepts to build the lists.

The library is divided in two parts :
1) algorithms for linear programming;
2) data structures for support sets and faces of polytopes.
The algorithms are independent from the data structures.

--------------------------------------------------------------------------------
file name                          : short description
--------------------------------------------------------------------------------
dictionaries                       : basic manipulations for simplex algorithm
linear_programming                 : primal and dual simplex algorithm
givens_rotations                   : transformations to triangulate matrices
integer_linear_inequalties         : feasibility of integer linear inequalities
floating_linear_inequalities       : feasibility of floating linear inequalities
face_enumerators_utilities         : some utilities for the face enumerators
integer_face_enumerators           : enumerate k-faces of integer polytope
floating_face_enumerators          : enumerate k-faces of floating polytope
floating_linear_inequality_solvers : primal-dual algo with inconsistency proof
--------------------------------------------------------------------------------
generic_lists_of_vectors           : generic lists of links to vectors
generic_lists_of_vectors_io        : input/output for generic lists of vectors
lists_of_integer_vectors           : lists of standard integer vectors
lists_of_integer_vectors_io        : input/output of lists of integer vectors
lists_of_floating_vectors          : lists of standard floating vectors
lists_of_floating_vectors_io       : input/output of lists of floating vectors
generic_arrays_of_vector_lists     : generic arrays of vector lists 
generic_arrays_of_vector_lists_io  : input/output for arrays of vector lists
arrays_of_integer_vector_lists     : arrays of integer vector lists
arrays_of_integer_vector_lists_io  : i/o for arrays of integer vector lists
arrays_of_floating_vector_lists    : arrays of floating vector lists
arrays_of_floating_vector_lists_io : i/o for arrays of floating vector lists
integer_support_functions          : support functions for integer polytopes
integer_faces_of_polytope          : faces of integer polytopes
integer_faces_of_polytope_io       : output for faces of integer polytopes
floating_support_functions         : support functions for floating polytopes
floating_faces_of_polytope         : faces of floating polytopes
--------------------------------------------------------------------------------
ts_diclp                           : test dictionaries and linear programming
ts_givrot                          : test of givens rotations
ts_lstvec                          : test lists of links to vectors
--------------------------------------------------------------------------------
The multi-precision facilities have not been developed throughout this
library, since we are dealing with Newton polytopes, spanned by vertices
with small integer numbers.

This library contains three different methods for deciding on the
feasibility of a linear-inequality system:
1) dictionaries : along the book 
2) looking for inconsistency proofs
3) primal/dual method with either a solution or an inconsistency proof

The algorithms to enumerate the k-faces are not efficient if one is
interested in the whole face lattice of a polytope.

wc *adb counts 6765 lines of Ada code