Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-18T09:22:28.245Z Has data issue: false hasContentIssue false
  • English
  • Français

A Multilevel Method for the Solution of Time Dependent Optimal Transport

Published online by Cambridge University Press:  03 March 2015

Eldad Haber  and
Raya Horesh
Eldad Haber*
Affiliation:
Department of Mathematics & Department of Earth and Ocean Science, The University of British Columbia, Vancouver, BC, Canada; IBM research, NY, USA
Raya Horesh
Affiliation:
Department of Mathematics & Department of Earth and Ocean Science, The University of British Columbia, Vancouver, BC, Canada; IBM research, NY, USA
*
*Email address: [email protected] (E. Haber)
Get access

Abstract

In this paper we present a new computationally efficient numerical scheme for the minimizing flow for the computation of the optimal L2 mass transport mapping using the fluid approach. We review the method and discuss its numerical properties. We then derive a new scaleable, efficient discretization and a solution technique for the problem and show that the problem is equivalent to a mixed form formulation of a nonlinear fluid flow in porous media. We demonstrate the effectiveness of our approach using a number of numerical experiments.

Keywords

15A1265F1065F15Optimal mass transportinverse problemsstaggered grids
Type
Research Article
Information
Numerical Mathematics: Theory, Methods and Applications , Volume 8 , Issue 1 , February 2015 , pp. 97 - 111
Copyright
Copyright © Global-Science Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Ascher, U.. Numerical Methods for Evolutionary Differential Equations, SIAM, Philadelphia 2008.CrossRefGoogle Scholar
[2]Ambrosio, L.. Lecture Notes on Optimal Transport Theory, CIME Series of Springer Lecture Notes, Euro Summer School Mathematical Aspects of Evolving Interfaces, Madeira, Portugal, Springer-Verlag, New York, 2000.Google Scholar
[3]Angenent, S.. Haker, S. and Tannenbaum, A.. Minimizing flows for the Monge-Kantorovich problem, SIAM J. Math. Analysis 35 (2003), pp. 61–97.CrossRefGoogle Scholar
[4]Bear, J.. Dynamics of Fluids in Porous Media, Dover Publications, New York, (1972).Google Scholar
[5]Benamou, J.D. and Brenier, Y.. A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numer. Math., 84 (2000), pp. 375–393.CrossRefGoogle Scholar
[6]Benzi, M., Golub, G.H., and Liesen, J.. Numerical solution of saddle point problems, Acta Numerica, 14 (2005), pp. 1–137.CrossRefGoogle Scholar
[7] Edited by Lorenz, T. Biegler, Ghattas, Omar, Heinkenschloss, Matthias, Keyes, David, and Waanders, Bart van Bloemen. Real-Time PDE-Constrained Optimization, SIAM Philadelphia (2007).Google Scholar
[8]Borz, A. and Kunisch, K.. A globalization strategy for the multigrid solution of elliptic optimal control problems, Optimization Methods and Software, 21(3) (2006), pp. 445–459.CrossRefGoogle Scholar
[9]Brezzi, F. and Fortin, M.. Mixed and Hybrid Finite Element Methods, Springer-Verlag, (1991).Google Scholar
[10]Byrd, R.H., Curtis, F.E., and Nocedal, J.. An Inexact SQP Method for Equality Constrained Optimization, SIAM J. on Optimization, 19 (2008), pp. 351–369.CrossRefGoogle Scholar
[11]Chartrand, R., Vixie, K., Wohlberg, B., and Bollt, E.. A gradient descent solution to the Monge-Kantorovich problem, submitted to SIAM J. Sci. Comput., (2005).Google Scholar
[12]Cullen, M. and Purser, R.. An extended Lagrangian theory of semigeostrophic frontogenesis, J. Atmos. Sci., 41 (1984), pp. 1477–1497.2.0.CO;2>CrossRefGoogle Scholar
[13]Dean, E.J., Glowinski, R.. Numerical methods for fully nonlinear elliptic equations of the Monge-Amp‘ere type, to appear, Comput. Methods Appl. Mech (2008).Google Scholar
[14]Delzanno, G.L., Chacon, L., Finn, J.M., Chung, Y., and Lapenta, G.. An optimal robust equidis-tribution method for two-dimensional grid adaptation based on Monge-Kantorovich optimization, Journal of Computational Physics archive, 227(23), (2008), pp. 9841–9864.CrossRefGoogle Scholar
[15]Evans, L.C.. Partial differential equations and Monge-Kantorovich mass transfer, in Current Developments in Mathematics, International Press, Boston, MA, 1999, pp. 65–126.Google Scholar
[16]Fletcher, R., Leyffer, S., and Ph.Toint, L.. A Brief History of Filter Methods, SIAG/Optimization Views-and-News, 18 (2007).Google Scholar
[17]Gunzburger, M.D.. Prespectives in flow control and optimization, SIAM, Philadelphia, 2003.Google Scholar
[18]Haber, E. and Ascher, U. and Oldenburg, D.. On Optimization Techniques for Solving Nonlinear Inverse Problems, Inverse Problems, 16 (2000), pp. 1263–1280.CrossRefGoogle Scholar
[19]Haber, E., Rehman, T., Tannenbaum, A.. An Efficient Numerical Method for the Solution of the L2 Optimal Mass Transfer Problem, to appear, SIAM J. on Scientific Computing.Google Scholar
[20]Jenkins, E.W., Kelley, C.T., Miller, C.T., and Kees, C.E.. An Aggregation-based Domain Decomposition Preconditioner for Groundwater Flow, SIAM J. Sci. Comp., (23) (2001), pp. 430–441.CrossRefGoogle Scholar
[21]Kantorovich, L.V.. On a problem of Monge, Uspekhi Mat. Nauk., 3 (1948), pp. 225–226.Google Scholar
[22]Moulton, J.D., Dendy, J.E., and Hyman, J.M.. The black box multigrid numerical homogenization algorithm, J. Comput. Phys., 141 (1998) pp. 1–29.Google Scholar
[23]Nicolaides, R.A.. Existence, Uniqueness and Approximation for Generalized Saddle Point Problems, SIAM Journal on Numerical Analysis, 18 (1982), pp. 349–357.CrossRefGoogle Scholar
[24]Oberman, A.. Wide stencil finite difference schemes for the elliptic Monge-Ampere equation and functions of the eigenvalues of the Hessian, Discrete and Continuous Dynamical Systems series B (DCDS B), 10 (2008), pp. 221–238.CrossRefGoogle Scholar
[25]Oliker, V. and Prussner, L.. On the numerical solution of the equation and its discretizations, Numerische Mathematik, 54 (1988), pp. 271–293.CrossRefGoogle Scholar
[26]Rachev, S. and Rüschendorf, L.. Mass Transportation Problems, Vol. I, Probab. Appl., Springer-Verlag, New York, 1998.Google Scholar
[27]Rubinstein, J. and Wolansky, G.. Intensity control with a free-form lens, J. Opt. Soc. Am. A, 24 (2007), pp. 463–469.CrossRefGoogle ScholarPubMed
[28]Ruge, J., Stben, K.. Algebraic multigrid, in: McCormick, S.F.. (Ed.), Multigrid Methods, Frontiers in Applied Mathematics, (3), SIAM, Philadelphia (1987), pp. 73–130.CrossRefGoogle Scholar
[29]Saad, Y. and Schultz, M.H.. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAMJ. Sci. Stat. Comput., 7 (1986), pp. 856–869.CrossRefGoogle Scholar
[30]Trottenberg, U., Oosterlee, C., and Schulle, A.. Multigrid, Academic Press, 2001.Google Scholar
[31]Villani, C.. Topics in Optimal Transportation, Graduate Studies in Mathematics, vol. 58, AMS, Providence, RI, 2003.CrossRefGoogle Scholar
[32]Volkwein, S.. Mesh-Independence of Lagrange-SQP Methods with Lipschitz-Continuous Lagrange Multiplier Updates, Optimization Methods and Software, 17 (2002), pp. 77–111.CrossRefGoogle Scholar