Abstract
A new algorithm to compute the Legendre–Fenchel transform is proposed and investigated. The so-called Linear-time Legendre Transform (LLT) improves all previously known Fast Legendre Transform algorithms by reducing their log-linear worst-case time complexity to linear. Since the algorithm amounts to computing several convex hulls and sorting, any convex hull algorithm well-suited for a particular problem gives a corresponding LLT algorithm. After justifying the convergence of the Discrete Legendre Transform to the Legendre–Fenchel transform, an extended computation time complexity analysis is given and confirmed by numerical tests. Finally, the LLT is illustrated with several examples and a LLT MATLAB package is described.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Y. Brenier, Un algorithme rapide pour le calcul detransformée de Legendre-Fenchel discrètes, C. R. Acad. Sci. Paris Sér. I Math. 308 (1989) 587–589.
R.M. Corless, G.H. Gonnet, D.E.G. Hare, D.J. Jeffrey and D.E. Knuth, On the Lambert W function, Adv. Comput. Math. 5 (1996) 329–359.
L. Corrias, Fast Legendre-Fenchel transform and applications to Hamilton-Jacobi equations and conservation laws, SIAM J. Numer. Anal. 33 (1996) 1534–1558.
H. Edelsbrunner, Algorithms in Combinatorial Geometry,EATC Monographs on Theoretical Computer Science (Springer, Berlin, 1987).
J.-B. Hiriart-Urruty, Lipschitz r-continuity of the approximatesubdifferential of a convex function, Math. Scand. 47 (1980) 123–134.
J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysisand Minimization Algorithms, A Series of Comprehensive Studies in Mathematics (Springer, Berlin, 1993).
D.E. Knuth, The Art of ComputerProgramming, Vol. 3: Sorting and Searching, Series in Computer Science and Information Processing (Addison-Wesley, Reading, MA, 1973).
Y. Lucet, A fast computational algorithm for the Legendre-Fenchel transform, Comput. Optim. Appl. 6 (1996) 27–57.
Y. Lucet, Latransformée de Legendre-Fenchel et la convexifiée d'une fonction: algorithmes rapides de calcul, analyse et régularité du second ordre, Ph.D. thesis, Laboratoire Approximation et Optimisation, Université Paul Sabatier, 118 Route de Narbonne, 31062 Toulouse Cedex 4, France (February 1997).
A. Noullez and M. Vergassola, A fastLegendre transform algorithm and applications to the adhesion model, J. Sci. Comput. 9 (1994) 259–281.
P. Plazanet, Contributionà l'analyse des fonctions convexes et des différences de fonctions convexes. Applications à l'optimisation et à la théorie des E.D.P., Ph.D. thesis, Laboratoire d'Analyse Numérique, Université Paul Sabatier, 118 Route de Narbonne, 31062 Toulouse Cedex 4, France (1990).
F.P. Preparata and M.I. Shamos,Computational Geometry, Texts and Monographs in Computer Science (Springer, Berlin, 3rd ed., 1990).
R.T. Rockafellar, ConvexAnalysis (Princeton University Press, Princeton, 1970).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lucet, Y. Faster than the Fast Legendre Transform, the Linear-time Legendre Transform. Numerical Algorithms 16, 171–185 (1997). https://doi.org/10.1023/A:1019191114493
Issue Date:
DOI: https://doi.org/10.1023/A:1019191114493