A linear-time approximate convex envelope algorithm using the double Legendre-Fenchel transform with application to phase separation (Q2515072)

The authors study the double discrete Legendre-Fenchel transform (LFT) to approximate the convex envelope of a given function. The first part of this paper presents the convergence results on the double discrete LFT in the multivariate case which use [\textit{L. Corrias}, SIAM J. Numer. Anal. 33, No. 4, 1534--1558 (1996; Zbl 0856.49023)] as a starting point. The convergence proof requires the study of the dual grid on which the second discrete LFT is applied; its choice has great impact on the accuracy of the resulting approximation of the convex envelope. In the second part, the authors give an improvement (both in time and accuracy) of the standard algorithm based on a change in the factorization order for the second discrete LFT. Another improvement consists in merging (through a maximum operation ) the results obtained after the two possible changes in the factorization order. The numerical results illustrating the benefits of the proposed approach are presented. An efficient handling of dual grids of arbitrary length is devised. In the last part, the authors apply the algorithm to the study of phase separation in non-ideal ionic solutions.