Unimodularity Library

The Unimodularity Library is a software library written in C++ that implements an efficient algorithm for testing total unimodularity [1], based on Seymour's decomposition theorem [2] for regular matroids. The algorithm runs in O((n+m)5) time and is a simplified version of the cubic algorithm of [3]. The algorithm can also test for the related properties of unimodularity and strong unimodularity.

The Unimodularity Library is published under the Boost Software License [4]. It was developed by Matthias Walter under supervision of Klaus Truemper.

Note that the code is superseded by the Combinatorial Matrix Recognition library.

Download, Installation & Usage

In publications, please do not forget to cite us!

With Boost

If you have Boost 1.43 or later:
unimodularity-library-1.2f.tar.gz

Without Boost

If you don't have Boost 1.43 or later:
unimodularity-library-noboost-1.2f.tar.gz

With polymake

To use it from the polymake system: unimodularity-library-Polymake-1.2f.tar.gz

Installation

Read the README file for instructions or simply try 

./configure
make

to compile and 

sudo make install

to install the software. The main binary is called unimodularity-test; it can also be found in the src/ directory prior to installing.

Usage: Program

Create a file with the 4 x 5 matrix: 

4 5
1 1 0 0 1
0 1 1 0 1
0 0 1 1 1
1 0 0 1 1

Then invoke unimodularity-test with the file name as the only argument. If you find out that your matrix is not t.u. and want to search for a violator, you should add the -c option.

Usage: C++ Library

To use the library in C++, you need to create a boost::numeric::ublas::matrix<int> object and call the is_totally_unimodular function. There are different versions of this function the allow you to obtain certificates for the answer.

Changes & Bugfixes

  • Version 1.2h (09/27/2019): Fixed a bug in search for violating submatrix. Added functionality to test directly for regularity of binary matroids.
  • Version 1.2g (08/15/2019): Added support for complement total unimodularity.
  • Version 1.2f (2017-03-14): Raise an error message if an integer overflow occurs during k-modularity check; reported by Filippo Quondam.
  • Version 1.2e (2016-02-28): Bug in violator search; reported by Bala Krishnamoorthy.
  • Version 1.2d (2015-02-06): Memory bug; reported by Tobias Windisch.
  • Version 1.2c (2014-05-08): Compilation errors due to more recent Boost; fix by Volker Braun.
  • Version 1.2b (2012-10-12): Compilation error on Mac OS; reported by Yvon Sauvagneau.
  • Version 1.2 (2012-04-13): Official version for article [1]. Polymake users can now analyze the matroid decomposition.
  • Version 1.1 (2012-02-09): Bug in graphicness test. Older versions may produce wrong results! Reported by Paulo Seijas. Update for polymake version 2.11 by Marc Pfetsch.
  • Version 1.0 (2011-06-13): First release of the software.

Article Experiments

To repeat our experiments from [1], fetch the test matrices article-experiments.tar.gz and follow the instructions in the enclosed README file.

References

  1. Matthias Walter and Klaus Truemper.
    Implementation of a unimodularity test.
    Math. Program. Ser. C, 5(1):57-73, 2013.
  2. Paul D. Seymour.
    Decomposition of Regular Matroids.
    Journal of combinatorial Theory, Series B, 28(3):305-359, 1980.
  3. Klaus Truemper.
    A Decomposition Theory for Matroids. V. Testing of Matrix Total Unimodularity.
    Journal of Combinatorial Theory, Series B, 49(2):241-281, 1990.
  4. Boost Software License, v1.0.