We propose a generalization of nonlinear stability of numerical one-step integrators to Riemannian manifolds in the spirit of Butcher's notion of B-stability. Taking inspiration from Simpson-Porco and Bullo, we introduce non-expansive systems on such manifolds and define B-stability of integrators. In this first exposition, we provide concrete results for a geodesic version of the Implicit Euler (GIE) scheme. We prove that the GIE method is B-stable on Riemannian manifolds with non-positive sectional curvature. We show through numerical examples that the GIE method is expansive when applied to a certain non-expansive vector field on the 2-sphere, and that the GIE method does not necessarily possess a unique solution for large enough step sizes. Finally, we derive a new improved global error estimate for general Lie group integrators.
Citation: |
Figure 6. Left: The Implicit Lie-Euler method applied to (21) with stepsize $ h = 2 $ and $ c\in[-2, 2] $. The dashed curve shows the arrival point parametrized by $ c $. The solid line depicts the exact solution. Right: the distance between two solutions for increasing stepsizes with three different choices of isotropy parameter $ c\in\{0, 1, 2\} $
[1] |
O. Arandjelovic, G. Shakhnarovich, J. Fisher, R. Cipolla and T. Darrell, Face recognition with image sets using manifold density divergence, Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), (2005), 581-588.
![]() |
[2] |
M. Arnold and O. Brüls, Convergence of the generalized-$\alpha$ scheme for constrained mechanical systems, Multibody System Dynamics, 18 (2007), 185-202.
doi: 10.1007/s11044-007-9084-0.![]() ![]() ![]() |
[3] |
M. Arnold, O. Brüls and A. Cardona, Error analysis of generalized-$\alpha$ Lie group time integration methods for constrained mechanical systems, Numerische Mathematik, 129 (2015), 149-179.
doi: 10.1007/s00211-014-0633-1.![]() ![]() ![]() |
[4] |
R. Bhatia and J. Holbrook, Riemannian geometry and matrix geometric means, Linear Algebra and its Applications, 413 (2006), 594-618.
doi: 10.1016/j.laa.2005.08.025.![]() ![]() ![]() |
[5] |
G. Bogfjellmo and H. Marthinsen, High-order symplectic partitioned Lie group methods, Foundations of Computational Mathematics, 16 (2016), 493-530.
doi: 10.1007/s10208-015-9257-9.![]() ![]() ![]() |
[6] |
J. C. Butcher, A stability property of implicit Runge-Kutta methods, BIT, 15 (1975), 358-361.
doi: 10.1007/BF01931672.![]() ![]() |
[7] |
E. Celledoni, E. Çokaj, A. Leone, D. Murari and B. Owren, Lie group integrators for mechanical systems, International Journal of Computer Mathematics, 99 (2021), 1-31.
doi: 10.1080/00207160.2021.1966772.![]() ![]() ![]() |
[8] |
E. Celledoni, S. Eidnes, B. Owren and T. Ringholm, Dissipative numerical schemes on Riemannian manifolds with applications to gradient flows, SIAM Journal on Scientific Computing, 40 (2018), 3789-3806.
doi: 10.1137/18M1190628.![]() ![]() ![]() |
[9] |
E. Celledoni, S. Eidnes, B. Owren and T. Ringholm, Energy-preserving methods on Riemannian manifolds, Mathematics of Computation, 89 (2020), 699-716.
doi: 10.1090/mcom/3470.![]() ![]() ![]() |
[10] |
E. Celledoni, A. Marthinsen and B. Owren, Commutator-free Lie group methods, Future Generation Computer Systems, 19 (2003), 341-352.
doi: 10.1016/S0167-739X(02)00161-9.![]() ![]() |
[11] |
E. Celledoni, H. Marthinsen and B. Owren, An introduction to Lie group integrators - basics, new developments and applications, Journal of Computational Physics, 257 (2014), 1040-1061.
doi: 10.1016/j.jcp.2012.12.031.![]() ![]() ![]() |
[12] |
E. Celledoni and B. Owren, A class of intrinsic schemes for orthogonal integration, SIAM Journal on Numerical Analysis, 40 (2002), 2069-2084.
doi: 10.1137/S0036142901385143.![]() ![]() ![]() |
[13] |
G. Cheng, H. Salehian and B. C. Vemuri, Efficient recursive algorithms for computing the mean diffusion tensor and applications to DTI segmentation, Computer Vision-ECCV 2012: 12th European Conference on Computer Vision, (2012), 390-401.
doi: 10.1007/978-3-642-33786-4_29.![]() ![]() |
[14] |
S. H. Christiansen, H. Z. Munthe-Kaas and B. Owren, Topics in structure-preserving discretization, Acta Numerica, 20 (2011), 1-119.
doi: 10.1017/S096249291100002X.![]() ![]() ![]() |
[15] |
P. E. Crouch and R. Grossman, Numerical integration of ordinary differential equations on manifolds, Journal of Nonlinear Science, 3 (1993), 1-33.
doi: 10.1007/BF02429858.![]() ![]() ![]() |
[16] |
C. Curry and A. Schmeding, Convergence of Lie group integrators, Numerische Mathematik, 144 (2020), 357-373.
doi: 10.1007/s00211-019-01083-1.![]() ![]() ![]() |
[17] |
G. Dahlquist, Error analysis for a class of methods for stiff nonlinear initial value problems, Numerical Analysis, Lecture Notes in Math., Springer-Verlag, Berlin, 506 (1976), 60-72.
![]() ![]() |
[18] |
G. Dahlquist and R. Jeltsch, Generalized disks of contractivity for explicit and implicit Runge-Kutta methods, Dept. of Numerical Analysis and Computer Science, The Royal Institute of Technology, Stockholm, Report TRITA-NA-7906, (1979).
![]() |
[19] |
A. Davydov, S. Jafarpour and F. Bullo, Non-Euclidean contraction theory for robust nonlinear stability, Institute of Electrical and Electronics Engineers. Transactions on Automatic Control, 67 (2022), 6667-6681.
doi: 10.1109/TAC.2022.3183966.![]() ![]() ![]() |
[20] |
K. Dekker and J. G. Verwer, Stability of Runge-Kutta Methods for Stiff Nonlinear Differential Equations, CWI Monogr., 2. North-Holland, Amsterdam-New-York-Oxford, 1984.
![]() ![]() |
[21] |
F. Demoures, F. Gay-Balmaz, S. Leyendecker, S. Ober-Blöbaum, T. S. Ratiu and Y. Weinand, Discrete variational Lie group formulation of geometrically exact beam dynamics, Numerische Mathematik, 130 (2015), 73-123.
doi: 10.1007/s00211-014-0659-4.![]() ![]() ![]() |
[22] |
P. T. Fletcher and S. Joshi, Riemannian geometry for the statistical analysis of diffusion tensor data, Signal Processing, 87 (2007), 250-262.
doi: 10.1016/j.sigpro.2005.12.018.![]() ![]() |
[23] |
R. M. Gregório and P. R. Oliveira, A proximal technique for computing the Karcher mean of symmetric positive definite matrices, Optimization Online, (2013).
![]() |
[24] |
E. Hairer and G. Wanner, Solving Ordinary Differential Equations II. Stiff and Differential-Algebraic Problems Second edition, Springer Ser. Comput. Math., 14. Springer-Verlag, 1996.
doi: 10.1007/978-3-642-05221-7.![]() ![]() ![]() |
[25] |
J. Hall and M. Leok, Lie group spectral variational integrators, Foundations of Computational Mathematics, 17 (2017), 199-257.
doi: 10.1007/s10208-015-9287-3.![]() ![]() ![]() |
[26] |
S. Hante and M. Arnold, RATTLie: A variational Lie group integration scheme for constrained mechanical systems, Numerical Solution of Differential and Differential-Algebraic Equations. Selected Papers from NUMDIFF-15. Journal of Computational and Applied Mathematics, 387 (2021), 112492.
![]() |
[27] |
H. M. Hilber, T. J. R. Hughes and R. L. Taylor, Improved numerical dissipation for time integration algorithms in structural dynamics, Earthquake Engineering & Structural Dynamics, 5 (1977), 283-292.
doi: 10.1002/eqe.4290050306.![]() ![]() |
[28] |
S. Holzinger and J. Gerstmayr, Time integration of rigid bodies modelled with three rotation parameters, Multibody System Dynamics, 53 (2021), 345-378.
doi: 10.1007/s11044-021-09778-w.![]() ![]() ![]() |
[29] |
Z. Huang, R. Wang, S. Shan and X. Chen, Face recognition on large-scale video in the wild with hybrid Euclidean-and-Riemannian metric learning, Pattern Recognition, 48 (2015), 3113-3124.
doi: 10.1016/j.patcog.2015.03.011.![]() ![]() |
[30] |
A. Iserles, H. Munthe-Kaas, S. P. Nørsett and A. Zanna, Lie Group Methods, Acta Numerica, 9 (2000), 215-365.
doi: 10.1017/S0962492900002154.![]() ![]() ![]() |
[31] |
H. Karcher, Riemannian center of mass and mollifier smoothing, Communications on Pure and Applied Mathematics, 30 (1977), 509-541.
doi: 10.1002/cpa.3160300502.![]() ![]() ![]() |
[32] |
M. Kunzinger, H. Schichl, R. Steinbauer and J. A. Vickers, Global Gronwall estimates for integral curves on Riemannian manifolds, Revista Matemática Complutense, 19 (2006), 133-137.
doi: 10.5209/rev_REMA.2006.v19.n1.16639.![]() ![]() ![]() |
[33] |
J. M. Lee, Introduction to Riemannian Manifolds, Graduate Texts in Mathematics, vol. 176. Springer, Cham, 2018.
![]() ![]() |
[34] |
T. Lee, M. Leok and N. H. McClamroch, Lie group variational integrators for the full body problem, Computer Methods in Applied Mechanics and Engineering, 196 (2007), 2907-2924.
doi: 10.1016/j.cma.2007.01.017.![]() ![]() ![]() |
[35] |
B. Leimkuhler and G. W. Patrick, A symplectic integrator for Riemannian manifolds, Journal of Nonlinear Science, 6 (1996), 367-384.
doi: 10.1007/BF02433475.![]() ![]() ![]() |
[36] |
T. Leitz and S. Leyendecker, Galerkin Lie-group variational integrators based on unit quaternion interpolation, Computer Methods in Applied Mechanics and Engineering, 338 (2018), 333-361.
doi: 10.1016/j.cma.2018.04.022.![]() ![]() ![]() |
[37] |
D. Lewis and J. C. Simo, Conserving Algorithms for the Dynamics of Hamiltonian Systems on Lie Groups, Journal of Nonlinear Science, 4 (1994), 253-299.
doi: 10.1007/BF02430634.![]() ![]() ![]() |
[38] |
J. E. Marsden and M. West, Discrete mechanics and variational integrators, Acta Numerica, 10 (2001), 357-514.
doi: 10.1017/S096249290100006X.![]() ![]() ![]() |
[39] |
R. McLachlan, K. Modin and O. Verdier, A minimal-variable symplectic integrator on spheres, Mathematics of Computation, 86 (2017), 2325-2344.
doi: 10.1090/mcom/3153.![]() ![]() ![]() |
[40] |
M. Moakher, A differential geometric approach to the geometric mean of symmetric positive-definite matrices, SIAM Journal on Matrix Analysis and Applications, 26 (2005), 735-747.
doi: 10.1137/S0895479803436937.![]() ![]() ![]() |
[41] |
H. Munthe-Kaas, High order Runge-Kutta methods on manifolds, Applied Numerical Mathematics, 29 (1999), 115-127.
doi: 10.1016/S0168-9274(98)00030-0.![]() ![]() ![]() |
[42] |
B. Owren, Lie group integrators, Discrete Mechanics, Geometric Integration and Lie-Butcher Series, Springer Proc. Math. Stat., Springer, Cham, 267 (2018), 29-69.
doi: 10.1007/978-3-030-01397-4_2.![]() ![]() ![]() |
[43] |
X. Pennec, P. Fillard and N. Ayache, A Riemannian framework for tensor computing, International Journal of Computer Vision, 66 (2006), 41-66.
doi: 10.1007/s11263-005-3222-z.![]() ![]() |
[44] |
Y. Rathi, A. Tannenbaum and O. Michailovich, Segmenting images on the tensor manifold, 2007 IEEE Conference on Computer Vision and Pattern Recognition, (2007), 1-8.
doi: 10.1109/CVPR.2007.383010.![]() ![]() |
[45] |
C. L. Siegel, Symplectic Geometry, Academic Press, New York, 1964.
![]() ![]() |
[46] |
J. C. Simo and L. Vu-Quoc, On the Dynamics of Finite-Strain Rods Undergoing Large Motions – A Geometrically Exact Approach, Computer Methods in Applied Mechanics and Engineering, 66 (1988), 125-161.
doi: 10.1016/0045-7825(88)90073-4.![]() ![]() ![]() |
[47] |
J. W. Simpson-Porco and F. Bullo, Contraction theory on Riemannian manifolds, Systems Control Lett., 65 (2014), 74-80.
doi: 10.1016/j.sysconle.2013.12.016.![]() ![]() ![]() |
[48] |
Z. Terze, A. Müller and D. Zlatar, Singularity-free time integration of rotational quaternions using non-redundant ordinary differential equations, Multibody System Dynamics, 38 (2016), 201-225.
doi: 10.1007/s11044-016-9518-7.![]() ![]() ![]() |
[49] |
O. Tuzel, F. Porikli and P. Meer, Region covariance: A fast descriptor for detection and classification, Computer Vision–ECCV 2006, (2006), 589-600.
doi: 10.1007/11744047_45.![]() ![]() |
[50] |
A. Zanna, K. Engø and H. Munthe-Kaas, Adjoint and selfadjoint Lie-group methods, BIT. Numerical Mathematics, 41 (2001), 395-421.
doi: 10.1023/A:1021950708869.![]() ![]() ![]() |
[51] |
E. Zhang and L. Noakes, Riemannian cubics and elastica in the manifold SPD(n) of all $ n \times n $ symmetric positive-definite matrices, Journal of Geometric Mechanics, 11 (2019), 277-299.
doi: 10.3934/jgm.2019015.![]() ![]() ![]() |
Construction for the proofs of Theorems 2.2 and 3.1
Riemannian distance of two solutions after one step plotted for increasing values of the step size h with the same initial values
One step of GIE method for two initial points with increasing step size
Top: One step of SPHMP (9) (left) and GIMP (8) (right) method for the same two initial points with increasing step size
A bifurcation diagram for solutions to the equation (18)
Left: The Implicit Lie-Euler method applied to (21) with stepsize