**Summary.** Using your favourite $O(n^d)$ algorithm for finding a matching in graphs on $O(n)$ matrices, there is a simple algorithm using  $O(n^{d+2})$ operations over the reals for decomposing doubly-stochastic matrices.

**Details.** 
The following proof of the Birkhoff–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 > 0$:
   1. Set $t \gets t + 1$.
   1. For each $i \in [n]$: let $S_i = \bigl\{ j \in [n]: A_{ij} > 0 \bigr\}$.
   2. Find a bijection $\sigma: [n] \to [n]$ such that $\sigma(i) \in S_i$<br>(such a bijection exists, and can be found efficiently, by Hall's Marriage criterion).
   3. Let $u^{(t)} = \max\,\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]$. 
   4. Update $A \gets \bigl(A - u^{(t)} P^{(t)}\bigr)$, and update $N$ to the number of non-zero elements of $A$<br>(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](https://books.google.co.uk/books?id=8-ipCAAAQBAJ&lpg=PA58&ots=aoNEzv1fh_&dq=decomposing%20doubly%20stochastic%20matrices&pg=PA58#v=onepage&q=decomposing%20doubly%20stochastic%20matrices&f=false) by Stasys Jukna