the Fourier-Motzkin library

[<< home] [description] [documentation] [download] [installation] [publications] [history] Current version: 0.5.0


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:

Communication: one group is available for subscription

Please contact the author directly for any question.


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.



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
The make install command can be used to install the FM library.
$> 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]
  2. Miscellaneous

  3. 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]


10/30/08: Release of fm-0.5.0

02/16/08: Release of fm-0.4.0
12/01/06: Release of fm-0.3.0
09/06/06: Release of fm-0.2.0
06/08/06: Release of fm-0.1.2
06/07/06: Release of fm-0.1.1
06/05/06: Release of fm-0.1.0