Abstract
A new algorithm for the computation of discrete Legendre transforms is discussed. Classical solutions have a running time proportional toN 2d, whereN is the size of the spatial grid andd is the space dimension. The new algorithm has a running timeO((N log2 N) d). A general application of this algorithm is to the weak solutions of hyperbolic systems of conservation laws as considered by Lax (1973,Hyperbolic Systems of Conservation Laws and the Mathematical Theory of Shock Waves, S.I.A.M.). The potential of the method is illustrated on the “adhesion model,” a multi-dimensional version of the Burgers equation, used to study the formation of large-scale structures in cosmology.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arnold, V. I. (1983).Geometrical Methods in the Theory of Ordinary Differential Equations, Springer-Verlag, Berlin.
Aurell, E. (1992). Private communication.
Benzi, R., Paladin, G., Parisi, G., and Vulpiani, A. (1984) On the multifractal nature of fully developed turbulence and chaotic systems,J. Phys. A 17, 3521.
Brachet, M., Meiron, D. I., Orszag, S. A., Nickel B. G., Morf, R. H., and Frisch, U. (1983). Small-scale structure of the Taylor-Green vortex,J. Fluid Mech. 130, 411.
Brenier, Y. (1989). Un algorithme rapide pour le calcul de transformées de Legendre-Fenchel discrètes,C.R. Acad. Sci. Paris 308, 587–589.
Burgers, J. M. (1929). On the application of statistical, mechanics to the theory of turbulent fluid motion,Proc. Roy. Neth. Acad. Soc. 32, 643.
Burgers, J. M. (1974).The Nonlinear Diffusion Equation, D. Reidel Publ. Co.
Cole, J. D. (1951). On a quasi-linear parabolic equation occuring in aerodynamics,Quart. Appl. Math. 9, 225.
Corrias, L. (1993). Fast Legendre-Fenchel transform and applications to Hamilton-Jacobi equation and conservation laws,SIAM J. Num. Anal., submitted.
Fournier, J. D., and Frisch, U. (1983). L'équation, de Burgers déterministe et statistique,J. de Méc. Théor. et Appl 2, 699.
Gurbatov, S. N., and Saichev, A. I. (1984).Radiophys. Quant. Electr. 27, 4, 303;Izv. VUZ Radiofiz. (USSR)27, 456.
Gurbatov, S., Malakhov, A., and Saichev, A. (1991).Nonlinear Random Waves and Turbulence in Nondispersive Media: Waves, Rays, Particles, Manchester University Press.
Halsey, T. C., Jensen, M. H., Kadanoff, L. P. Procaccia, I., and Shraiman, B. (1986). Fractal measures and their singularities: the characterization of strange sets.Phys. Rev. A 33, 1141.
Hopf, E. (1950). The partial differential equationu t +uu x =u xx ,Comm. Pure Appl. Mech. 3, 201.
Kardar, M., Parisi, G., and Zhang, Y. C. (1986). Dynamical scaling of growing interfaces,Phys. Rev. Lett. 56, 889.
Kida, S. (1979). Asymptotic properties of Burgers turbulence,J. Fluid Mech. 93, 337.
Kuramoto, Y. (1985):Chemical Oscillations, Waves and Turbulence Springer-Verlag, Berlin.
Lax, P. D. (1973).Hyperbolic Systems of Conservation Laws and the Mathematical Theory of Shock Waves, S.I.A.M.
Musha, T., Kosugi, Y., Matsumoto, G., and Suzuki, M. (1981). Modulation of the time relation of action potential impulses propagating along an axon,IEEE Trans. Biomedical Eng. BME-28, 616–623.
Parisi, G., and Frisch, U. (1985). In Ghil, M., Benzi, R., and Parisi, G. (eds.),Turbulence and Predictability in Geophysical Fluid Dynamics, p. 84, Proc. Int'l. School of Physics “E. Fermi,” Varenna, Italy, 1983.
Schwartz, M., and Edwards, S. F. (1992). Nonlinear deposition: a new approach,Europhys. Lett. 20, 301–305.
Shandarin, S. F., and Zeldovich, Ya. B. (1989). The large-scale structure of the universe: Turbulence, intermittency, structures in a self-gravitating medium,Rev. Mod. Phys. 61, 185–220.
She, Z. S., Aurell, E., and Frisch, U. (1992). The inviscid Burgers equation with initial data of Brownian type,Comm. Math. Phys. 148, 623.
Sinai, Ya. G. (1992). Statistics of shock waves in solutions of Burger's equation in the limit of vanishing viscosity,Comm. Math. Phys. 148, 601.
Vergassola, M., Dubrulle, B., Frisch, U., and Noullez, A. (1994). Burgers' equation, devil's staircases and the mass distribution for large-scale structures,Astron. & Astrophys. 289, 325–356.
Zeldovich, Ya. B. (1970). Gravitational Instability: An approximate theory for large density perturbations,Astron. & Astrophys. 5, 84–89.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Noullez, A., Vergassola, M. A fast Legendre transform algorithm and applications to the adhesion model. J Sci Comput 9, 259–281 (1994). https://doi.org/10.1007/BF01575032
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01575032