Search

We prove the equivariant divergence formula for the axiom A flow attractors, which is a recursive formula for perturbation of transfer operators of physical measures along center-unstable manifolds. Hence the linear response acquires an `ergodic theorem', which means that it can be sampled by recursively computing only $2u$ many vectors on one orbit, where $u$ is the unstable dimension., Comment: comments are welcome!

We develop the no-propagate algorithm for sampling the linear response of random dynamical systems, which are non-uniform hyperbolic deterministic systems perturbed by noise with smooth density. We first derive a Monte-Carlo type formula and then the algorithm, which is different from the ensemble (stochastic gradient) algorithms, finite-element algorithms, and fast-response algorithms; it does not involve the propagation of vectors or covectors, and only the density of the noise is differentiated, so the formula is not cursed by gradient explosion, dimensionality, or non-hyperbolicity. We demonstrate our algorithm on a tent map perturbed by noise and a chaotic neural network with 51 layers $\times$ 9 neurons. By itself, this algorithm approximates the linear response of non-hyperbolic deterministic systems, with an additional error proportional to the noise. We also discuss the potential of using this algorithm as a part of a bigger algorithm with smaller error.

To generalize the backpropagation method to both discrete-time and continuous-time hyperbolic chaos, we introduce the adjoint shadowing operator $\mathcal{S}$ acting on covector fields. We show that $\mathcal{S}$ can be equivalently defined as: (a) $\mathcal{S}$ is the adjoint of the linear shadowing operator $S$; (b) $\mathcal{S}$ is given by a `split then propagate' expansion formula; (c) $\mathcal{S}(\omega)$ is the only bounded inhomogeneous adjoint solution of $\omega$. By (a), $\mathcal{S}$ adjointly expresses the shadowing contribution, a significant part of the linear response, where the linear response is the derivative of the long-time statistics with respect to system parameters. By (b), $\mathcal{S}$ also expresses the other part of the linear response, the unstable contribution. By (c), $\mathcal{S}$ can be efficiently computed by the nonintrusive shadowing algorithm in Ni and Talnikar (2019 J. Comput. Phys. 395 690-709), which is similar to the conventional backpropagation algorithm. For continuous-time cases, we additionally show that the linear response admits a well-defined decomposition into shadowing and unstable contributions.

We devise the fast adjoint response algorithm for the gradient of physical measures (long-time-average statistics) of discrete-time hyperbolic chaos with respect to many system parameters. Its cost is independent of the number of parameters. The algorithm transforms our new theoretical tools, the adjoint shadowing lemma and the equivariant divergence formula, into the form of progressively computing $u$ many bounded vectors on one orbit. Here $u$ is the unstable dimension. We demonstrate our algorithm on an example difficult for previous methods, a system with random noise, and a system of a discontinuous map. We also give a short formal proof of the equivariant divergence formula. Compared to the better-known finite-element method, our algorithm is not cursed by dimensionality of the phase space (typical real-life systems have very high dimensions), since it samples by one orbit. Compared to the ensemble/stochastic method, our algorithm is not cursed by the butterfly effect, since the recursive relations in our algorithm is bounded., Comment: 24 pages, 11 figures. This update: we replaced the previous proof of equivariant divergence formula with a short and formal one based on Lie derivatives. The previous proof was moved to arXiv:2108.13863. The adjoint shadowing lemma is updated to arXiv:2207.06648

We show that the derivative of the (measure) transfer operator with respect to the parameter of the map is a divergence. Then, for physical measures of discrete-time hyperbolic chaotic systems, we derive an equivariant divergence formula for the unstable perturbation of transfer operators along unstable manifolds. This formula and hence the linear response, the parameter-derivative of physical measures, can be sampled by recursively computing only $2u$ many vectors on one orbit, where $u$ is the unstable dimension. The numerical implementation of this formula in \cite{far} is neither cursed by dimensionality nor the sensitive dependence on initial conditions., Comment: final version at JSP

