Grassmannian spectral shooting

Ledoux, Veerle; Malham, Simon; Thümmler, Vera

doi:10.1090/S0025-5718-10-02323-9

Grassmannian spectral shooting
HTML articles powered by AMS MathViewer

by Veerle Ledoux, Simon J. A. Malham and Vera Thümmler PDF

Math. Comp. 79 (2010), 1585-1619 Request permission

Abstract:

We present a new numerical method for computing the pure-point spectrum associated with the linear stability of coherent structures. In the context of the Evans function shooting and matching approach, all the relevant information is carried by the flow projected onto the underlying Grassmann manifold. We show how to numerically construct this projected flow in a stable and robust manner. In particular, the method avoids representation singularities by, in practice, choosing the best coordinate patch representation for the flow as it evolves. The method is analytic in the spectral parameter and of complexity bounded by the order of the spectral problem cubed. For large systems it represents a competitive method to those recently developed that are based on continuous orthogonalization. We demonstrate this by comparing the two methods in three applications: Boussinesq solitary waves, autocatalytic travelling waves and the Ekman boundary layer.

References

Hisham Abou-Kandil, Gerhard Freiling, Vlad Ionescu, and Gerhard Jank, Matrix Riccati equations, Systems & Control: Foundations & Applications, Birkhäuser Verlag, Basel, 2003. In control and systems theory. MR 1997753, DOI 10.1007/978-3-0348-8081-7
J. Alexander, R. Gardner, and C. Jones, A topological invariant arising in the stability analysis of travelling waves, J. Reine Angew. Math. 410 (1990), 167–212. MR 1068805
J. C. Alexander and R. Sachs, Linear instability of solitary waves of a Boussinesq-type equation: a computer assisted computation, Nonlinear World 2 (1995), no. 4, 471–507. MR 1360872
L. Allen, Modelling dolphin hydrodynamics: The numerical analysis and hydrodynamic stability of flow past compliant surfaces, Ph.D. Thesis, University of Surrey, 2001.
Leanne Allen and Thomas J. Bridges, Numerical exterior algebra and the compound matrix method, Numer. Math. 92 (2002), no. 2, 197–232. MR 1922919, DOI 10.1007/s002110100365
Leanne Allen and Thomas J. Bridges, Hydrodynamic stability of the Ekman boundary layer including interaction with a compliant surface: a numerical framework, Eur. J. Mech. B Fluids 22 (2003), no. 3, 239–258. MR 1991025, DOI 10.1016/S0997-7546(03)00036-0
Nairo D. Aparicio, Simon J. A. Malham, and Marcel Oliver, Numerical evaluation of the Evans function by Magnus integration, BIT 45 (2005), no. 2, 219–258. MR 2176193, DOI 10.1007/s10543-005-0001-8
N. J. Balmforth, R. V. Craster, and S. J. A. Malham, Unsteady fronts in an autocatalytic system, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 455 (1999), no. 1984, 1401–1433. MR 1701752, DOI 10.1098/rspa.1999.0366
J. Billingham and D. J. Needham, The development of travelling waves in quadratic and cubic autocatalysis with unequal diffusion rates. I. Permanent form travelling waves, Philos. Trans. Roy. Soc. London Ser. A 334 (1991), no. 1633, 1–24. MR 1155096, DOI 10.1098/rsta.1991.0001
S. Billey, Grassmannians and other Schubert varieties, talk, April 14, 2007.
David Bindel, James Demmel, and Mark Friedman, Continuation of invariant subspaces in large bifurcation problems, SIAM J. Sci. Comput. 30 (2008), no. 2, 637–656. MR 2385879, DOI 10.1137/060654219
Sergio Bittanti, Alan J. Laub, and Jan C. Willems (eds.), The Riccati equation, Communications and Control Engineering Series, Springer-Verlag, Berlin, 1991. MR 1132048, DOI 10.1007/978-3-642-58223-3
Ȧke Björck and Gene H. Golub, Numerical methods for computing angles between linear subspaces, Math. Comp. 27 (1973), 579–594. MR 348991, DOI 10.1090/S0025-5718-1973-0348991-3
Thomas J. Bridges, Gianne Derks, and Georg Gottwald, Stability and instability of solitary waves of the fifth-order KdV equation: a numerical framework, Phys. D 172 (2002), no. 1-4, 190–216. MR 1946769, DOI 10.1016/S0167-2789(02)00655-3
Thomas J. Bridges and Sebastian Reich, Computing Lyapunov exponents on a Stiefel manifold, Phys. D 156 (2001), no. 3-4, 219–238. MR 1850782, DOI 10.1016/S0167-2789(01)00283-4
L.Q. Brin, Numerical testing of the stability of viscous shock waves, Ph.D. Thesis, Indiana University, Bloomington, 1998.
Leon Q. Brin, Numerical testing of the stability of viscous shock waves, Math. Comp. 70 (2001), no. 235, 1071–1088. MR 1710652, DOI 10.1090/S0025-5718-00-01237-0
Roger W. Brockett and Christopher I. Byrnes, Multivariable Nyquist criteria, root loci, and pole placement: a geometric viewpoint, IEEE Trans. Automat. Control 26 (1981), no. 1, 271–284. MR 609265, DOI 10.1109/TAC.1981.1102571
Elena Celledoni and Arieh Iserles, Approximating the exponential from a Lie algebra to a Lie group, Math. Comp. 69 (2000), no. 232, 1457–1480. MR 1709149, DOI 10.1090/S0025-5718-00-01223-0
Elena Celledoni and Brynjulf Owren, On the implementation of Lie group methods on the Stiefel manifold, Numer. Algorithms 32 (2003), no. 2-4, 163–183. MR 1989365, DOI 10.1023/A:1024079724094
H.-C. Chang, E.A. Demekhin and D.I. Kopelevich, Local stability theory of solitary pulses in an active medium, Physica D 97 (1996), pp. 353–375.
S. S. Chern, Complex manifolds without potential theory, Van Nostrand Mathematical Studies, No. 15, D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto, Ont.-London, 1967. MR 0225346
C.–C. Chou and R.E. Wyatt, Computational method for the quantum Hamilton–Jacobi equation: Bound states in one dimension, J. Chem. Phys. 125(174103) (2006), pp. 1–10.
C.–C. Chou and R.E. Wyatt, Riccati differential equation for quantum mechanical bound states: Comparison of numerical integrators, Int. J. Quant. Chem. 108 (2008), pp.238–248.
S. Coombes and M. R. Owen, Evans functions for integral neural field equations with Heaviside firing rate function, SIAM J. Appl. Dyn. Syst. 3 (2004), no. 4, 574–600. MR 2111240, DOI 10.1137/040605953
I. Coskun, Grassmannians: The first example of a moduli space, MIT Open Course Ware available at http://ocw.mit.edu/NR/rdonlyres/Mathematics/18-727Spring-2006.
Jian Deng and Shunsaku Nii, Infinite-dimensional Evans function theory for elliptic eigenvalue problems in a channel, J. Differential Equations 225 (2006), no. 1, 57–89. MR 2228692, DOI 10.1016/j.jde.2005.09.007
Gianne Derks, Ute Ebert, and Bernard Meulenbroek, Laplacian instability of planar streamer ionization fronts—an example of pulled front analysis, J. Nonlinear Sci. 18 (2008), no. 5, 551–590. MR 2448541, DOI 10.1007/s00332-008-9023-0
A. Dhooge, W. Govaerts, and Yu. A. Kuznetsov, MATCONT: a MATLAB package for numerical bifurcation analysis of ODEs, ACM Trans. Math. Software 29 (2003), no. 2, 141–164. MR 2000880, DOI 10.1145/779359.779362
L. Dieci and E.S. Van Vleck, Orthonormal integrators based on Householder and Givens transformations, Future Generation Computer Systems 19(3) (2003) Special issue: Geometric numerical algorithms, pp. 363–373.
Arjen Doelman, Robert A. Gardner, and Tasso J. Kaper, Stability analysis of singular patterns in the 1D Gray-Scott model: a matched asymptotics approach, Phys. D 122 (1998), no. 1-4, 1–36. MR 1650111, DOI 10.1016/S0167-2789(98)00180-8
L. O’C. Drury, Numerical solution of Orr-Sommerfeld-type equations, J. Comput. Phys. 37 (1980), no. 1, 133–139. MR 584325, DOI 10.1016/0021-9991(80)90008-X
Alan Edelman, Tomás A. Arias, and Steven T. Smith, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl. 20 (1999), no. 2, 303–353. MR 1646856, DOI 10.1137/S0895479895290954
John W. Evans, Nerve axon equations. IV. The stable and the unstable impulse, Indiana Univ. Math. J. 24 (1974/75), no. 12, 1169–1190. MR 393891, DOI 10.1512/iumj.1975.24.24096
William Fulton, Young tableaux, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, Cambridge, 1997. With applications to representation theory and geometry. MR 1464693
Fritz Gesztesy, Yuri Latushkin, and Konstantin A. Makarov, Evans functions, Jost functions, and Fredholm determinants, Arch. Ration. Mech. Anal. 186 (2007), no. 3, 361–421. MR 2350362, DOI 10.1007/s00205-007-0071-7
Fritz Gesztesy, Yuri Latushkin, and Kevin Zumbrun, Derivatives of (modified) Fredholm determinants and stability of standing and traveling waves, J. Math. Pures Appl. (9) 90 (2008), no. 2, 160–200 (English, with English and French summaries). MR 2437809, DOI 10.1016/j.matpur.2008.04.001
S.K. Gray and D.E. Manopoulous, Symplectic integrators tailored to the time-dependent Schrödinger equation, J. Chem. Phys. 104(18) (1996), pp. 7099–7112.
Leon Greenberg and Marco Marletta, Numerical solution of non-self-adjoint Sturm-Liouville problems and related systems, SIAM J. Numer. Anal. 38 (2001), no. 6, 1800–1845. MR 1856233, DOI 10.1137/S0036142999358743
Phillip Griffiths and Joseph Harris, Principles of algebraic geometry, Wiley Classics Library, John Wiley & Sons, Inc., New York, 1994. Reprint of the 1978 original. MR 1288523, DOI 10.1002/9781118032527
V. V. Gubernov, G. N. Mercer, H. S. Sidhu, and R. O. Weber, Evans function stability of non-adiabatic combustion waves, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 460 (2004), no. 2048, 2415–2435. MR 2073926, DOI 10.1098/rspa.2004.1285
Ernst Hairer, Christian Lubich, and Gerhard Wanner, Geometric numerical integration, Springer Series in Computational Mathematics, vol. 31, Springer-Verlag, Berlin, 2002. Structure-preserving algorithms for ordinary differential equations. MR 1904823, DOI 10.1007/978-3-662-05018-7
Daniel Henry, Geometric theory of semilinear parabolic equations, Lecture Notes in Mathematics, vol. 840, Springer-Verlag, Berlin-New York, 1981. MR 610244
Robert Hermann and Clyde F. Martin, Applications of algebraic geometry to systems theory. I, IEEE Trans. Automatic Control AC-22 (1977), no. 1, 19–25. MR 0444172, DOI 10.1109/tac.1977.1101395
R. Hermann and C. Martin, Lie theoretic aspects of the Riccati equation, NASA Report WP2-3:30.
R. Hermann and C. Martin, Periodic solutions of the Riccati equation, NASA Report TP3-3:00, IEEE (1980).
Robert Hermann and Clyde Martin, Lie and Morse theory for periodic orbits of vector fields and matrix Riccati equations. I. General Lie-theoretic methods, Math. Systems Theory 15 (1981/82), no. 3, 277–284. MR 667827, DOI 10.1007/BF01786984
Robert Hermann and Clyde Martin, Lie and Morse theory for periodic orbits of vector fields and matrix Riccati equations. II, Math. Systems Theory 16 (1983), no. 4, 297–306. MR 721102, DOI 10.1007/BF01744584
Jeffrey Humpherys and Kevin Zumbrun, An efficient shooting algorithm for Evans function calculations in large systems, Phys. D 220 (2006), no. 2, 116–126. MR 2253406, DOI 10.1016/j.physd.2006.07.003
Jeffrey Humpherys, Björn Sandstede, and Kevin Zumbrun, Efficient computation of analytic bases in Evans function analysis of large systems, Numer. Math. 103 (2006), no. 4, 631–642. MR 2221065, DOI 10.1007/s00211-006-0004-7
J.M. Hutson, Coupled channel methods for solving the bound-state Schrödinger equation, Computer Physics Communications 84 (1994), pp. 1–18.
A. Iserles, A. Marthinsen, and S. P. Nørsett, On the implementation of the method of Magnus series for linear differential equations, BIT 39 (1999), no. 2, 281–304. MR 1697681, DOI 10.1023/A:1022393913721
Arieh Iserles and Antonella Zanna, Efficient computation of the matrix exponential by generalized polar decompositions, SIAM J. Numer. Anal. 42 (2005), no. 5, 2218–2256. MR 2139245, DOI 10.1137/S0036142902415936
Arieh Iserles, Hans Z. Munthe-Kaas, Syvert P. Nørsett, and Antonella Zanna, Lie-group methods, Acta numerica, 2000, Acta Numer., vol. 9, Cambridge Univ. Press, Cambridge, 2000, pp. 215–365. MR 1883629, DOI 10.1017/S0962492900002154
L.Gr. Ixaru, Special techniques related to the CP methods for the coupled channel Schrödinger equation, talk given at Workshop Numerical Approach of Oscillatory functions 2008, Ghent.
B.R. Johnson, New numerical methods applied to solving the one-dimensional eigenvalue problem, J. Chem. Phys. 67(9) (1977), pp. 4086–4093.
Todd Kapitula and Björn Sandstede, Instability mechanism for bright solitary-wave solutions to the cubic-quintic Ginzburg-Landau equation, J. Opt. Soc. Amer. B Opt. Phys. 15 (1998), no. 11, 2757–2762. MR 1699233, DOI 10.1364/JOSAB.15.002757
S. L. Kleiman and Dan Laksov, Schubert calculus, Amer. Math. Monthly 79 (1972), 1061–1082. MR 323796, DOI 10.2307/2317421
Yuji Kodama, Young diagrams and $N$-soliton solutions of the KP equation, J. Phys. A 37 (2004), no. 46, 11169–11190. MR 2101933, DOI 10.1088/0305-4470/37/46/006
A. Kresch, Flag varieties and Schubert calculus, Algebraic groups, Universitätsverlag Göttingen, Göttingen, 2007, pp. 73–86. MR 2309940
S. Krogstad, A low complexity Lie group method on the Stiefel manifold, Reports in Informatics, ISSN 0333-3590, 2001.
S. Lafortune and J. Lega, Instability of local deformations of an elastic rod, Phys. D 182 (2003), no. 1-2, 103–124. MR 2002861, DOI 10.1016/S0167-2789(03)00125-8
Stéphane Lafortune and Pavel Winternitz, Superposition formulas for pseudounitary matrix Riccati equations, J. Math. Phys. 37 (1996), no. 3, 1539–1550. MR 1377650, DOI 10.1063/1.531448
V. Ledoux, Study of special algorithms for solving Sturm-Liouville and Schrödinger equations. Ph.D. Thesis, Universiteit Gent, 2007.
V. Ledoux, M. Van Daele and G. Vanden Berghe, A numerical procedure to solve the multichannel Schrödinger eigenvalue problem, Comp. Phys. Commun. 176 (2007), pp. 191-199.
Veerle Ledoux, Simon J. A. Malham, Jitse Niesen, and Vera Thümmler, Computing stability of multidimensional traveling waves, SIAM J. Appl. Dyn. Syst. 8 (2009), no. 1, 480–507. MR 2496765, DOI 10.1137/080724009
J.C. Light and R.B. Walker, An R matrix approach to the solution of coupled equations for atom-molecule reactive scattering, J. Chem. Phys. 65(10) (1976), p. 4272–4282.
Wilhelm Magnus, On the exponential solution of differential equations for a linear operator, Comm. Pure Appl. Math. 7 (1954), 649–673. MR 67873, DOI 10.1002/cpa.3160070404
D.E. Manopoulous and S.K. Gray, Symplectic integrators for the multichannel Schrödinger equation, J. Chem. Phys. 102(23) (1995), pp. 9214–9227.
Jerrold E. Marsden and Tudor S. Ratiu, Introduction to mechanics and symmetry, 2nd ed., Texts in Applied Mathematics, vol. 17, Springer-Verlag, New York, 1999. A basic exposition of classical mechanical systems. MR 1723696, DOI 10.1007/978-0-387-21792-5
Clyde Martin and Robert Hermann, Applications of algebraic geometry to systems theory. III. The McMillan degree and Kronecker indices of transfer functions as topological and holomorphic system invariants, SIAM J. Control Optim. 16 (1978), no. 5, 743–755. MR 527294, DOI 10.1137/0316050
M. J. Metcalf, J. H. Merkin, and S. K. Scott, Oscillating wave fronts in isothermal chemical systems with arbitrary powers of autocatalysis, Proc. Roy. Soc. London Ser. A 447 (1994), no. 1929, 155–174. MR 1303323, DOI 10.1098/rspa.1994.0133
Carl Meyer, Matrix analysis and applied linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. With 1 CD-ROM (Windows, Macintosh and UNIX) and a solutions manual (iv+171 pp.). MR 1777382, DOI 10.1137/1.9780898719512
John W. Milnor and James D. Stasheff, Characteristic classes, Annals of Mathematics Studies, No. 76, Princeton University Press, Princeton, N. J.; University of Tokyo Press, Tokyo, 1974. MR 0440554
Cleve Moler and Charles Van Loan, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev. 45 (2003), no. 1, 3–49. MR 1981253, DOI 10.1137/S00361445024180
Richard Montgomery, A tour of subriemannian geometries, their geodesics and applications, Mathematical Surveys and Monographs, vol. 91, American Mathematical Society, Providence, RI, 2002. MR 1867362, DOI 10.1090/surv/091
Hans Munthe-Kaas, High order Runge-Kutta methods on manifolds, Proceedings of the NSF/CBMS Regional Conference on Numerical Analysis of Hamiltonian Differential Equations (Golden, CO, 1997), 1999, pp. 115–127. MR 1662814, DOI 10.1016/S0168-9274(98)00030-0
A. Zanna and H. Z. Munthe-Kaas, Generalized polar decompositions for the approximation of the matrix exponential, SIAM J. Matrix Anal. Appl. 23 (2001/02), no. 3, 840–862. MR 1896821, DOI 10.1137/S0895479800377551
Shunsaku Nii, An extension of the stability index for travelling-wave solutions and its application to bifurcations, SIAM J. Math. Anal. 28 (1997), no. 2, 402–433. MR 1434043, DOI 10.1137/S003614109427878X
Erkki Oja, A simplified neuron model as a principal component analyzer, J. Math. Biol. 15 (1982), no. 3, 267–273. MR 684939, DOI 10.1007/BF00275687
Peter J. Olver, Equivalence, invariants, and symmetry, Cambridge University Press, Cambridge, 1995. MR 1337276, DOI 10.1017/CBO9780511609565
Robert L. Pego and Michael I. Weinstein, Eigenvalues, and instabilities of solitary waves, Philos. Trans. Roy. Soc. London Ser. A 340 (1992), no. 1656, 47–94. MR 1177566, DOI 10.1098/rsta.1992.0055
A. Postnikov, Total positivity, Grassmannians, and Networks, arXiv:math/060976v1 27 Sep 2006.
Heinz Prüfer, Neue Herleitung der Sturm-Liouvilleschen Reihenentwicklung stetiger Funktionen, Math. Ann. 95 (1926), no. 1, 499–518 (German). MR 1512291, DOI 10.1007/BF01206624
John D. Pryce, Numerical solution of Sturm-Liouville problems, Monographs on Numerical Analysis, The Clarendon Press, Oxford University Press, New York, 1993. Oxford Science Publications. MR 1283388
M. S. Ravi, Joachim Rosenthal, and Xiaochang Wang, Dynamic pole assignment and Schubert calculus, SIAM J. Control Optim. 34 (1996), no. 3, 813–832. MR 1384954, DOI 10.1137/S036301299325270X
J. Rosenthal, The Hermann–Martin curve, preprint report.
Björn Sandstede, Stability of travelling waves, Handbook of dynamical systems, Vol. 2, North-Holland, Amsterdam, 2002, pp. 983–1055. MR 1901069, DOI 10.1016/S1874-575X(02)80039-X
Björn Sandstede and Arnd Scheel, Curvature effects on spiral spectra: generation of point eigenvalues near branch points, Phys. Rev. E (3) 73 (2006), no. 1, 016217, 8. MR 2223064, DOI 10.1103/PhysRevE.73.016217
Jeremy Schiff and S. Shnider, A natural approach to the numerical integration of Riccati differential equations, SIAM J. Numer. Anal. 36 (1999), no. 5, 1392–1413. MR 1706774, DOI 10.1137/S0036142996307946
C. R. Schneider, Global aspects of the matrix Riccati equation, Math. Systems Theory 7 (1973), no. 3, 281–286. MR 391175, DOI 10.1007/BF01795945
Mark A. Shayman, Phase portrait of the matrix Riccati equation, SIAM J. Control Optim. 24 (1986), no. 1, 1–65. MR 818936, DOI 10.1137/0324001
Frank Sottile, Rational curves on Grassmannians: systems theory, reality, and transversality, Advances in algebraic geometry motivated by physics (Lowell, MA, 2000) Contemp. Math., vol. 276, Amer. Math. Soc., Providence, RI, 2001, pp. 9–42. MR 1837108, DOI 10.1090/conm/276/04509
Norman Steenrod, The Topology of Fibre Bundles, Princeton Mathematical Series, vol. 14, Princeton University Press, Princeton, N. J., 1951. MR 0039258
Jonathan Swinton and John Elgin, Stability of travelling pulse solutions to a laser equation, Phys. Lett. A 145 (1990), no. 8-9, 428–433. MR 1052867, DOI 10.1016/0375-9601(90)90307-A
David Terman, Stability of planar wave solutions to a combustion model, SIAM J. Math. Anal. 21 (1990), no. 5, 1139–1171. MR 1062397, DOI 10.1137/0521063
Frank W. Warner, Foundations of differentiable manifolds and Lie groups, Graduate Texts in Mathematics, vol. 94, Springer-Verlag, New York-Berlin, 1983. Corrected reprint of the 1971 edition. MR 722297
W-Y. Yan, U. Helmke and J.B. Moore, Global analysis of Oja’s flow for neural networks, IEEE Transactions on Neural Networks 5(5) (1994), pp. 674–683.
Xingren Ying and I. Norman Katz, A reliable argument principle algorithm to find the number of zeros of an analytic function in a bounded domain, Numer. Math. 53 (1988), no. 1-2, 143–163. MR 946373, DOI 10.1007/BF01395882
M. I. Zelikin, Control theory and optimization. I, Encyclopaedia of Mathematical Sciences, vol. 86, Springer-Verlag, Berlin, 2000. Homogeneous spaces and the Riccati equation in the calculus of variations; A translation of Homogeneous spaces and the Riccati equation in the calculus of variations (Russian), “Faktorial”, Moscow, 1998; Translation by S. A. Vakhrameev. MR 1739679, DOI 10.1007/978-3-662-04136-9