na13

Faster than the fast Legendre transform, the linear-time Legendre transform. An algorithm is proposed for numerical computation of the Legendre-Fenchel transform u∗(s)=supx[⟨s,x⟩−u(x)] with a linear-time complexity in arbitrary space dimensions. A corresponding MATLAB package is described and illustrated with examples. (netlib numeralgo na13)