CMR
1.3.0
|
A matrix \( M \in \mathbb{Z}^{m \times n} \) is totally unimodular if all its square submatrices have a determinant in \( \{-1,0,+1\} \). Here, a submatrix does not need to be contiguous, i.e., the matrix \(M = \begin{pmatrix} 1 & 0 & -1 \\ 1 & 0 & 1 \end{pmatrix} \) is not totally unimodular since the submatrix indexed by rows \( \{1, 2 \} \) and columns \( \{ 1,3 \} \) has determinant 2. In particular, every totally unimodular matrix has only entries in \( \{-1,0,+1\} \) as these are the 1-by-1 submatrices.
The command
cmr-tu IN-MAT [OPTION...]
determines whether the matrix given in file IN-MAT
is totally unimodular.
Options:
-i FORMAT
Format of file IN-MAT
, among dense
for dense-matrix and sparse
for sparse-matrix; default: dense.-D OUT-DEC
Write a decomposition tree of the underlying regular matroid to file OUT-DEC
; default: skip computation.-N NON-SUB
Write a minimal non-totally-unimodular 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.--algo ALGO
Use algorithm from {decomposition, submatrix, partition}; default: decomposition.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 default recognition algorithm is based on Implementation of a unimodularity test by Matthias Walter and Klaus Truemper (Mathematical Programming Computation, 2013). It first runs Camion's Signing Algorithm to reduce the question to that of recognizing regular matroids. Please cite the 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}, }
In order to repeat experiments described in the paper above, the function can be parameterized as to use exponential-time algorithms.
The corresponding function in the library is
and is defined in tu.h. Its parameters also allow to choose one of the enumeration algorithms with exponential running time instead of the decomposition algorithm.