We devise the fast linear response algorithm for differentiating fractal invariant measures of chaos with respect to perturbations of governing equations. We first derive the first computable expansion formula for the unstable divergence, then a `fast' formula by renormalized second-order tangent equations. The algorithm's cost is solving only one orbit and $u$, the unstable dimension, many first-order and second-order tangent equations; the main error is the sampling error of the orbit. We demonstrate it on an numerical example which is difficult for previous methods., Comment: 37 pages, 7 figures

Nonintrusive shadowing algorithms efficiently compute $v$, the difference between shadowing trajectories, then use $v$ to compute derivatives of averaged objectives of chaos with respect to parameters of the dynamical system. However, previous proofs of shadowing methods wrongly assume that shadowing trajectories are representative. In contrast, the linear response formula is proved rigorously, but is more difficult to compute. We prove that $v$ gives only a part, called the shadowing contribution, of the linear response; hence, the other part, the unstable contribution, is the systematic error of shadowing methods. For systems with a small ratio of unstable dimensions, with some further statistical assumptions, we show that the unstable contribution is small. We also briefly describe an algorithm for the unstable contribution, which is simpler to derive but less efficient than the fast linear response algorithm. Moreover, we prove the convergence of the nonintrusive shadowing algorithm, the fastest shadowing algorithm, to $v$ and to the shadowing contribution., Comment: 24 pages, no figure

This paper defines linear range as the range of parameter perturbations which lead to approximately linear perturbations in the states of a network. We compute linear range from the difference between actual perturbations in states and the tangent solution. Linear range is a new criterion for estimating the effectivenss of gradients and thus having many possible applications. In particular, we propose that the optimal learning rate at the initial stages of training is such that parameter changes on all minibatches are within linear range. We demonstrate our algorithm on two shallow neural networks and a ResNet., Comment: 9 pages, 4 figures

For hyperbolic diffeomorphisms, we define adjoint shadowing directions as a bounded inhomogeneous adjoint solution whose initial condition has zero component in the unstable adjoint direction. For hyperbolic flows, we define adjoint shadowing directions similarly, with the additional requirement that the average of its inner-product with the trajectory direction is zero. In both cases, we show unique existence of adjoint shadowing directions, and how they can be used for adjoint sensitivity analysis. Our work set a theoretical foundation for efficient adjoint sensitivity methods for long-time-averaged objectives such as NILSAS., Comment: 22 pages, 1 figure. The algorithm for the adjoint shadowing direction is at arXiv:1801.08674

We develop the NILSAS algorithm, which performs adjoint sensitivity analysis of chaotic systems via computing the adjoint shadowing direction. NILSAS constrains its minimization to the adjoint unstable subspace, and can be implemented with little modification to existing adjoint solvers. The computational cost of NILSAS is independent of the number of parameters. We demonstrate NILSAS on the Lorenz 63 system and a weakly turbulent three-dimensional flow over a cylinder., Comment: 34 pages, 11 figures. The adjoint shadowing direction which we compute is defined at arXiv:1807.05568

We present the Finite Difference Non-Intrusive Least Squares Shadowing (FD-NILSS) algorithm for computing sensitivities of long-time averaged quantities in chaotic dynamical systems. FD-NILSS does not require tangent solvers, and can be implemented with little modification to existing numerical simulation software. We also give a formula for solving the least-squares problem in FD-NILSS, which can be applied in NILSS as well. Finally, we apply FD-NILSS for sensitivity analysis of a chaotic flow over a 3-D cylinder at Reynolds number 525, where FD-NILSS computes accurate sensitivities and the computational cost is in the same order as the numerical simulation., Comment: 20 pages, 8 figures

This paper uses compressible flow simulation to analyze the hyperbolicity, shadowing directions, and sensitivities of a weakly turbulent three dimensional cylinder flow at Reynolds number 525 and Mach number 0.1. By computing the first 40 Covariant Lyapunov Vectors (CLVs), we find that unstable CLVs are active in the near-wake region, whereas stable CLVs are active in the far-wake region. This phenomenon is related to hyperbolicity since it shows that CLVs point to different directions; it also suggests that for open flows there is a large fraction of CLVs that are stable. However, due to the extra neutral CLV and the occasional tangencies between CLVs, our system is not uniform hyperbolic. By the Non-intrusive least-squares shadowing (NILSS) algorithm, we compute shadowing directions and sensitivities of long-time-averaged objectives. Our results suggest that shadowing methods may be valid for general chaotic fluid problems., Comment: 26 pages, 14 figures

This paper develops the non-intrusive formulation of the Least-squares shadowing (LSS) method, for computing the sensitivity of long-time averaged objectives in chaotic dynamical systems. This non-intrusive formulation constrains the computation to only the unstable subspace, greatly reducing the cost of LSS for many problems; moreover, it reparametrizes the LSS problem, requiring only minor modifications to existing tangent solvers. NILSS is demonstrated on a chaotic flow over a backward-facing step simulated with a mesh of 12e3 cells., Comment: 26 pages, 10 figures

This paper develops a variant of the Least Squares Shadowing (LSS) method, which has successfully computed the derivative for several chaotic ODEs and PDEs. The development in this paper aims to simplify Least Squares Shadowing method by improving how time dilation is treated. Instead of adding an explicit time dilation term as in the original method, the new variant uses windowing, which can be simpler to implement, especially for PDEs., Comment: 21 pages, 4 figures

For a parameterized hyperbolic system $\frac{du}{dt}=f(u,s)$ the derivative of the ergodic average $\langle J \rangle = \lim_{T \to \infty}\frac{1}{T}\int_0^T J(u(t),s)$ to the parameter $s$ can be computed via the Least Squares Shadowing algorithm (LSS). We assume that the sytem is ergodic which means that $\langle J \rangle$ depends only on $s$ (not on the initial condition of the hyperbolic system). After discretizing this continuous system using a fixed timestep, the algorithm solves a constrained least squares problem and, from the solution to this problem, computes the desired derivative $\frac{d\langle J \rangle}{ds}$. The purpose of this paper is to prove that the value given by the LSS algorithm approaches the exact derivative when the discretization timestep goes to $0$ and the timespan used to formulate the least squares problem grows to infinity., Comment: 21 pages, this article complements arXiv:1304.3635 and analyzes LSS for the case of continuous hyperbolic systems