A Brikhoff-von Neumann matrix decomposer in Java
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src
.gitignore
COPYING
LICENSE
README.md
pom.xml

README.md

Birkhoff-von Neumann Decomposition

Codeship status

This package provides an implementation of Brikhoff's heuristic for generating Birkhoff-von Neumann decompositions of bistochastic matricies.

Maven:

<dependency>
    <groupId>info.rmarcus</groupId>
	<artifactId>brikhoffvonneumann</artifactId>
	<version>0.1.0</version>
</dependency>

The algorithm decomposes a square bistochastic matrix (a matrix whose column and row sums are all equal to one) into a convex combination of permutation matrices. Each entry i,j in the bistochastic matrix can be interpreted as the probability that a permutation swapping elements i and j will appear in the (weighted) decomposition.

The results are a convex combination of permutation matrices:

Iterator<CoeffAndMatrix> i = BVNDecomposer.decomposeBiStocastic(new double[][] {{1./4., 1./4., 1./4., 1./4.}, 
		{1./4., 1./4., 1./4., 1./4.}, 
		{1./4., 1./4., 1./4., 1./4.},
		{1./4., 1./4., 1./4., 1./4.}});
		
double coeffSum = 0.0;

while (i.hasNext()) {
	CoeffAndMatrix cam = i.next();
	coeffSum += cam.coeff;
}

assertEquals(coeffSum, 1.0, BVNDecomposer.EPSILON);