CMR  1.3.0
Regular Matroids

A matrix $$M \in \{0,1\}^{m \times n}$$ is regular if the binary matroid represented by $$M$$ is representable over every field. This is equivalent to requiring that the matroid is equal to the ternary matroid represented by the Camion-signed version $$M'$$ of $$M$$, and thus equivalent to total unimodularity of $$M'$$.

Usage

The executable cmr-regular determines whether the support matrix $$M$$ of a given matrix is regular.

./cmr-regular [OPTION]... FILE


Options:

• -i FORMAT Format of input FILE; default: dense.
• -o FORMAT Format of output matrices; default: dense.
• -d Output the decomposition tree if $$M$$ is regular.
• n Output the elements of a minimal non-regular submatrix.
• N Output a minimal non-regular submatrix.
• s Print statistics about the computation to stderr.

Formats for matrices are dense-matrix and sparse-matrix. If FILE is -, then the input will be read from stdin.

Algorithm

The implemented recognition algorithm is based on Implementation of a unimodularity test by Matthias Walter and Klaus Truemper (Mathematical Programming Computation, 2013). It is based on Seymour's decomposition theorem for regular matroids. The algorithm runs in $$\mathcal{O}( (m+n)^5 )$$ time and is a simplified version of Truemper's cubic algorithm. Please cite the following paper in case the implementation contributed to your research:

@Article{WalterT13,
author    = {Walter, Matthias and Truemper, Klaus},
title     = {Implementation of a unimodularity test},
journal   = {Mathematical Programming Computation},
year      = {2013},
volume    = {5},
number    = {1},
pages     = {57--73},
issn      = {1867-2949},
doi       = {10.1007/s12532-012-0048-x},
publisher = {Springer-Verlag},
}


C Interface

The functionality is defined in regular.h. The main functions are: