<?xml version="1.0" encoding="ISO-8859-1"?><refentry xmlns="http://docbook.org/ns/docbook" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:svg="http://www.w3.org/2000/svg" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:db="http://docbook.org/ns/docbook" version="5.0-subset Scilab" xml:lang="en" xml:id="pl_lft_llt"><info><pubdate>04-Apr-2006</pubdate></info><refnamediv><refname>pl_lft_llt</refname><refpurpose>Legendre-Fenchel conjugate, LLT algorithm</refpurpose></refnamediv>
  
   
  
   
  
   
  
   
  
   

  
   <refsynopsisdiv><title>Calling Sequence</title><synopsis>Conj = pl_lft_llt(X,Y,S)
Conj = pl_lft_llt(X,Y,S,isConvex)
Conj = pl_lft_llt(X,Y,S,isConvex,fusionopt)</synopsis></refsynopsisdiv>

  
   <refsection><title>Parameters</title>
  
      <variablelist>

    
         <varlistentry>
    
            <term>X</term>
    
            <listitem>
       
               <para>column vector. A grid of points on which the function is sampled.
       </para>
    
            </listitem>
    
         </varlistentry>

    
         <varlistentry>
    
            <term>Y</term>
    
            <listitem>
       
               <para>column vector. The value of the function on the grid X: usually Y(i)=f(X(i)) for some function f.
       </para>
    
            </listitem>
    
         </varlistentry>

    
         <varlistentry>
    
            <term>S</term>
    
            <listitem>
       
               <para>column vector. The grid on which we want to compute the conjugate: f* is evaluated on S.
       </para>
    
            </listitem>
    
         </varlistentry>

    
         <varlistentry>
	    
            <term>isConvex</term>
	    
            <listitem>
		    
               <para>Optional. boolean. Whether or not the dataset (X,Y) is known to be convex.  If false or omitted, <link linkend="pl_bb">pl_bb</link> is first applied to the data.
		    </para>
	    
            </listitem>
    
         </varlistentry>

    
         <varlistentry>
	    
            <term>fusionopt</term>
	    
            <listitem>
		    
               <para>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.
		    </para>
	    
            </listitem>
    
         </varlistentry>

    
         <varlistentry>
    
            <term>Conj</term>
    
            <listitem>
       
               <para>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)
       </para>
    
            </listitem>
    
         </varlistentry>
  
      </variablelist>
  
   </refsection>
 
  
   <refsection><title>Description</title>
     
         <para>
     Compute numerically the discrete Legendre transform
     of a set of planar points (X(i),Y(i)) at 
     slopes S, i.e., <!--<programlisting><![CDATA[
        Conj(j)=max[S(j)*X(i)-Y(i)].
                 i
]]></programlisting>-->
			<para>
				<inlinemediaobject>
					<imageobject>
						<imagedata fileref="pl_ImagesOfEquationsByLatex/pl_lft_llt/pl_lft_llt_1.png"/>
					</imageobject>
				</inlinemediaobject>
			</para>
			<para>
     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.
			</para>
     </para>
  
   </refsection>

  
   <refsection><title>Examples</title><programlisting role="example"><![CDATA[
    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);
  ]]></programlisting></refsection>

  
   <refsection><title>See Also</title><simplelist type="inline">
    
      <member>
         <link linkend="pl_lft_llt_d">pl_lft_llt_d</link>
      </member>
    
      <member>
         <link linkend="pl_lft_direct">pl_lft_direct</link>
      </member>
  
   </simplelist></refsection>

  
   <refsection><title>Authors</title><para>
	  
      <literal>Yves Lucet</literal>, University of British Columbia, BC, Canada
  </para></refsection>

  
   <refsection><title>Bibliography</title>
    
      <para>
	Y. Lucet, 1997, Faster than the fast Legendre transform, the linear-time Legendre transform, Numerical Algorithms, 16(2):171-185. Code in Netlib.
    </para>
  
   </refsection>

  
   <refsection><title>Used Functions</title>
     
      <para>
     The convex hull computation is performed with the function <link linkend="pl_bb">pl_bb</link>. The core of the algorithm, which amounts to merging two increasing sequences, is performed with the function <link linkend="_pl_fusion">_pl_fusion</link> or <link linkend="_pl_fusionsci">_pl_fusionsci</link> depending on the value of the parameter fusionopt.
     </para>
  
   </refsection>

</refentry>
