lft_llt2d - 2D Legendre-Fenchel conjugate, LLT algorithm
Numerically compute the discrete Legendre transform on the grid Sr x Sc, given a function f(x,y) defined on a grid Xr x Xc, using the LLT1d algorithm to compute the conjugate in one dimension, then to compute it in the other dimension. If n==length(Xr)==length(Xc)==length(Sr)==length(Sc), this function calls LLT1d n times in one dimension and then n times in the other dimension (2*n^2), giving a linear running time with respect to the O(n^2) input size.
The conjugate of a function in R^2 can be factored to several conjugates which are elements of R.
f*(s(1),s(2)) = Sup [x(1)y(1) + x(2)y(2) - f(x(1),x(2))] x(1),x(2) = Sup [s(1)x(1) + Sup[s(2)x(2) - f(x(1),x(2))]] x(1) x(2)
Xr=(-2:0.1:2)'; Xc=(-2:0.1:2)'; Sr=(-2:0.1:2)'; Sc=(-2:0.1:2)'; deff('[z]=f(Xr,Xc)',['z= Xr^2 + Xc^2']); z=eval3d(f,Xr,Xc); result_llt = lft_llt2d (Xr, Xc, z, Sr, Sc, 0); //llt method result_direct = lft_direct2d (Xr, Xc, z, Sr, Sc, 1); //direct method
Mike Trienis, University of British Columbia, BC, Canada