Consideramos la solución numérica del transporte óptimo discreto multi-marginal (MOT) mediante el algoritmo de Sinkhorn. En general, el algoritmo de Sinkhorn sufre de la maldición de la dimensionalidad con respecto al número de márgenes. Si la función de coste MOT se desacopla según un árbol o círculo, su complejidad es lineal en el número de medidas marginales. En este caso, aceleramos la convolución con el núcleo radial requerido en el algoritmo de Sinkhorn a través de métodos rápidos de Fourier no uniformes. Cada paso del algoritmo de Sinkhorn acelerado propuesto con una función de coste estructurada en árbol tiene una complejidad de en lugar de la clásica para operaciones de matriz-vector directas, donde es el número de márgenes y cada medida marginal está soportada en, a lo sumo, puntos. En el caso de una función de coste estructurada en círculo, la complejidad mejora de a . Esto se confirma a través de experimentos numéricos.