  We present an iterative method to efficiently solve the optimal
transportation problem for a class of strictly convex costs which includes
quadratic and p-power costs. Given two probability measures supported on a
discrete grid with n points, we compute the optimal map using O(n) storage
space and O(n log(n)) operations per iteration, with an approximately
exponential convergence rate. Our approach allows us to solve optimal
transportation problems on spatial grids as large as 4096x4096 and 384x384x384
in a matter of minutes.
