![]() |
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 command
cmr-regular IN-MAT [OPTION...]
determines whether the matrix given in file IN-MAT
is regular.
Options:
-i FORMAT
Format of file IN-MAT
; default: dense.-D OUT-DEC
Write a decomposition tree of the regular matroid to file OUT-DEC
; default: skip computation.-N NON-MINOR
Write a minimal non-regular submatrix to file NON-SUB
; default: skip computation.Advanced options:
--stats
Print statistics about the computation to stderr.--time-limit LIMIT
Allow at most LIMIT
seconds for the computation.--no-direct-graphic
Check only 3-connected matrices for regularity.--no-series-parallel
Do not allow series-parallel operations in decomposition tree.Formats for matrices: dense, sparse If IN-MAT
is -
then the matrix is read from stdin. If OUT-DEC
or NON-SUB
is -
then the decomposition tree (resp. the submatrix) is written to stdout.
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 corresponding function in the library is
and is defined in regular.h.