{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:11:12Z","timestamp":1771035072740,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T00:00:00Z","timestamp":1677542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T00:00:00Z","timestamp":1677542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003385","name":"Georg-August-Universit\u00e4t G\u00f6ttingen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003385","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer. Math."],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Large optimal transport problems can be approached via domain decomposition, i.e.\u00a0by iteratively solving small partial problems independently and in parallel. Convergence to the global minimizers under suitable assumptions has been shown in the unregularized and entropy regularized setting and its computational efficiency has been demonstrated experimentally. An accurate theoretical understanding of its convergence speed in geometric settings is still lacking. In this article we work towards such an understanding by deriving, via<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varGamma $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u0393<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-convergence, an asymptotic description of the algorithm in the limit of infinitely fine partition cells. The limit trajectory of couplings is described by a continuity equation on the product space where the momentum is purely horizontal and driven by the gradient of the cost function. Global optimality of the limit trajectories remains an interesting open problem, even when global optimality is established at finite scales. Our result provides insights about the efficiency of the domain decomposition algorithm at finite resolutions and in combination with coarse-to-fine schemes.<\/jats:p>","DOI":"10.1007\/s00211-023-01347-x","type":"journal-article","created":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T15:03:13Z","timestamp":1677596593000},"page":"451-492","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Asymptotic analysis of domain decomposition for optimal transport"],"prefix":"10.1007","volume":"153","author":[{"given":"Mauro","family":"Bonafini","sequence":"first","affiliation":[]},{"given":"Ismael","family":"Medina","sequence":"additional","affiliation":[]},{"given":"Bernhard","family":"Schmitzer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,2,28]]},"reference":[{"issue":"3","key":"1347_CR1","first-page":"439","volume":"17","author":"L Ambrosio","year":"1990","unstructured":"Ambrosio, L.: Metric space valued functions of bounded variation. Ann. Sc. Norm. Super. Pisa Cl. Sci. Ser. 4 17(3), 439\u2013478 (1990)","journal-title":"Ann. Sc. Norm. Super. Pisa Cl. Sci. Ser. 4"},{"key":"1347_CR2","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198502456.001.0001","volume-title":"Functions of Bounded Variation and Free Discontinuity Problems","author":"L Ambrosio","year":"2000","unstructured":"Ambrosio, L., Fusco, N., Pallara, D.: Functions of Bounded Variation and Free Discontinuity Problems. Courier Corporation (2000)"},{"issue":"1","key":"1347_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1137\/S0036141002410927","volume":"35","author":"S Angenent","year":"2003","unstructured":"Angenent, S., Haker, S., Tannenbaum, A.: Minimizing flows for the Monge\u2013Kantorovich problem. SIAM J. Math. Anal. 35(1), 61\u201397 (2003)","journal-title":"SIAM J. Math. Anal."},{"issue":"6","key":"1347_CR4","doi-asserted-by":"publisher","first-page":"1808","DOI":"10.1137\/0732082","volume":"32","author":"J-D Benamou","year":"1994","unstructured":"Benamou, J.-D.: A domain decomposition method for the polar factorization of vector-valued mappings. SIAM J. Numer. Anal. 32(6), 1808\u20131838 (1994)","journal-title":"SIAM J. Numer. Anal."},{"issue":"1","key":"1347_CR5","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.jcp.2013.12.015","volume":"260","author":"J-D Benamou","year":"2014","unstructured":"Benamou, J.-D., Froese, B.D., Oberman, A.M.: Numerical solution of the optimal transportation problem using the Monge\u2013Amp\u00e8re equation. J. Comput. Phys. 260(1), 107\u2013126 (2014)","journal-title":"J. Comput. Phys."},{"key":"1347_CR6","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1007\/s00211-020-01127-x","volume":"145","author":"RJ Berman","year":"2020","unstructured":"Berman, R.J.: The Sinkhorn algorithm, parabolic optimal transport and geometric Monge\u2013Amp\u00e8re equations. Numer. Math. 145, 771\u2013836 (2020)","journal-title":"Numer. Math."},{"key":"1347_CR7","series-title":"Wiley Series in Probability and Statistics","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316962","volume-title":"Convergence of Probability Measures","author":"P Billingsley","year":"1999","unstructured":"Billingsley, P.: Convergence of Probability Measures. Wiley Series in Probability and Statistics, 2nd edn. Wiley (1999)","edition":"2"},{"key":"1347_CR8","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/s00211-021-01245-0","volume":"149","author":"M Bonafini","year":"2021","unstructured":"Bonafini, M., Schmitzer, B.: Domain decomposition for entropy regularized optimal transport. Numer. Math. 149, 819\u2013870 (2021). https:\/\/doi.org\/10.1007\/s00211-021-01245-0","journal-title":"Numer. Math."},{"issue":"4","key":"1347_CR9","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1002\/cpa.3160440402","volume":"44","author":"Y Brenier","year":"1991","unstructured":"Brenier, Y.: Polar factorization and monotone rearrangement of vector-valued functions. Commun. Pure Appl. Math. 44(4), 375\u2013417 (1991)","journal-title":"Commun. Pure Appl. Math."},{"issue":"2","key":"1347_CR10","doi-asserted-by":"publisher","first-page":"1385","DOI":"10.1137\/15M1050264","volume":"49","author":"G Carlier","year":"2017","unstructured":"Carlier, G., Duval, V., Peyr\u00e9, G., Schmitzer, B.: Convergence of entropic schemes for optimal transport and gradient flows. SIAM J. Math. Anal. 49(2), 1385\u20131418 (2017)","journal-title":"SIAM J. Math. Anal."},{"key":"1347_CR11","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF01582220","volume":"67","author":"R Cominetti","year":"1992","unstructured":"Cominetti, R., San Martin, J.: Asymptotic analysis of the exponential penalty trajectory in linear programming. Math. Program. 67, 169\u2013187 (1992)","journal-title":"Math. Program."},{"key":"1347_CR12","unstructured":"Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transportation distances. In: Advances in Neural Information Processing Systems, vol. 26 (NIPS 2013), pp. 2292\u20132300 (2013)"},{"key":"1347_CR13","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1016\/0024-3795(89)90490-4","volume":"114\u2013115","author":"J Franklin","year":"1989","unstructured":"Franklin, J., Lorenz, J.: On the scaling of multidimensional matrices. Linear Algebra Appl. 114\u2013115, 717\u2013735 (1989)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"1347_CR14","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF02392620","volume":"177","author":"W Gangbo","year":"1996","unstructured":"Gangbo, W., McCann, R.J.: The geometry of optimal transportation. Acta Math. 177(2), 113\u2013161 (1996)","journal-title":"Acta Math."},{"issue":"19","key":"1347_CR15","doi-asserted-by":"publisher","first-page":"4325","DOI":"10.1093\/imrn\/rnr188","volume":"2012","author":"Y-H Kim","year":"2012","unstructured":"Kim, Y.-H., Streets, J., Warren, M.: Parabolic optimal transport equations on manifolds. Int. Math. Res. Not. 2012(19), 4325\u20134350 (2012)","journal-title":"Int. Math. Res. Not."},{"key":"1347_CR16","first-page":"127","volume":"672","author":"J Kitagawa","year":"2012","unstructured":"Kitagawa, J.: A parabolic flow toward solutions of the optimal transportation problem on domains with boundary. J. Reine Angew. Math. 672, 127\u2013160 (2012)","journal-title":"J. Reine Angew. Math."},{"key":"1347_CR17","doi-asserted-by":"publisher","first-page":"2603","DOI":"10.4171\/JEMS\/889","volume":"21","author":"J Kitagawa","year":"2019","unstructured":"Kitagawa, J., M\u00e9rigot, Q., Thibert, B.: Convergence of a Newton algorithm for semi-discrete optimal transport. J. Eur. Math. Soc. 21, 2603 (2019)","journal-title":"J. Eur. Math. Soc."},{"issue":"4","key":"1347_CR18","doi-asserted-by":"publisher","first-page":"1879","DOI":"10.1016\/j.jfa.2011.11.026","volume":"262","author":"C L\u00e9onard","year":"2012","unstructured":"L\u00e9onard, C.: From the Schr\u00f6dinger problem to the Monge\u2013Kantorovich problem. J. Funct. Anal. 262(4), 1879\u20131920 (2012)","journal-title":"J. Funct. Anal."},{"issue":"6","key":"1347_CR19","doi-asserted-by":"publisher","first-page":"1693","DOI":"10.1051\/m2an\/2015055","volume":"49","author":"B L\u00e9vy","year":"2015","unstructured":"L\u00e9vy, B.: A numerical algorithm for L2 semi-discrete optimal transport in 3D. ESAIM Math. Model. Numer. Anal. 49(6), 1693\u20131715 (2015)","journal-title":"ESAIM Math. Model. Numer. Anal."},{"issue":"5","key":"1347_CR20","doi-asserted-by":"publisher","first-page":"1583","DOI":"10.1111\/j.1467-8659.2011.02032.x","volume":"30","author":"Q M\u00e9rigot","year":"2011","unstructured":"M\u00e9rigot, Q.: A multiscale approach to optimal transport. Comput. Gr. Forum 30(5), 1583\u20131592 (2011)","journal-title":"Comput. Gr. Forum"},{"issue":"5\u20136","key":"1347_CR21","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1561\/2200000073","volume":"11","author":"G Peyr\u00e9","year":"2019","unstructured":"Peyr\u00e9, G., Cuturi, M.: Computational optimal transport. Found. Trends Mach. Learn. 11(5\u20136), 355\u2013607 (2019)","journal-title":"Found. Trends Mach. Learn."},{"key":"1347_CR22","volume-title":"Real and Complex Analysis","author":"W Rudin","year":"1987","unstructured":"Rudin, W.: Real and Complex Analysis, 3rd edn. McGraw-Hill Inc, USA (1987)","edition":"3"},{"key":"1347_CR23","doi-asserted-by":"crossref","unstructured":"Santambrogio, F.: Optimal Transport for Applied Mathematicians, vol.\u00a087 of Progress in Nonlinear Differential Equations and Their Applications. Birkh\u00e4user, Boston (2015)","DOI":"10.1007\/978-3-319-20828-2"},{"issue":"3","key":"1347_CR24","doi-asserted-by":"publisher","first-page":"A1443","DOI":"10.1137\/16M1106018","volume":"41","author":"B Schmitzer","year":"2019","unstructured":"Schmitzer, B.: Stabilized sparse scaling algorithms for entropy regularized transport problems. SIAM J. Sci. Comput. 41(3), A1443\u2013A1481 (2019)","journal-title":"SIAM J. Sci. Comput."},{"key":"1347_CR25","doi-asserted-by":"crossref","unstructured":"Schmitzer, B., Schn\u00f6rr, C.: A hierarchical approach to optimal transport. In: Scale Space and Variational Methods (SSVM 2013), pp. 452\u2013464 (2013)","DOI":"10.1007\/978-3-642-38267-3_38"},{"key":"1347_CR26","doi-asserted-by":"crossref","unstructured":"Villani, C.: Optimal Transport: Old and New, vol.\u00a0338 of Grundlehren der mathematischen Wissenschaften. Springer (2009)","DOI":"10.1007\/978-3-540-71050-9"}],"container-title":["Numerische Mathematik"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00211-023-01347-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00211-023-01347-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00211-023-01347-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,7]],"date-time":"2023-12-07T23:32:56Z","timestamp":1701991976000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00211-023-01347-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,28]]},"references-count":26,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["1347"],"URL":"https:\/\/doi.org\/10.1007\/s00211-023-01347-x","relation":{},"ISSN":["0029-599X","0945-3245"],"issn-type":[{"value":"0029-599X","type":"print"},{"value":"0945-3245","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,28]]},"assertion":[{"value":"25 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}