BirkhoffDecomposition.jl

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

Build Status codecov

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).

Used By Packages

No packages found.