<< gph_version | CCA (Computational Convex Analysis) | pl_lft_llt_2d >>

CCA (Computational Convex Analysis) >> CCA (Computational Convex Analysis) > pl_lft_llt

# pl_lft_llt

Legendre-Fenchel conjugate, LLT algorithm

### Calling Sequence

    Conj = pl_lft_llt(X,Y,S)
    Conj = pl_lft_llt(X,Y,S,isConvex)
    Conj = pl_lft_llt(X,Y,S,isConvex,fusionopt)

### Parameters

X

  column vector. A grid of points on which the function is sampled.

Y

  column vector. The value of the function on the grid X: usually Y(i)=f(X(i)) for some function f.

S

  column vector. The grid on which we want to compute the conjugate: f* is evaluated on S.

isConvex

  Optional. boolean. Whether or not the dataset (X,Y) is known to be convex. If false or omitted, pl_bb is first applied to the data.

fusionopt

  Optional. integer. Select the implementation of the fusion algorithm. fusionopt=1 (or omitted) selects _pl_fusionsci, a fast implementation using scilab syntax but with nonlinear complexity. Any over value selects the _pl_fusion implementation, a (slower) loop-based implementation that runs in linear-time.

Conj

  column vector. Contains the value of the conjugate f* of the function f evaluated on at the points S(j). In other words: Conj(j) = Max(S(j) * X(i) - Y(i) | over all indexes i)

### Description

Compute numerically the discrete Legendre transform of a set of planar points (X(i),Y(i)) at slopes S, i.e.,

    Conj(j)=max[S(j)*X(i)-Y(i)].
             i

It uses the Linear-time Legendre Transform (LLT) algorithm for a linear-time worst-case complexity theta(n+m) with n=length(X)=length(Y) and m=length(S). The LLT algorithm first compute the lower convex envelope of the points (X(i),Y(i)), and then merge two increasing sequences.

### Examples

    X=[-5:0.5:5]';
    Y=X.^2;
    S=(Y(2:size(Y,1))-Y(1:size(Y,1)-1))./(X(2:size(X,1))-X(1:size(X,1)-1));
    Conj=pl_lft_llt(X,Y,S);
    Conj2=pl_lft_llt(X,Y,S,1);

### See Also

- pl_lft_llt_d
- pl_lft_direct

### Authors

`Yves Lucet`, University of British Columbia, BC, Canada

### Bibliography

Y. Lucet, 1997, Faster than the fast Legendre transform, the linear-time Legendre transform, Numerical Algorithms, 16(2):171-185. Code in Netlib.

### Used Functions

The convex hull computation is performed with the function pl_bb. The core of the algorithm, which amounts to merging two increasing sequences, is performed with the function _pl_fusion or _pl_fusionsci depending on the value of the parameter fusionopt.

<< gph_version | CCA (Computational Convex Analysis) | pl_lft_llt_2d >>