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 <i>O</i>(<i>N</i>²) memory and <i>O</i>(<i>N</i>²) time requirements for large-scale input or output images with <i>N</i> 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 <i>O</i>(<i>N</i>) memory and <i>O</i>(<i>N</i><i>log</i>⁡<i>N</i>) to <i>O</i>(<i>N</i>^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.