Implicit Low-Rank Riemannian Schemes for the Time Integration of Stiff Partial Differential Equations
Abstract
We propose two implicit numerical schemes for the low-rank time integration of stiff nonlinear partial differential equations. Our approach uses the preconditioned Riemannian trust-region method of Absil, Baker, and Gallivan, 2007. We demonstrate the efficiency of our method for solving the Allen–Cahn and the Fisher–KPP equations on the manifold of fixed-rank matrices. Our approach allows us to avoid the restriction on the time step typical of methods that use the fixed-point iteration to solve the inner nonlinear equations. Finally, we demonstrate the efficiency of the preconditioner on the same variational problems presented in Sutti and Vandereycken, 2021.
References
[1]
Absil PA, Baker CG, and Gallivan KA Trust-region methods on riemannian manifolds Found. of Comput. Math. 2007 7 303-330
[2]
Absil PA, Mahony R, and Sepulchre R Optimization Algorithms on Matrix Manifolds 2008 Princeton, NJ Princeton University Press
[3]
Absil PA and Malick J Projection-like retractions on matrix manifolds SIAM J. Optim. 2012 22 1 135-158
[4]
Absil PA and Oseledets IV Low-rank retractions: a survey and new results Comput. Optim. Appl. 2015 62 1 5-29
[5]
Allen SM and Cahn JW Ground state structures in ordered binary alloys with second neighbor interactions Acta Metall. 1972 20 3 423-433
[6]
Allen SM and Cahn JW A correction to the ground state of FCC binary ordered alloys with first and second neighbor pairwise interactions Scr. Metall. 1973 7 12 1261-1264
[7]
Beneš M, Chalupecký V, and Mikula K Geometrical image segmentation by the Allen-Cahn equation Appl. Numer. Math. 2004 51 2 187-205
[8]
Benzi M, Golub GH, and Liesen J Numerical solution of saddle point problems Acta. Numer. 2005 14 1-137
[9]
Billaud-Friess M, Falcó A, and Nouy A A new splitting algorithm for dynamical low-rank approximation motivated by the fibre bundle structure of matrix manifolds BIT Numer. Math. 2022 62 2 387-408
[10]
Boumal N An Introduction to Optimization on Smooth Manifolds 2023 Cambridge Cambridge University Press
[11]
Boumal N and Absil PA Low-rank matrix completion via preconditioned optimization on the Grassmann manifold Linear Algebra Appl. 2015 475 200-239
[12]
Boumal N, Mishra B, Absil PA, and Sepulchre R Manopt, a Matlab toolbox for optimization on manifolds J. Mach. Lear. Res. 2014 15 1455-1459
[13]
Brenner S and Scott R The Mathematical Theory of Finite Element Methods. Texts in Applied Mathematics 2007 New York Springer
[14]
Cai, J.F., Huang, W., Wang, H., Wei, K.: Tensor completion via tensor train based low-rank quotient geometry under a preconditioned metric (2022)
[15]
Ceruti G, Kusch J, and Lubich C A rank-adaptive robust integrator for dynamical low-rank approximation BIT Numer. Math. 2022 62 4 1149-1174
[16]
Ceruti G and Lubich C An unconventional robust integrator for dynamical low-rank approximation BIT Numer. Math. 2022 62 1 23-44
[17]
Charous, A., Lermusiaux, P.: Dynamically orthogonal differential equations for stochastic and deterministic reduced-order modeling of ocean acoustic wave propagation. In: OCEANS 2021: San Diego – Porto, pp. 1–7 (2021).
[18]
Charous, A., Lermusiaux, P.F.J.: Stable rank-adaptive dynamically orthogonal runge-kutta schemes (2022)
[19]
Dieudonné J Foundations of Modern Analysis 1960 New York Academic Press
[20]
Dobrosotskaya JA and Bertozzi AL A wavelet-laplace variational technique for image deconvolution and inpainting IEEE Trans. Image Process. 2008 17 5 657-663
[21]
Edelman A, Arias TA, and Smith ST The geometry of algorithms with orthogonality constraints SIAM J. Matrix Anal. Appl. 1998 20 2 303-353
[22]
Feppon F and Lermusiaux PFJ Dynamically orthogonal numerical schemes for efficient stochastic advection and lagrangian transport SIAM Rev. 2018 60 3 595-625
[23]
Feppon F and Lermusiaux PFJ A geometric approach to dynamical model order reduction SIAM J. Matrix Anal. Appl. 2018 39 1 510-538
[24]
Fisher RA The wave of advance of advantageous genes Ann. Eug. 1937 7 4 355-369
[25]
Grasedyck L Existence of a low rank or -matrix approximant to the solution of a Sylvester equation Numer. Linear Algebra with Appl. 2004 11 4 371-389
[26]
Gratton S, Sartenaer A, and Toint PL Recursive trust-region methods for multiscale nonlinear optimization SIAM J. Optim. 2008 19 1 414-444
[27]
Helmke U and Moore JB Optimization and Dynamical Systems 1994 London Springer-Verlag
[28]
Henderson HV and Searle SR The vec-permutation matrix, the vec operator and Kronecker products: a review Linear Multilinear Algebra 1981 9 4 271-288
[29]
Henson VE Bouman CA and Stevenson RL Multigrid methods nonlinear problems: an overview Computational Imaging 2003 US International Society for Optics and Photonics, SPIE 36-48
[30]
Hundsdorfer W and Verwer J Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations 2003 1 Berlin, Heidelberg Springer
[31]
Khatri CG and Rao CR Solutions to some functional equations and their applications to characterization of probability distributions Sankhyā Ser. A 1968 30 2 167-180
[32]
Kieri E, Lubich C, and Walach H Discretized dynamical low-rank approximation in the presence of small singular values SIAM J. Numer. Anal. 2016 54 2 1020-1038
[33]
Kieri E and Vandereycken B Projection methods for dynamical low-rank approximation of high-dimensional problems Comput. Methods Appl. Math. 2019 19 1 73-92
[34]
Koch O and Lubich C Dynamical low-rank approximation SIAM J. Matrix Anal. Appl. 2007 29 2 434-454
[35]
Kolmogorov, A.N., Petrowsky, I.G., Piskunov, N.S.: Studies of the diffusion with the increasing quantity of the substance; its application to a biological problem. In: O.A. Oleinik (ed.) I.G. Petrowsky Selected Works. Part II: Differential Equations and Probability Theory, Classics of Soviet Mathematics, vol. 5, first edn., chap. 6, pp. 106–132. CRC Press, London (1996).
[36]
Kressner, D.: Advanced numerical analysis (2015). https://www.epfl.ch/labs/anchp/wp-content/uploads/2018/05/AdvancedNA2015.pdf
[37]
Kressner D, Steinlechner M, and Vandereycken B Preconditioned low-rank riemannian optimization for linear systems with tensor product structure SIAM J. Sci. Comput. 2016 38 4 A2018-A2044
[38]
Kressner D and Tobler C Preconditioned low-rank methods for high-dimensional elliptic PDE eigenvalue problems Comput. Methods Appl. Math. 2011 11 3 363-381
[39]
Kressner D and Tobler C Algorithm 941: Htucker–a matlab toolbox for tensors in hierarchical tucker format ACM Trans. Math. Softw. 2014 40 3 22:1-22:22
[40]
Kürschner, P.: Efficient low-rank solution of large-scale matrix equations. Ph.D. thesis, Aachen (2016)
[41]
Laux T and Simon TM Convergence of the Allen-Cahn equation to multiphase mean curvature flow Commun. Pure Appl. Anal. 2018 71 8 1597-1647
[42]
Le Dret H and Lucquin B Partial Differential Equations: Modeling, Analysis and Numerical Approximation 2016 Basel Birkhäuser
[43]
Lee D and Lee S Image segmentation based on modified fractional Allen-Cahn equation Math. Probl. Eng. 2019 2019 3980181
[44]
Lee HG and Kim J An efficient and accurate numerical algorithm for the vector-valued Allen-Cahn equations Comput. Phys. Commun. 2012 183 10 2107-2115
[45]
Lermusiaux P Evolving the subspace of the three-dimensional multiscale ocean variability: massachusetts bay J. Mar. Syst. 2001 29 1 385-422 Three-Dimensional Ocean Circulation: Lagrangian measurements and diagnostic analyses
[46]
Lermusiaux, P.F.J., Robinson, A.R.: Data assimilation via error subspace statistical estimation. Part i: theory and schemes. Mon. Weather Rev. 127(7), 1385–1407 (1999). https://doi.org/10.1175/1520-0493(1999)1271385:DAVESS2.0.CO;2
[47]
Li Y, Jeong D, Choi J, Lee S, and Kim J Fast local image inpainting based on the Allen-Cahn model Digit. Signal Process. 2015 37 65-74
[48]
Lubich C and Oseledets IV A projector-splitting integrator for dynamical low-rank approximation BIT Numer. Math. 2014 54 1 171-188
[49]
Massei S, Robol L, and Kressner D Hierarchical adaptive low-rank format with applications to discretized partial differential equations Numer. Linear Algebra Appl. 2022 29 6 e2448
[50]
Mishra B, Meyer G, Bach F, and Sepulchre R Low-rank optimization with trace norm penalty SIAM J. Optim. 2013 23 4 2124-2149
[51]
Mishra B and Sepulchre R Riemannian preconditioning SIAM J. Optim. 2016 26 1 635-660
[52]
Mishra, B., Vandereycken, B.: A Riemannian approach to low-rank algebraic Riccati equations. In: 21st International Symposium on Mathematical Theory of Networks and Systems, pp. 965–968. Groningen, The Netherlands (2014)
[53]
Murray JD Mathematical Biology I. An Introduction 2002 3 New York, NY Springer
[54]
Musharbash E, Nobile F, and Vidličková E Symplectic dynamical low rank approximation of wave equations with random parameters BIT Numer. Math. 2020 60 4 1153-1201
[55]
Ngo, T., Saad, Y.: Scaled Gradients on Grassmann Manifolds for Matrix Completion. In: Pereira, F., Burges, C., Bottou, L., Weinberger, K. (eds.) Adv. Neural Inf. Process. Syst., vol. 25. Curran Associates Inc., USA (2012)
[56]
Nocedal J and Wright SJ Numerical Optimization 2006 2 New York, NY Springer
[57]
Rakhuba M, Novikov A, and Oseledets I Low-rank Riemannian eigensolver for high-dimensional Hamiltonians J. Comput. Phys. 2019 396 718-737
[58]
Rakhuba M and Oseledets I Jacobi-Davidson method on low-rank matrix manifolds SIAM J. Sci. Comput. 2018 40 2 A1149-A1170
[59]
Rodgers A, Dektor A, and Venturi D Adaptive integration of nonlinear evolution equations on tensor manifolds J. Sci. Comput. 2022 92 2 39
[60]
Rodgers A and Venturi D Implicit step-truncation integration of nonlinear PDEs on low-rank tensor manifolds J. Sci. Comput. 2022 97 2 33 arXiv:2207.01962
[61]
Sapsis TP and Lermusiaux PF Dynamically orthogonal field equations for continuous stochastic dynamical systems Phys. D: Nonlinear Phenom. 2009 238 23 2347-2360
[62]
Shalit, U., Weinshall, D., Chechik, G.: Online Learning in The Manifold of Low-Rank Matrices. In: Lafferty, J., Williams, C., Shawe-Taylor, J., Zemel, R., Culotta, A. (eds.) Adv. Neural Inf. Process. Syst., vol. 23. Curran Associates Inc., USA (2010)
[63]
Shalit U, Weinshall D, and Chechik G Online learning in the embedded manifold of low-rank matrices J. Mach. Lear. Res. 2012 13 429-458
[64]
Simoncini V Computational methods for linear matrix equations SIAM Rev. 2016 58 3 377-441
[65]
Steihaug T The conjugate gradient method and trust regions in large scale optimization SIAM J. Numer. Anal. 1983 20 3 626-637
[66]
Steinlechner M Riemannian optimization for high-dimensional tensor completion SIAM J. Sci. Comput. 2016 38 5 S461-S484
[67]
Sutti, M.: Riemannian algorithms on the stiefel and the fixed-rank manifold. Ph.D. thesis, University of Geneva (2020). ID: unige:146438
[68]
Sutti, M., Vandereycken, B.: RMGLS: A MATLAB algorithm for Riemannian multilevel optimization. Available online (2020).
[69]
Sutti M and Vandereycken B Riemannian multigrid line search for low-rank problems SIAM J. Sci. Comput. 2021 43 3 A1803-A1831
[70]
Toint, P.L.: Towards an efficient sparsity exploiting Newton method for minimization. In: Sparse Matrices and Their Uses, pp. 57–88. Academic Press, London, England (1981)
[71]
Ueckermann M, Lermusiaux P, and Sapsis T Numerical schemes for dynamically orthogonal equations of stochastic fluid and ocean flows J. Comput. Phys. 2013 233 272-294
[72]
Uschmajew, A., Vandereycken, B.: Geometric methods on low-rank matrix and tensor manifolds, chap. 9, pp. 261–313. Springer International Publishing, Cham (2020).
[73]
Van Loan CF The ubiquitous Kronecker product J. Comput. and Appl. Math. 2000 123 1–2 85-100
[74]
Vandereycken B Low-rank matrix completion by riemannian optimization SIAM J. Optim. 2013 23 2 1214-1236
[75]
Vandereycken B and Vandewalle S A riemannian optimization approach for computing low-rank solutions of Lyapunov equations SIAM J. Matrix Anal. Appl. 2010 31 5 2553-2579
[76]
Wen Z and Goldfarb D A line search multigrid method for large-scale nonlinear optimization SIAM J. Optim. 2009 20 3 1478-1503
[77]
Yang X, Feng JJ, Liu C, and Shen J Numerical simulations of jet pinching-off and drop formation using an energetic variational phase-field method J. Comput. Phys. 2006 218 1 417-428
[78]
Yoon S, Jeong D, Lee C, Kim H, Kim S, Lee HG, and Kim J Fourier-spectral method for the phase-field equations Mathematics 2020 8 8 1385
Index Terms
- Implicit Low-Rank Riemannian Schemes for the Time Integration of Stiff Partial Differential Equations
Index terms have been assigned to the content through auto-classification.
Recommendations
Error analysis and applications of the Fourier-Galerkin Runge-Kutta schemes for high-order stiff PDEs
An integrating factor mixed with Runge-Kutta technique is a time integration method that can be efficiently combined with spatial spectral approximations to provide a very high resolution to the smooth solutions of some linear and nonlinear partial ...
Implicit-Explicit Difference Schemes for Nonlinear Fractional Differential Equations with Nonsmooth Solutions
† Special Section on Two Themes: CSE Software and Big Data in CSEWe propose second-order implicit-explicit (IMEX) time-stepping schemes for nonlinear fractional differential equations with fractional order $0<\beta<1$. From the known structure of the nonsmooth solution and by introducing corresponding correction terms,...
Convergence of a Low-Rank Lie--Trotter Splitting for Stiff Matrix Differential Equations
We propose a numerical integrator for determining low-rank approximations to solutions of large-scale matrix differential equations. The considered differential equations are semilinear and stiff. Our method consists of first splitting the differential ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s) 2024.
Publisher
Plenum Press
United States
Publication History
Published: 13 August 2024
Accepted: 17 July 2024
Revision received: 17 June 2024
Received: 19 May 2023
Author Tags
Author Tags
Qualifiers
- Research-article
Funding Sources
- Ministry of Science and Technology, Taiwan
- Swiss National Science Foundation
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Dec 2024