![]() |
CMR
1.3.0
|
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' \).
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.
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}, }
The functionality is defined in regular.h. The main functions are: