The complexity of decomposing a bi-stochastic matrix
Summary. Using your favourite $O(n^d)$ algorithm for finding a matching in graphs on $O(n)$ vertices, there is a simple algorithm using  $O(\max\{n^{d+2},n^4\})$ operations over the reals for decomposing doubly-stochastic matrices. The run-time bound comes from $O(n^2)$ iterations of a procedure in which each iteration involves finding a matching, and modifying coefficients of an $n \times n$ matrix. (There are undoubtedly ways of streamlining these operations, at least in the case of the time required to modify the matrix coefficients.)

Details. 
The following proof of the Birkhoff&ndash;von Neumann theorem can be found e.g. in [1], and leads to an efficient algorithm for decomposing doubly-stochastic matrices.

We consider matrices $A$ whose rows and columns all sum to the same value (which for a doubly-stochastic input is initially 1). Let $N$ be the number of non-zero entries in your $n \times n$ doubly-stochastic matrix: in decomposing the matrix, we will reduce the number of non-zero entries while keeping the invariant of having constant line-sums. Thus at each stage, we have either $N \geqslant n$ or $N = 0$, by the invariant of having equal line-sums.


Set $t \gets 0$.
While $N &gt; 0$:


Set $t \gets t + 1$.
For each $i \in [n]$: let $S_i = \bigl\{ j \in [n]: A_{ij} &gt; 0 \bigr\}$.
Find a bijection $\sigma: [n] \to [n]$ such that $\sigma(i) \in S_i$(such a bijection exists, and can be found efficiently, by Hall's Marriage criterion).
Let $u^{(t)} = \min\,\bigl\{A_{i,\sigma(i)} : i \in [n]\bigr\}$, and let $P^{(t)}$ be the permutation matrix for which $P^{(t)}_{i,\sigma(i)} = 1$ for each $i \in [n]$. 
Update $A \gets \bigl(A - u^{(t)} P^{(t)}\bigr)$, and update $N$ to the number of non-zero elements of $A$(which is smaller by at least $1$).

Return $\bigl(u^{(1)},P^{(1)}\bigr)$, ... $\bigl(u^{(t)},P^{(t)}\bigr)$, representing the decomposition $\sum_{i\in[t]} u^{(i)} P^{(i)}$ of the input.


[1] Extremal Combinatorics: With Applications in Computer Science by Stasys Jukna