## BirkhoffDecomposition.jl

Julia package for decomposing doubly stochastic matrices
Author vvalls
Popularity
0 Stars
Updated Last
2 Years Ago
Started In
September 2020

BirkhoffDecomposition.jl is a Julia package for decomposing a doubly stochastic matrix as the sum of permutation matrices.

Installation: `julia> import Pkg; Pkg.add("BirkhoffDecomposition")`

## Exact Birkhoff decomposition

```# Load the package
using BirkhoffDecomposition

# Generate a random doubly stochastic matrix (n is the dimension)
n  = 3;
X  = randomDoublyStochasticMatrix(n);

# Compute exact decomposition
P, w = birkdecomp(X);```

The output of `birkdecomp(X)` is an array `P` of `n*n` permutation matrices and `w` a vector of weights. We can now write the doubly stochastic matrix `X` in vector form as `P*w`

## Approximate Birkhoff decomposition

The command `birkdecomp(X,ε)` obtains an ε-approximate Birkhoff decomposition of matrix `X`. In particular, the resulting decomposition `Y = reshape(P*w,n,n)` ensures that the Frobenious norm of `X-Y` is smaller than `ε`.

```n  = 16; X = randomDoublyStochasticMatrix(n);
ε = 1e-2;
P, w = birkdecomp(X,ε);

Y = reshape(P*w,n,n);
sqrt(sum((X-Y).^2)) <= ε  # Frobenius norm```

## Cite

The algorithm implemented in the package is the `Birkhoff+` presented in:

``````Víctor Valls, George Iosifidis, and Leandros Tassiulas
Birkhoff's Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches.
arXiv preprint arXiv:2011.02752.
``````

The article has been accepted for publication in IEEE/ACM Transactions on Networking (April 2021).

### Required Packages

View all packages

### Used By Packages

No packages found.