Unimodularity Library
The Unimodularity Library is a software library written in C++
that implements an efficient algorithm for testing total unimodularity,
based on Seymour's decomposition theorem [1] for regular matroids.
The algorithm runs in O( (n+m)^5 ) time and is a simplified version
of the cubic algorithm of [2]. The algorithm can also test for the
related properties of unimodularity and strong unimodularity.
The Unimodularity Library is published under the Boost Software License [3].
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 (03/14/2017):
-
Raise an error message if an integer overflow occurs during k-modularity check.
Thanks to Filippo Quondam for reporting the problem.
Version 1.2e (02/28/2016):
-
Fixed a bug in violator search.
Thanks to Bala Krishnamoorthy for reporting the problem.
Version 1.2d (02/06/2015):
-
Fixed segfault bug.
Thanks to Tobias Windisch for reporting the problem.
Version 1.2c (08/05/2014):
-
Fixed compilation errors due to more recent Boost versions.
Thanks to Volker Braun for the fix.
Version 1.2b (10/12/2012):
-
Fixed compilation error on Mac OS.
Thanks to Yvon Sauvageau for reporting the problem.
Version 1.2 (04/13/2012):
-
Users of the Polymake extension can now analyze the matroid decomposition.
-
Updated package documentation (including the experiments' documentation).
-
This is the official version corresponding to our article in Mathematical Programming Computation.
Version 1.1 (02/09/2012):
-
A bug in the graphicness test in versions before 1.1
may cause a graphic matrix to be not recognized as such.
Thanks to Paulo Seijas for reporting the problem.
-
Marc Pfetsch provided an update to make the extension compatible with Polymake version 2.11.
Version 1.0 (06/13/2011):
-
Released version 1.0 (the publication version).
-
Get the files unimodularity-library-1.2h.tar.gz,
which depends on the Boost Software Library (version 1.43.0 or later) [4]. If you don't have boost installed,
get unimodularity-library-noboost-1.2h.tar.gz.
-
Read the README file for instructions or simply try
./configure
make
make install
to install the software. The main binary is called unimodularity-test;
it can be found in the src/ directory prior to installing.
-
In publications, please cite the library as follows:
M. Walter and K. Truemper, Implementation of a Unimodularity Test, Mathematical Programming Computation, volume 5, number 1, pp. 57-73, 2013.
Here is the bibtex entry.
-
For a first test of the program, create a file with the matrix:
5 4
1 0 0 1
1 1 0 0
0 1 1 0
0 0 1 1
1 1 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.
-
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
if you want to obtain certificates for the answer.
As an alternative, use the
unimodularity extension
for the
Polymake system.
Experiments in the article "Implementation of a Unimodularity Test"
To repeat our experiments, fetch the test matrices
article-experiments.tar.gz
and follow the instructions in the README file.
References
[1]
|
P. D. Seymour. Decomposition of regular matroids.
J. Comb. Theory, Ser. B 28, 305-359, 1980.
|
[2]
|
K. Truemper.
A decomposition theory for matroids.
V. Testing of matrix total unimodularity,
J. Comb. Theory, Ser. B 49, 241-281, 1990.
|
[3]
|
http://www.boost.org/LICENSE_1_0.txt
|
|