A fast, large-scale optimal transport algorithm for holographic beam shaping

Optimal transport methods have recently established state-of-the-art accuracy and efficiency for holographic laser beam shaping. However, use of such methods is hindered by severe O(N²) memory and O(N²) time requirements for large-scale input or output images with N total pixels. Here we leverage the dual formulation of the optimal transport problem and the separable structure of the cost to implement algorithms with greatly reduced O(N) memory and O(Nlog⁡N) to O(N^3/2) time complexity. These algorithms are parallelizable and can solve megapixel-scale beam shaping problems in tens of seconds on a CPU or seconds on a GPU.