This is an old revision of the document!
====== findorbit ====== ''findorbit'' calculates equilibria, traveling waves, and periodic orbits of plane Couette flow using a Newton-GMRES-hookstep algorithm developed by Divakar Viswanath, U Michigan. ====== Mathematics ====== The following is an overview of the Viswanath Newton-GMRES-hookstep algorithm, meant as a reference for the options of the ''findorbit'' utility. It leaves out a number of gnarly details. And please excuse the mishmash of plain text, html, and dokuwiki-latex! Let u = discretized velocity field, as difference from laminar flow f^T(u) = time-T map of the Navier Stokes eqn, numerically integrated σ = a symmetry of plane Couette flow G(u,σ,T) = σ f^T(u) - u, a zero of G(u,σ,T) is an invariant solution of Navier-Stokes r(u,σ,T) = 1/2 ||G(u,σ,T)||^2 = residual of G(u,σ,T)=0 ||G|| = a norm of G, to be defined later. Equilibria, traveling waves, periodic orbits, and relative periodic orbits are all solutions of G(u,σ,T) = 0. * equilibria: σ is the identity and t is arbitrary. We set σ = 1, hold T fixed to a arbitrary value, and search over u * traveling waves: σ is a translation τ(cx T, cz T) and T is arbitrary. We hold T fixed and search over u and a finite phase shifts, (ax, az) = (cx T / Lx, cz T/ Lz). * periodic orbits: σ is fixed and we search over u and T. * relative periodic orbits: we search over u, σ, and T. Let x be the finite set of free variables being searched over, e.g. for a periodic orbit, 10^5 spectral coefficients of u plus the period T. We want to find a zero of G(x) or equivalently a minimum of r(x). ===== Newton algorithm ===== The Newton algorithm for solving G(x) = 0 is Let x* be the solution, i.e. G(x*) = 0. Suppose we start with an initial guess x near x*. Let x* = x + dx. Then <latex> G(x^*) = G(x) + DG(x) \, dx + O(|dx|^2) = 0 </latex> Drop higher order terms and solve <latex> DG \, dx = -G(x) </latex> Then start with new guess x' = x+dx and iterate. ===== GMRES ===== In the present case x is 10^5 dimensional or more, so it is not practical to compute the matrix DG in order to solve the Newton equation. So we use GMRES (Generalized Minimal Residuals), an iterative algorithm for solving linear systems A x = b by repeated calculations of the product A x for test values of x. Specifically, we look for solutions x within n-dimensional //Krylov subpaces// spanned by Ab, A^2b, A^3 b, ..., A^n b. If the eigenvalues of A are well-separated, you can often get a good solution x in a n-dimensional Krylov subspace with n << dim(x). In our case the product is DG dx, and it is calculated using numerical integration of Navier-Stokes. If x = (u,σ,T), then dx = (du,dσ,dT) and <latex> $ \begin{align*} DG \, dx &= G(u+du, \, \sigma+d\sigma, \, T+dT) \\ &= (\sigma+d\sigma) f^{T+dT}(u+du) - \sigma f^T(u) \end{align} $ </latex> which can be easily calculated by numerical integrations of f. For low Reynolds numbers (Re=400) and small cells [Lx,Ly,Lz] approx [pi, 2, pi], we can usually find an approximate solution to DG dx = -G(x) in forty or so iterations. That means forty or so integrations around the approximate periodic orbit. This accounts for the bulk of the CPU time consumed by ''findorbit''. For more on GMRES, see Trefethen and Bau in the [[#References]]. ===== Hookstep ===== Unfortunately, Newton iteration only works when you are very near the solution, i.e. within the radius of accurate linear approximation of dynamics around the solution. Otherwise the Newton step dx can be widely inacccurate and send you shooting off towards infinity (or "to infinity and beyond," as [[http://www.youtube.com/watch?v=8mVEGfH4s5g|Beyonce]] says). So, instead taking the Newton step directly, we put a limit on the size of the Newton step <latex> \| dx \|^2 \leq \delta^2 </latex> where ====== References ====== Divakar Viswanath, "Recurrent motions within plane Couette turbulence", J. Fluid Mech. 580 (2007), http://arxiv.org/abs/physics/0604062 Lloyd N. Trefethen and David Bau, "Numerical Linear Algebra", SIAM, Philadelphia, 1997. Dennis and Schnabel, "Numerical Methods for Unconstrained Optimization and Nonlinear Equations", Prentice-Hall Series in Computational Mathematics, Englewood Cliffs, New Jersey, 1983. Beyonce, "Single Ladies", http://www.youtube.com/watch?v=8mVEGfH4s5g
