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