Parallel Monte Carlo computation of invariant measures

In recent years, the statistical study of chaotic dynamical systems has attracted tremendous attention in science and engineering. In doing so the theory and methods for the existence and computation of absolutely continuous invariant measures (also called physical measures in physical sciences) have played a major role. In this dissertation, the computational problem of invariant measures is studied with Ulam's method, combined with parallel computing techniques and a kind of Monte Carlo approach.; Let S : [0, 1] → [0, 1] be a nonsingular transformation and let P : L1 (0, 1) → L1 (0, 1) be the corresponding Frobenius-Perron operator. In Ulam's method we approximate the infinite dimensional operator P with a finite dimensional one P_n obtained via a Galerkin projection onto the subspace of piecewise constant functions with respect to the given partition of the interval [0, 1], and then we solve the fixed point problem of the finite dimensional approximation. Since in general the analytic evaluation of the resulting matrix is difficult or even impossible, we employ a “uniform sampling” idea, which is a deterministic variant of the usual Monte Carlo method for a better performance and is called the quasi-Monte Carlo method in this dissertation, for the implementation of Ulam's method. To overcome the disadvantage of time-consuming for the quasi-Monte Carlo method, we take advantage of the fact that the evaluation of the entries of the matrix in Ulam's method is independent of each other. Thus a natural parallel evaluation scheme is proposed in this work. Moreover, we present a completely parallel algorithm for the computation of the fixed density of the Frobenius-Perron operator, in which not only the evaluation of the matrix is parallelized, but also the computation, which uses the iteration algorithm (IA) as compared with the Gaussian algorithm (GA), of the fixed density of the matrix is parallelized. The numerical experiments show that the new algorithm is a fast and reliable numerical scheme for the computation of invariant measures, and the new quasi-Monte Carlo approach works much better than the Monte Carlo approach initially proposed by Hunt of the National Institute of Standards and Technology in 1994.; Besides the numerical work mentioned above, we also present some theoretical work by giving a rigorous approximation order analysis for the method of piecewise linear Markov finite approximations. The construction of this piecewise linear method is for the purpose of improving the convergence rate of Ulam's piecewise constant method. In the dissertation we use the idea of approximations of continuous functions by a sequence of positive linear operators to prove that the error bound for the piecewise linear Markov method is indeed O( h2), which is compatible with past numerical results.; Lastly, as an application example, the computation of the probability density function (PDF) of the first-order digital phase locked loop (DPLL) in electronics is discussed with our parallel quasi-Monte Carlo algorithm. The numerical results show that the completely parallel quasi-Monte Carlo algorithm computes the complicated invariant density much more efficiently than the original “operator function evaluation method” used by some researchers in this field.