×

Parallel implementations of the false nearest neighbors method to study the behavior of dynamical models. (English) Zbl 1205.68499

Summary: Dynamical models are an issue of multidisciplinary studies with direct applications in different areas of science and technology (medicine, oceanography, economics, biology, etc.). One way to study dynamical models is through their associated time series in order to find out the model evolution (equilibrium points, orbits, trajectories, etc.) and determine intervals where the predictions are reliable. A key point in this process is the computing of the time series embedding dimension using the False Nearest Neighbors (FNN) method. The FNN method has a high computational cost when long time series are available (or used), so the execution time has to be reduced. This paper describes two parallel implementations of the FNN method for hybrid (shared and distributed) memory architectures. To the best of the authors’ knowledge, the hybrid implementations presented in this paper represent the first parallel implementation of this type. Moreover, considering a hybrid implementation makes it possible to take advantage of different parallel architectures, because knowing the numbers of nodes and the number of cores per node, the software is autotuned in order to exploit the maximum degree of parallelism existing in the target machine. The computationally intensive part of the method lies mainly in the neighbor search and therefore this task is parallelized and executed using 2 to 64 processors. The accuracy and performance of the two parallel approaches are then assessed and compared against the best sequential implementation of the FNN method which appears in the TISEAN project.

MSC:

68W10 Parallel algorithms in computer science

Software:

TISEAN; MPI; pthreads
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Packard, N. H.; Crutchfield, J. P.; Farmer, J. D.; Shaw, R. S., Geometry from a time series, Phys. Rev. Lett., 45, 712-716 (1980)
[2] Takens, F., Detecting strange attractors in turbulence, (Rand, D. A.; Young, L.-S., Dynamical Systems and Turbulence, Warwick 1980 (1981), Springer: Springer New York), 366-381
[3] Kennel, M. B.; Brown, R.; Abarbanel, H. D.I., Determining embedding dimension for phase-space reconstruction using a geometrical construction, Phys. Rev. A, 45, 3403-3411 (1992)
[4] Schreiber, T., Efficient neighbor searching in nonlinear time series analysis, Int. J. Bifur. Chaos, 5, 349-358 (1995) · Zbl 0885.58052
[5] Hegger, R.; Kantz, H.; Schreiber, T., Practical implementation of nonlinear time series methods: The TISEAN package, Chaos, 9, 413-435 (1999) · Zbl 0990.37522
[6] Gropp, W.; Lusk, E.; Skjellum, A., Using MPI: Portable Parallel Programming with the Message-Passing Interface (1994), MIT Press: MIT Press Cambridge
[7] F. Mueller, Pthreads Library Interface, Institut für Informatik Tech. Report, Humboldt-Universität zu Berlin, 1999.; F. Mueller, Pthreads Library Interface, Institut für Informatik Tech. Report, Humboldt-Universität zu Berlin, 1999.
[8] Grama, A.; Gupta, A.; Karypis, G.; Kumar, V., Introduction to Parallel Computing (2003), Pearson Education: Pearson Education Harlow
[9] Lorenz, E., Deterministic nonperiodic flow, J. Atmospheric. Sci., 20, 130-141 (1963) · Zbl 1417.37129
[10] Hénon, M., A two-dimensional mapping with a strange attractor, Commun. Math. Phys., 50, 69-77 (1976) · Zbl 0576.58018
[11] Rössler, O. E., An equation for continuous chaos, Phys. Lett. A, 57, 397-398 (1976) · Zbl 1371.37062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.