FM

Description

FM is a library dedicated to manipulating Q-polyhedra, and especially those representing the projection of a given system of inequalities. The projection is computed with an improved version of the Fourier-Motzkin algorithm. The library offers features such as:

• A redundancy-controlled C implementation of the Fourier-Motzkin projection algorithm.
• A lexicographic min/max computation (for Q and Z polyhedra).
• A lot of auxiliary functions to manipulate Q-polyhedra.

Communication: one group is available for subscription

• fm-announce: receive announces about releases of the software.

Documentation

Please note that the two following documents are highly preliminary, and incomplete. The documentation will be improved soon. In the meantime, don't hesitate to contact the author for any question.

• FM manual: fm.pdf.
• FM API documentation: browse the Doxygen documentation or download it.

Download

• To download the FM library: fm-0.5.0.tar.gz

Installation

The installation of FM follows the classical GNU library scheme. You can optionally specify the path of PIPLib install to the configure script with --with-piplib, to enable all the functionalities of the library (especially the Le Fur redundancy elimination method). It is strongly recommanded to compile FM with PIPLib enabled for better scalability on larger systems. The configure script will automatically detect the location of optional dependence if --prefix=path/to/dir is specified and the dependence is installed in path/to/dir.

$> tar xzf fm-0.5.0.tar.gz
$> cd fm-0.5.0
$> ./configure --prefix=/path/to/be/installed 
$> make

The make check command can be used to make a test run of FM. It will execute some I/O tests, basic rational tests and 4 solver/lexmin computation tests.

$> make check

$> make install

Publications involving FM

In conferences

1. Louis-Noël Pouchet, Cédric Bastoul, Albert Cohen and John Cavazos. Iterative optimization in the polyhedral model: Part II, multidimensional time. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'08), pp 90--100, ACM Press, Tucson, Arizona, June 2008.
   [bibtex-entry] [pdf] [slides]

Miscellaneous

2. Louis-Noël Pouchet. When Iterative Optimization Meets the Polyhedral Model: One-dimensional Date. Master thesis (University of Paris-Sud XI), Orsay, France, October 2006.
   [bibtex-entry] [pdf] [slides]

History

10/30/08: Release of fm-0.5.0

• Improvements:
  • Redundancy reduction: Provide automatic scaling flag for fm_solver (FM_SOLVER_AUTO_SIMPLIFY).
  • New algorithms: Add fm_solution_traverse, a generic polytope scanner.
  • Improve the robustness of the library, and the memory behavior.
• License: FM is now released under the terms of the GNU Lesser GPL v3.
• Bug fixes: small fixes for memory leak and null constraints handling, and in fm_solution_point_included.

• Improvements:
  • Redundancy reduction: Add optional support of Piplib (for polyhedra emptiness test and improved redundancy reduction). Add compacted_solution type (compaction based on implicit equality detection over normalized inequalities).
  • New features: Offer computation of sets of 'connected' variables
  • New algorithms: Add Gaussian elimination, and Le Fur descending methods for redundancy reduction.
• Bug fixes: Fix an important bug in the integer hull computation, remove memory leaks.

• Improvments: No significant improvment.
• Bug fixes: Support 64-bit architecture.

• Improvments: Implement last research results about the algorithm.
• Bug fixes: No significant bug fixed.

• Improvements: Reduce memory footprint.
• Bug fixes: No significant bug fixed.

• Improvements: Add some extra features to the solver.
• Bug fixes: Fix an important bug in the termination clause of the algorithm.

• Initial release of the project.