Numerical characterization of nonlinear dynamical systems using parallel computing: the role of GPUs approach. (English) Zbl 1473.37102
Summary: The characterization of nonlinear dynamical systems and their attractors in terms of invariant measures, basins of attractions and the structure of their vector fields usually outlines a task strongly related to the underlying computational cost. In this work, the practical aspects related to the use of parallel computing – specially the use of Graphics Processing Units (GPUs) and of the Compute Unified Device Architecture (CUDA) – are reviewed and discussed in the context of nonlinear dynamical systems characterization. In this work such characterization is performed by obtaining both local and global Lyapunov exponents for the classical forced Duffing oscillator. The local divergence measure was employed by the computation of the Lagrangian Coherent Structures (LCSs), revealing the general organization of the flow according to the obtained separatrices, while the global Lyapunov exponents were used to characterize the attractors obtained under one or more bifurcation parameters. These simulation sets also illustrate the required computation time and speedup gains provided by different parallel computing strategies, justifying the employment and the relevance of GPUs and CUDA in such extensive numerical approach. Finally, more than simply providing an overview supported by a representative set of simulations, this work also aims to be a unified introduction to the use of the mentioned parallel computing tools in the context of nonlinear dynamical systems, providing codes and examples to be executed in MATLAB and using the CUDA environment, something that is usually fragmented in different scientific communities and restricted to specialists on parallel computing strategies.
MSC:
| 37M25 | Computational methods for ergodic theory (approximation of invariant measures, computation of Lyapunov exponents, entropy, etc.) |
| 68W10 | Parallel algorithms in computer science |
Keywords:
chaos; CUDA; Duffing oscillator; GPU computing; Lagrangian coherent structures; Lyapunov bifurcation diagram; Lyapunov exponents; parallel computing; parameter spaceReferences:
| [1] | Garland, M.; Le Grand, S.; Nickolls, J.; Anderson, J.; Hardwick, J.; Morton, S., Parallel computing experiences with CUDA, IEEE Micro, 28, 4, 13-27 (2008) |
| [2] | Kirk, D. B.; Hwu, W. W., Programming massively parallel processors: A hands-on approach (2013), Elsevier - Morgan Kaufmann |
| [3] | Lindholm, E.; Nickolls, J.; Oberman, S.; Montrym, J., NVIDIA Tesla: A unified graphics and computing architecture, IEEE Micro, 28, 2, 39-55 (2008) |
| [4] | Montrym, J.; Moreton, H., The GeForce 6800, IEEE Micro, 25, 2, 41-51 (2005) |
| [5] | Nickolls, J.; Dally, W. J., The GPU computing era, IEEE Micro, 30, 2, 56-69 (2010) |
| [6] | Blythe, D., Rise of the graphics processor, Proc IEEE, 96, 5, 761-778 (2008) |
| [7] | Hager, G.; Wellein, G., Introduction to high performance computing for scientists and engineers (2011), CRC Press |
| [8] | Rauber, T.; Runger, G., Parallel programming for multicore and cluster systems (2010), Springer · Zbl 1211.68073 |
| [9] | Owens, J. D.; Houston, M.; Luebke, D.; Green, S.; Stone, J. E.; Phillips, J. C., GPU computing, Proc IEEE, 96, 5, 879-899 (2008) |
| [10] | Owens, J. D.; Luebke, D.; Govindaraju, N.; Harris, M.; Krüger, J.; Lefohn, A. E., A survey of general-purpose computation on graphics hardware, Comput Graph Forum, 26, 1, 80-113 (2007) |
| [11] | Langdon, W. B., Debugging CUDA, Proceedings of the thirteenth annual conference companion on genetic and evolutionary computation GECCO ’11, 415-422 (2011), ACM: ACM New York, NY, USA |
| [13] | Liu, W.; Schmidt, B.; Voss, G.; Müller-Wittig, W., Molecular dynamics simulations on commodity GPUs with CUDA, (Aluru, S.; Parashar, M.; Badrinath, R.; Prasanna, V., High performance computing - HiPC 2007. High performance computing - HiPC 2007, Lecture Notes in Computer Science, vol. 4873 (2007), Springer Berlin Heidelberg), 185-196 |
| [14] | Luttmann, E.; Ensign, D. L.; Vaidyanathan, V.; Houston, M.; Rimon, N.; Oland, J., Accelerating molecular dynamic simulation on the cell processor and playstation 3, J Comput Chem, 30, 2, 268-274 (2009) |
| [15] | Wirawan, A.; Schimidt, B.; Zhang, H.; Kowoh, C. K., High performance protein sequence database scanning on the cell broadband engine, Sci Progr, 17, 1-2, 97-111 (2009) |
| [16] | Liu, W.; Schmidt, B.; Voss, G.; Müller-Wittig, W., Accelerating molecular dynamics simulations using graphics processing units with CUDA, Comput Phys Commun, 179, 9, 634-641 (2008) |
| [17] | Dickson, N. G.; Karimi, K.; Hamze, F., Importance of explicit vectorization for CPU and GPU software performance, J Comput Phys, 230, 13, 5383-5398 (2011) |
| [18] | Preis, T.; Virnau, P.; Paul, W.; Schneider, J. J., GPU accelerated Monte Carlo simulation of the 2D and 3D Ising model, J Comput Phys, 228, 12, 4468-4477 (2009) · Zbl 1167.82347 |
| [19] | Tomov, S.; McGuigan, M.; Bennett, R.; Smith, G.; Spiletic, J., Benchmarking and implementation of probability-based simulations on programmable graphics cards, Comput Graph, 29, 1, 71-80 (2005) |
| [20] | Ho, T.-Y.; Lam, P.-M.; Leung, C.-S., Parallelization of cellular neural networks on GPU, Pattern Recognit, 41, 8, 2684-2692 (2008) · Zbl 1147.68675 |
| [21] | Oh, K.-S.; Jung, K., GPU implementation of neural networks, Pattern Recognit, 37, 6, 1311-1314 (2004) · Zbl 1070.68555 |
| [22] | Dixon, P. R.; Oonishi, T.; Furui, S., Harnessing graphics processors for the fast computation of acoustic likelihoods in speech recognition, Comput Speech Lang, 23, 4, 510-526 (2009) |
| [23] | Scanzio, S.; Cumani, S.; Gemello, R.; Mana, F.; Laface, P., Parallel implementation of artificial neural network training for speech recognition, Pattern Recognit Lett, 31, 11, 1302-1309 (2010) |
| [24] | Nasse, F.; Thurau, C.; Fink, G. A., Face detection using GPU-based convolutional neural networks, (Jiang, X.; Petkov, N., Computer analysis of images and patterns. Computer analysis of images and patterns, Lecture Notes in Computer Science, vol. 5702 (2009), Springer Berlin Heidelberg), 83-90 |
| [25] | Lopes, N.; Ribeiro, B., An evaluation of multiple feed-forward networks on GPUs, Int J Neural Syst, 21, 01, 31-47 (2011) |
| [26] | Eklund, A.; Andersson, M.; Knutsson, H., fMRI analysis on the GPU - possibilities and challenges, Comput Methods Progr Biomed, 105, 2, 145-161 (2012) |
| [27] | Eklund, A.; Dufort, P.; Forsberg, D.; LaConte, S. M., Medical image processing on the GPU - past, present and future, Med Image Anal, 17, 8, 1073-1094 (2013) |
| [28] | Fluck, O.; Vetter, C.; Wein, W.; Kamen, A.; Preim, B.; Westermann, R., A survey of medical image registration on graphics hardware, Comput Methods Progr Biomed, 104, 3, e45-e57 (2011) |
| [29] | Hlawatsch, M.; Vollrath, J. E.; Sadlo, F.; Weiskopf, D., Coherent structures of characteristic curves in symmetric second order tensor fields, IEEE Trans Vis Comput Graph, 17, 6, 781-794 (2011) |
| [30] | Kutter, O.; Shams, R.; Navab, N., Visualization and GPU-accelerated simulation of medical ultrasound from CT images, Comput Methods Progr Biomed, 94, 3, 250-266 (2009) |
| [31] | Shams, R.; Sadeghi, P.; Kennedy, R.; Hartley, R., Parallel computation of mutual information on the GPU with application to real-time registration of 3D medical images, Comput Methods Progr Biomed, 99, 2, 133-146 (2010) |
| [32] | Stone, S. S.; Haldar, J. P.; Tsao, S. C.; Hwu, W.-m. W.; Sutton, B. P.; Liang, Z. P., Accelerating advanced MRI reconstructions on GPUs, J Parallel Distrib Comput, 68, 10, 1307-1318 (2008) |
| [33] | Izhikevich, E. M., Simple model of spiking neurons, IEEE Trans Neural Netw, 14, 6, 1569-1572 (2003) |
| [34] | Izhikevich, E. M., Dynamical systems in neuroscience - The geometry of excitability and bursting (2007), The MIT Press |
| [35] | Bernhard, F.; Keriven, R., Spiking neurons on GPUs, (Alexandrov, V. N.; van Albada, G. D.; Sloot, P. M.A.; Dongarra, J., Computational science - ICCS 2006. Computational science - ICCS 2006, Lecture Notes in Computer Science, vol. 3994 (2006), Springer Berlin Heidelberg: Springer Berlin Heidelberg Reading, UK), 236-243 |
| [36] | Fidjeland, A. K.; Roesch, E. B.; Shanahan, M. P.; Luk, W., NeMo: A platform for neural modelling of spiking neurons using GPUs, Proceedings of the twentieth IEEE international conference on application-specific Systems, architectures and processors, 2009, ASAP 2009, Boston, MA, 137-144 (2009) |
| [37] | Fidjeland, A. K.; Shanahan, M. P., Accelerated simulation of spiking neural networks using GPUs, Proceedings of the 2010 international joint conference on neural networks (IJCNN), 1-8 (2010) |
| [38] | Igarashi, J.; Shouno, O.; Fukai, T.; Tsujino, H., Real-time simulation of a spiking neural network model of the basal ganglia circuitry using general purpose computing on graphics processing units, Neural Netw, 24, 9, 950-960 (2011) |
| [39] | Nageswaran, J. M.; Dutt, N.; Krichmar, J. L.; Nicolau, A.; Veidenbaum, A., Efficient simulation of large-scale spiking neural networks using CUDA graphics processors, Proceedings of the international joint conference on neural networks, 2009 (IJCNN 2009)., 2145-2152 (2009) |
| [40] | Frezzotti, A.; Ghiroldi, G. P.; Gibelli, L., Solving the Boltzmann equation on GPUs, Comput Phys Commun, 182, 12, 2445-2453 (2011) · Zbl 1308.65009 |
| [41] | Kloss, Y. Y.; Shuvalov, P. V.; Tcheremissine, F. G., Solving Boltzmann equation on GPU, Procedia Comput Sci, 1, 1, 1083-1091 (2010) |
| [42] | Kuznik, F.; Obrecht, C.; Rusaouen, G.; Roux, J. J., LBM based flow simulation using GPU computing processor, Comput Math Appl, 59, 7, 2380-2392 (2010) · Zbl 1193.76112 |
| [43] | Nandapalan, N.; Brent, R. P.; Murray, L. M.; Rendell, A. P., High-performance pseudo-random number generation on graphics processing units, (Wyrzykowski, R.; Dongarra, J.; Karczewski, K.; Waśniewski, J., Parallel processing and applied mathematics. Parallel processing and applied mathematics, Lecture Notes in Computer Science, vol. 7203 (2012), Springer Berlin Heidelberg), 609-618 |
| [44] | Rinaldi, P. R.; Dari, E. A.; Vénere, M. J.; Clausse, A., Uso de GPUs para La Simulación de Fluidos en 3D con El Método de Lattice Boltzmann, Mec Comput, XXIX, 72, 7095-7108 (2010) |
| [45] | Mancho, A. M.; Small, D.; Wiggins, S., A tutorial on dynamical systems concepts applied to Lagrangian transport in oceanic flows defined as finite time data sets: Theoretical and computational issues, Phys Rep, 437, 3-4, 55-124 (2006) |
| [46] | Mancho, A. M.; Wiggins, S.; Curbelo, J.; Mendoza, C., Lagrangian descriptors: A method for revealing phase space structures of general time dependent dynamical systems, Commun Nonlinear Sci Numer Simul, 18, 12, 3530-3557 (2013) · Zbl 1344.37031 |
| [47] | Wiggins, S., The dynamical systems approach to Lagrangian transport in oceanic flows, Ann Rev Fluid Mech, 37, 1, 295-328 (2005) · Zbl 1117.76058 |
| [48] | Domínguez, J. M.; Crespo, A. J.C.; Valdez-Balderas, D.; Rogers, B. D.; Gómez-Gesteira, M., New multi-GPU implementation for smoothed particle hydrodynamics on heterogeneous clusters, Comput Phys Commun, 184, 8, 1848-1860 (2013) |
| [49] | Molnár Jr., F.; Szakály, T.; Mészáros, R.; Lagzi, I., Air pollution modelling using a graphics processing unit with CUDA, Comput Phys Commun, 181, 1, 105-112 (2010) · Zbl 1202.92085 |
| [50] | Singh, B.; Pardyjak, E. R.; Norgren, A.; Willemsen, P., Accelerating urban fast response Lagrangian dispersion simulations using inexpensive graphics processor parallelism, Environ Model Softw, 26, 6, 739-750 (2011) |
| [51] | Garth, C.; Li, G.-S.; Tricoche, X.; Hansen, C. D.; Hagen, H., Visualization of coherent structures in transient 2D flows, (Hege, H. C.; Polthier, K.; Scheuermann, G., Topology-based methodsin visualization II (mathematics and visualization) (2009), Springer Berlin Heidelberg), 1-13 · Zbl 1188.68339 |
| [52] | Sadlo, F.; Peikert, R., Visualizing Lagrangian coherent structures and comparison to vector field topology, (Hege, H. C.; Polthier, K.; Scheuermann, G., Topology-based methods in visualization II (mathematics and visualization) (2009), Springer Berlin Heidelberg), 15-29 · Zbl 1160.94308 |
| [53] | Gilmore, R.; McCallum, J. W.L., Structure in the bifurcation diagram of the Duffing oscillator, Phys Rev E, 51, 2, 935-956 (1995) |
| [54] | Guckenheimer, J.; Holmes, P., Nonlinear oscillations, dynamical systems, and bifurcations of vector fields. Nonlinear oscillations, dynamical systems, and bifurcations of vector fields, Applied Mathematical Sciences, vol. 42 (2000), Springer · Zbl 0515.34001 |
| [55] | Kanamaru, T., Duffing oscillator, Scholarpedia, 3, 3, 6327 (2008) |
| [56] | Mira, C.; Touzani-Qriouet, M.; Kawakami, H., Bifurcation structures generated by the nonautonomous Duffing equation, Int J Bifurc Chaos, 9, 7, 1363-1379 (1999) · Zbl 0970.34031 |
| [57] | Lekien, F.; Shadden, S. C.; Marsden, J. E., Lagrangian coherent structures in n-dimensional systems, J Math Phys, 48, 6, 065404 (2007) · Zbl 1144.81374 |
| [58] | Shadden, S. C.; Astorino, M.; Gerbeau, J. F., Computational analysis of an aortic valve jet with Lagrangian coherent structures, Chaos, 20, 1, 017512 (2010) |
| [59] | Shadden, S. C.; Dabiri, J. O.; Marsden, J. E., Lagrangian analysis of fluid transport in empirical vortex ring flows, Phys Fluids, 18, 4, 047105 (2006) · Zbl 1185.76700 |
| [60] | Shadden, S. C.; Lekien, F.; Marsden, J. E., Definition and properties of Lagrangian coherent structures from finite-time Lyapunov exponents in two-dimensional aperiodic flows, Physica D, 212, 3-4, 271-304 (2005) · Zbl 1161.76487 |
| [62] | Sharma, G.; Martin, J., MATLAB: A language for parallel computing, Int J Parallel Progr, 37, 1, 3-36 (2009) · Zbl 1191.68892 |
| [63] | Soriano, D. C.; Fazanaro, F. I.; Suyama, R.; Oliveira, J. R.; Attux, R.; Madrid, M. K., A method for Lyapunov spectrum estimation using cloned dynamics and its application to the discontinuously-excited FitzHugh-Nagumo model, Nonlinear Dyn, 67, 1, 413-424 (2012) · Zbl 1242.93105 |
| [64] | Januszewski, M.; Kostur, M., Accelerating numerical solution of stochastic differential equations with CUDA, Comput Phys Commun, 181, 1, 183-188 (2010) · Zbl 1205.65024 |
| [66] | Murray, L., GPU acceleration of Runge-Kutta integrators, IEEE Trans Parallel Distrib Syst, 23, 1, 94-101 (2012) |
| [67] | Shure, L., A Mandelbrot set on MATLAB (2011), The Mathworks, Inc. |
| [68] | Boffetta, G.; Cencini, M.; Falcioni, M.; Vulpiani, A., Predictability: a way to characterize complexity, Phys Rep, 356, 6, 367-474 (2002) · Zbl 0977.37005 |
| [69] | Monti, M.; Pardo, W. B.; Walkenstein, J. A.; Rosa Jr., E.; Grebogi, C., Color map of Lyapunov exponents of invariant sets, Int J Bifurc Chaos, 9, 7, 1459-1463 (1999) · Zbl 0964.37021 |
| [70] | Parker, T. S.; Chua, L. O., Practical numerical algorithms for chaotic systems (1989), Springer-Verlag · Zbl 0692.58001 |
| [71] | Wolf, A.; Swift, J. B.; Swinney, H. L.; Vastano, J. A., Determining Lyapunov exponents from a time series, Physica D, 16, 3, 285-317 (1985) · Zbl 0585.58037 |
| [72] | Leine, R. I., The historical development of classical stability concepts: Lagrange, Poisson and Lyapunov stability, Nonlinear Dyn, 59, 1-2, 173-182 (2010) · Zbl 1183.70002 |
| [73] | Anishchenko, V. S.; Astakhov, V.; Neiman, A.; Vadivasova, T.; Schimansky-Geier, L., Nonlinear dynamics of chaotic and stochastic systems: Tutorial and modern developments (2007), Springer · Zbl 1125.37001 |
| [74] | Shimada, I.; Nagashima, T., A numerical approach to ergodic problem of dissipative dynamical systems, Prog Theor Phys, 61, 6, 1605-1616 (1979) · Zbl 1171.34327 |
| [75] | Benettin, G.; Galgani, L.; Giorgilli, A.; Strelcyn, J.-M., Lyapunov characteristic exponents for smooth dynamical systems and for Hamiltonian systems; A method for computing all of them. Part 2: Numerical application, Meccanica, 15, 1, 21-30 (1980) |
| [76] | Fazanaro, F. I.; Soriano, D. C.; Suyama, R.; Madrid, M. K.; Attux, R.; Oliveira, J. R., Information generation and Lagrangian coherent structures in multiscroll attractors, Proceedings of the third IFAC conference on analysis and control of chaotic systems 2012, Cancún, México, vol. 3, 47-52 (2012) |
| [77] | Fazanaro, F. I.; Soriano, D. C.; Suyama, R.; Madrid, M. K.; Attux, R.; Oliveira, J. R., Characterization of multiscroll attractors using Lyapunov exponents and Lagrangian coherent structures, Chaos, 23, 2, 023105 (2013) · Zbl 1331.37123 |
| [78] | Haller, G., Finding finite-time invariant manifolds in two-dimensional velocity fields, Chaos, 10, 1, 99-108 (2000) · Zbl 0979.37012 |
| [79] | Haller, G., Distinguished material surfaces and coherent structures in three-dimensional fluid flows, Physica D, 149, 4, 248-277 (2001) · Zbl 1015.76077 |
| [80] | Haller, G., Lagrangian structures and the rate of strain in a partition of two-dimensional turbulence, Phys Fluids, 13, 11, 3365-3386 (2001) · Zbl 1184.76207 |
| [81] | Haller, G., Lagrangian coherent structures from approximate velocity data, Phys Fluids, 14, 6, 1851-1861 (2002) · Zbl 1185.76161 |
| [82] | Haller, G., A variational theory of hyperbolic Lagrangian coherent structures, Physica D, 240, 7, 574-598 (2011) · Zbl 1214.37056 |
| [83] | Haller, G.; Sapsis, T., Lagrangian coherent structures and the smallest finite-time Lyapunov exponent, Chaos, 21, 2, 023115 (2011) · Zbl 1317.37106 |
| [84] | Haller, G.; Yuan, G., Lagrangian coherent structures and mixing in two-dimensional turbulence, Physica D, 147, 3-4, 352-370 (2000) · Zbl 0970.76043 |
| [85] | Peacock, T.; Dabiri, J., Introduction to focus issue: Lagrangian coherent structures, Chaos, 20, 1, 017501 (2010) |
| [86] | Olcay, A. B.; Pottebaum, T. S.; Krueger, P. S., Sensitivity of Lagrangian coherent structure identification to flow field resolution and random errors, Chaos, 20, 1, 017506 (2010) · Zbl 1311.76035 |
| [87] | Brunton, S. L.; Rowley, C. W., Fast computation of finite-time Lyapunov exponent fields for unsteady flows, Chaos, 20, 1, 017503 (2010) · Zbl 1311.76102 |
| [88] | Conti, C.; Rossinelli, D.; Koumoutsakos, P., GPU and APU computations of finite time Lyapunov exponent fields, J Comput Phys, 231, 5, 2229-2244 (2012) · Zbl 1426.76524 |
| [89] | Lipinski, D.; Mohseni, K., A ridge tracking algorithm and error estimate for efficient computation of Lagrangian coherent structures, Chaos, 20, 1, 017504 (2010) · Zbl 1311.76034 |
| [90] | Dziekonski, A.; Sypek, P.; Lamecki, A.; Mrozowski, M., Generation of large finite-element matrices on multiple graphics processors, Int J Numer Methods Eng, 94, 2, 204-220 (2013) · Zbl 1352.65494 |
| [91] | Albuquerque, H. A.; Rech, P. C., A Parameter-Space of a Chua System with a smooth nonlinearity, Int J Bifurc Chaos, 19, 4, 1351-1355 (2009) |
| [92] | Albuquerque, H. A.; Rubinger, R. M.; Rech, P. C., Self-similar structures in a 2D parameter-space of an inductorless Chua’s circuit, Phys Lett A, 372, 27-28, 4793-4798 (2008) · Zbl 1221.37233 |
| [93] | Albuquerque, H. A.; Rubinger, R. M.; Rech, P. C., Theoretical and experimental time series analysis of an inductorless Chua’s circuit, Physica D, 233, 1, 66-72 (2007) · Zbl 1126.37051 |
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.
