Parallel computation of the correlation dimension from a time series
A parallel algorithm is presented for computing the Correlation Dimension (D2) from a time series generated by a dynamical system, using the method of correlation integrals. Three versions are discussed: the first computes all distances between points in the phase space, whereas the second and third compute only distances less than a threshold ?; the third version in particular is very powerful since it employs a box-assisted approach and linked lists for a fast search of neighboring points. The parallelization is designed for coarse-grained multiprocessor systems with distributed memory and is accomplished using a message passing model and partitioning points evenly among processors. Uniform implementation and computational analysis allow a clear comparison of the three versions. The algorithms, tested on the Transtech PARAstation multiprocessor, are well balanced, give a linear speed-up and show a good scalability. The third version is particularly suitable for fast processing of very long time series and allows the estimation of D2 even for medium- and high-dimensional systems, where an extremely large number of points is needed. The algorithms can be adapted with few modifications to the computation of the generalized dimensions Dq, and they can also be useful in other applications involving the efficient computation of distances between points in a large set. More generally, the computational framework can be used in similar problems involving long-range interactions.
correlation dimension message passing computation of distances long-range interactions nonlinear time series analysis box-assisted parallel algorithms distributed memory multiprocessors