Faster than the Fast Legendre Transform, the Linear-time Legendre Transform
Faster than the Fast Legendre Transform, the Linear-time Legendre Transform
复制标题
线性时间勒让德变换比快速勒让德变换更快
作者：
Y. Lucet
提出并研究了一种计算Legendre-Fenchel变换的新算法。所谓的线性时间勒让德变换（LLT）改进了所有先前已知的快速勒让德变换算法，通过将其对数线性最坏情况的时间复杂度降低到线性。由于该算法相当于计算几个凸壳和排序，任何凸船体算法非常适合于一个特定的问题，给出了相应的LLT算法。在证明了离散Legendre变换到Legendre-Fenchel变换的收敛性之后，给出了一个扩展的计算时间复杂度分析，并通过数值试验加以证实。最后，LLT说明了几个例子和LLT MATLAB软件包描述。
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.