×

zbMATH — the first resource for mathematics

Discrete processes and their continuous limits. (English) Zbl 07241770
Summary: The possibility that a discrete process can be fruitfully approximated by a continuous one, with the latter involving a differential system, is fascinating. Important theoretical insights, as well as significant computational efficiency gains may lie in store. A great success story in this regard are the Navier-Stokes equations, which model many phenomena in fluid flow rather well. Recent years saw many attempts to formulate more such continuous limits, and thus harvest theoretical and practical advantages, in diverse areas including mathematical biology, economics, finance, computational optimization, image processing, game theory, and machine learning.
Caution must be applied as well, however. In fact, it is often the case that the given discrete process is richer in possibilities than its continuous differential system limit, and that a further study of the discrete process is practically rewarding. Furthermore, there are situations where the continuous limit process may provide important qualitative, but not quantitative, information about the actual discrete process. This paper considers several case studies of such continuous limits and demonstrates success as well as cause for caution. Consequences are discussed.

MSC:
65K05 Numerical mathematical programming methods
65L04 Numerical methods for stiff equations
68U10 Computing methodologies for image processing
Software:
COLSYS; RODAS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] H. Akaike, On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method, Ann. Inst. Statist. Math. Tokyo, 11, 1-16 (1959) · Zbl 0100.14002
[2] U. Ascher, On symmetric schemes and differential-algebraic equations, SIAM J. Sci. Statist. Comput., 10, 937-949 (1989) · Zbl 0687.65084
[3] U. Ascher; J. Christiansen; R. D. Russell, Collocation software for boundary-value ODEs, ACM Trans. Math. Software, 7, 209-222 (1981) · Zbl 0455.65067
[4] U. Ascher and C. Greif, A First Course in Numerical Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011. · Zbl 1326.65001
[5] U. Ascher; E. Haber; H. Huang, On effective methods for implicit piecewise smooth surface recovery, SIAM J. Sci. Comput., 28, 339-358 (2006) · Zbl 1104.65320
[6] U. Ascher; H. Huang; K. van den Doel, Artificial time integration, BIT, 47, 3-25 (2007) · Zbl 1113.65068
[7] U. Ascher, R. Mattheij and R. Russell, Numerical Solution of Boundary Value Problems for Ordinary Differential Equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1995. · Zbl 0843.65054
[8] U. Ascher and L. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. · Zbl 0908.65055
[9] U. Ascher; S. Reich, The midpoint scheme and variants for Hamiltonian systems: Advantages and pitfalls, SIAM J. Sci. Comput., 21, 1045-1065 (1999) · Zbl 0947.65133
[10] U. Ascher and H. Huang, Numerical analysis in visual computing: What we can learn from each other, Vietnam J. Math, 46 (2018) 745-759. · Zbl 06996356
[11] D. Baraff and A. Witkin, Large steps in cloth simulation, In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, Association for Computing Machinery, New York, New York, 1998, 43-54.
[12] C. Barnes, E. Shechtman, A. Finkelstein and D. Goldman, Patchmatch: A randomized correspondence algorithm for structural image editing, ACM Trans. Graph., 27 (2009), Art. 24, 11 pp.
[13] J. Barzilai; J. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8, 141-148 (1988) · Zbl 0638.65055
[14] A. Beck, First-Order Methods in Optimization, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2017. · Zbl 1384.65033
[15] M. Betancourt, M. Jordan and A. Wilson, On symplectic optimization, preprint, 2018, arXiv: 1802.03653v2.
[16] M. Burger, M. Di Francesco, P. A. Markowich and M. T. Wolfram, On a mean field game optimal control approach modeling fast exit scenarios in human crowds, In 52nd IEEE Conference on Decision and Control, Florence, 2013, 3128-3133.
[17] D. Calvetti and L. Reichel, Lanczos-based exponential filtering for discrete ill-posed problems, Numer. Algorithms, 29 2002, 45-65. · Zbl 0997.65068
[18] D. Calvetti, L. Reichel, and Q. Zhang., Iterative exponential filtering for large discrete ill-posed problems., Numer. Math., 83: 535-556, 1999. · Zbl 0947.65039
[19] A. Chambolle; T. Pock, An introduction to continuous optimization for imaging, Acta Numer., 25, 161-319 (2016) · Zbl 1343.65064
[20] T. Chan and J. Shen, Image Processing and Analysis: Variational, PDE, Wavelet and Stochastic Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. · Zbl 1095.68127
[21] D. Chen, D. Levin, L. Matusic and D. Kaufman, Dynamics-aware numerical coarsening for fabrication design, ACM Trans. Graphics, 36 (2017), Art. 84, 15 pp.
[22] A. J. Chorin, Numerical solution of the Navier-Stokes equations, Math. Comp., 22, 745-762 (1968) · Zbl 0198.50103
[23] A. J. Chorin and J. E. Marsden, A Mathematical Introduction to Fluid Mechanics, 3rd edition, Springer-Verlag, New York, 1993. · Zbl 0774.76001
[24] S. Darabi, E. Shechtman, C. Barnes, D. Goldman and P. Sen, Image melding: Combining inconsistent images using patch-based synthesis, ACM Trans. Graph., 31 (2012), Art. 82, 1-82.
[25] P. Deuflhard, Newton’s Method for Nonlinear Problems, Springer-Verlag, Berlin, 2004. · Zbl 1056.65051
[26] J. Diakonikolas; L. Orecchia, The approximate duality gap technique: A unified theory of first-order methods, SIAM J. Optim., 29, 660-689 (2019) · Zbl 1412.90085
[27] K. van den Doel; U. Ascher, Dynamic level set regularization for large distributed parameter estimation problems, Inverse Problems, 23, 1271-1288 (2007) · Zbl 1117.65147
[28] K. van den Doel; U. Ascher, The chaotic nature of faster gradient descent methods, J. Sci. Comput., 51, 560-581 (2011) · Zbl 1252.65073
[29] H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Kluwer Academic Publishers Group, Dordrecht, 1996. · Zbl 0859.65054
[30] Z. Farbman, R. Fattal, D. Lischinski and R. Szeliski, Edge-preserving decompositions for multi-scale tone and detail manipulation, in ACM SIGGRAPH 2008 Papers, Association for Computing Machinery, New York, New York, 2008.
[31] D. A. Gomez; J. Saúde, Mean field games models - A brief survey, Dyn. Games Appl., 4, 110-154 (2014) · Zbl 1314.91048
[32] D. A. Gomez; J. Mohr; R. R. Souza, Continuous time finite state mean field games, Appl. Math. Optim., 68, 99-143 (2013) · Zbl 1283.91016
[33] A. Greenbaum, Iterative Methods for Solving Linear Systems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. · Zbl 0883.65022
[34] E. Hairer, C. Lubich and G. Wanner, Geometric Numerical Integration, Springer-Verlag, Berlin, 2002. · Zbl 0994.65135
[35] E. Hairer and G. Wanner, Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems, 2nd edition, Springer-Verlag, Berlin, 1996. · Zbl 0859.65067
[36] H. Huang and U. Ascher, Fast denoising of surface meshes with intrinsic texture, Inverse Problems, 24 (2008), 034003, 18 pp. · Zbl 1142.65015
[37] H. Huang; U. Ascher, Surface mesh smoothing, regularization, and feature detection, SIAM J. Sci. Comput., 31, 74-93 (2008) · Zbl 1190.65025
[38] H. Huang; D. Li; R. Zhang; U. Ascher; D. Cohen-Or, Consolidation of unorganized point clouds for surface reconstruction, ACM Trans. Graph., 28, 1-7 (2009) · Zbl 1372.94043
[39] H. Huang, S. Wu, M. Gong, D. Cohen-Or, U. Ascher and H. Zhang, Edge-aware point set resampling, ACM Trans. Graph., 32 (2013), Art. 9, 12 pp. · Zbl 1322.68222
[40] H. Huang, K. Yin, M. Gong, D. Lischinski, D. Cohen-Or, U. M. Ascher, and B. Chen, “Mind the gap”: Tele-registration for structure-driven image completion, ACM Trans. Graph., 32 (2013), Art. 174, 10 pp.
[41] J. Kaipo and E. Somersalo, Statistical and Computational Inverse Problems, Springer-Verlag, New York, 2005.
[42] H.-O. Kreiss, Centered difference approximation to singular systems of odes, in Symposia Mathematica X, 1972.
[43] J.-M. Lasry; P.-L. Lions, Mean field games, Jpn. J. Math., 2, 229-260 (2007) · Zbl 1156.91321
[44] R. Malhamé; M. Huang; P. Caines, Large population stochastic dynamic games: Closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle, Commun. Inf. Syst., 6, 221-252 (2006) · Zbl 1136.91349
[45] M. Markowich, C. Ringhofer and C. Schmeiser, Semi-conductor Equations, Springer-Verlag, Vienna, 1990. · Zbl 0765.35001
[46] Y. Nesterov, A method of solving a convex programming problem with convergence rate \(O(1/k^2)\), Dokl. Akad. Nauk SSSR, 269, 543-547 (1983)
[47] Y. Nesterov, Lectures on Convex Optimization, Springer, Cham, 2018. · Zbl 1427.90003
[48] J. Nocedal and S. Wright, Numerical Optimization, Springer-Verlag, New York, 1999. · Zbl 0930.65067
[49] S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Springer-Verlag, New York, 2003. · Zbl 1026.76001
[50] B. T. Polyak, Some methods of speeding up the convergence of iteration methods, Z. Vycisl. Mat i Mat. Fiz., 4, 791-803 (1964)
[51] M. Raydan; B. Svaiter, Relaxed steepest descent and Cauchy-Barzilai-Borwein method, Comput. Optim. Appl., 21, 155-167 (2002) · Zbl 0988.90049
[52] F. Roosta-Khorasani, K. van den Doel and U. Ascher, Stochastic algorithms for inverse problems involving PDEs and many measurements, SIAM J. Sci. Comput., 36 (2014), S3-S22. · Zbl 1307.65158
[53] L. Ruthotto; E. Haber, Deep neural networks motivated by partial differential equations, J. Math. Imaging Vision, 62, 352-364 (2019) · Zbl 1434.68522
[54] W. Su, S. Boyd, and E. Candes, A differential equation for modelling Nesterov’s accelerated gradient method, Advances in Neural Information Processing Systems (NIPS), 27 (2014). · Zbl 1391.90667
[55] W. Su; S. Boyd; E. Candes, A differential equation for modelling Nesterov’s accelerated gradient method: Theory and insights, J. Mach. Learn. Res., 17, 1-43 (2016) · Zbl 1391.90667
[56] E. Tadmor; S. Nezzar; L. Vese, A multiscale image representation using hierarchical (BV, \({L}^2)\) decompositions, Multiscale Model. Simul., 2, 554-579 (2004) · Zbl 1146.68472
[57] A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-posed Problems, John Wiley and Sons, Inc., New York-Toronto, Ont.-London, 1977. · Zbl 0354.65028
[58] G. Wanner, Kepler, Newton and numerical analysis, Acta Numer., 19, 561-598 (2010) · Zbl 1247.70001
[59] A. Wibisono, A. Wilson and M. Jordan, A variational perspective on accelerated methods in optimization, Proc. Natl. Acad. Sci. U. S. A., 113 (2016), E7351-E7358. · Zbl 1404.90098
[60] W. I. Zangwill, Nonlinear programming: A unified approach, Prentice-Hall, Inc., Englewood Cliffs, N. J., 1969. · Zbl 0195.20804
[61] J. Zhang, A. Mokhtari, S. Sra and A. Jadbabai, Direct Runge-Kutta discretization achieves acceleration, preprint, 2018, arXiv: 1805.00521.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.