Randomized methods to characterize large-scale vortical flow networks
Autoři:
Zhe Bai aff001; N. Benjamin Erichson aff002; Muralikrishnan Gopalakrishnan Meena aff003; Kunihiko Taira aff003; Steven L. Brunton aff004
Působiště autorů:
Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA, United States of America
aff001; Department of Applied Mathematics, University of Washington, Seattle, WA, United States of America
aff002; Department of Mechanical and Aerospace Engineering, University of California, Los Angeles, CA, United States of America
aff003; Department of Mechanical Engineering, University of Washington, Seattle, WA, United States of America
aff004
Vyšlo v časopise:
PLoS ONE 14(11)
Kategorie:
Research Article
prolekare.web.journal.doi_sk:
https://doi.org/10.1371/journal.pone.0225265
Souhrn
We demonstrate the effective use of randomized methods for linear algebra to perform network-based analysis of complex vortical flows. Network theoretic approaches can reveal the connectivity structures among a set of vortical elements and analyze their collective dynamics. These approaches have recently been generalized to analyze high-dimensional turbulent flows, for which network computations can become prohibitively expensive. In this work, we propose efficient methods to approximate network quantities, such as the leading eigendecomposition of the adjacency matrix, using randomized methods. Specifically, we use the Nyström method to approximate the leading eigenvalues and eigenvectors, achieving significant computational savings and reduced memory requirements. The effectiveness of the proposed technique is demonstrated on two high-dimensional flow fields: two-dimensional flow past an airfoil and two-dimensional turbulence. We find that quasi-uniform column sampling outperforms uniform column sampling, while both feature the same computational complexity.
Klíčová slova:
Linear algebra – Eigenvalues – Eigenvectors – Centrality – Turbulence – Fluid flow – Flow field – Singular value decomposition
Zdroje
1. Holmes PJ, Lumley JL, Berkooz G, Rowley CW. Turbulence, coherent structures, dynamical systems and symmetry. 2nd ed. Cambridge Monographs in Mechanics. Cambridge, England: Cambridge University Press; 2012.
2. Taira K, Brunton SL, Dawson S, Rowley CW, Colonius T, McKeon BJ, et al. Modal analysis of fluid flows: An overview. AIAA Journal. 2017;55(12):4013–4041. doi: 10.2514/1.J056060
3. Taira K, Hemati MS, Brunton SL, Sun Y, Duraisamy K, Bagheri S, et al. Modal Analysis of Fluid Flows: Applications and Outlook. accepted, AIAA Journal. 2019. doi: 10.2514/1.J058462
4. Noack BR, Afanasiev K, Morzynski M, Tadmor G, Thiele F. A hierarchy of low-dimensional models for the transient and post-transient cylinder wake. Journal of Fluid Mechanics. 2003;497:335–363. doi: 10.1017/S0022112003006694
5. Schmid PJ. Dynamic Mode Decomposition of Numerical and Experimental Data. Journal of Fluid Mechanics. 2010;656:5–28. doi: 10.1017/S0022112010001217
6. Rowley CW, Mezić I, Bagheri S, Schlatter P, Henningson DS. Spectral analysis of nonlinear flows. Journal of Fluid Mechanics. 2009;645:115–127. doi: 10.1017/S0022112009992059
7. Kutz JN, Brunton SL, Brunton BW, Proctor JL. Dynamic Mode Decomposition: Data-Driven Modeling of Complex Systems. SIAM; 2016.
8. Dullerud GE, Paganini F. A course in robust control theory: A convex approach. Texts in Applied Mathematics. Berlin, Heidelberg: Springer; 2000.
9. Bagheri S, Hoepffner J, Schmid PJ, Henningson DS. Input-output analysis and control design applied to a linear model of spatially developing flows. Applied Mechanics Reviews. 2009;62(2):020803–1–020803–27. doi: 10.1115/1.3077635
10. Brunton SL, Noack BR. Closed-loop turbulence control: Progress and challenges. Applied Mechanics Reviews. 2015;67:050801–1–050801–48. doi: 10.1115/1.4031175
11. Sipp D, Schmid PJ. Linear Closed-Loop Control of Fluid Instabilities and Noise-Induced Perturbations: A Review of Approaches and Tools. Applied Mechanics Reviews. 2016;68(2):020801. doi: 10.1115/1.4033345
12. Carlberg K, Barone M, Antil H. Galerkin v. least-squares Petrov–Galerkin projection in nonlinear model reduction. Journal of Computational Physics. 2017;330:693–734. doi: 10.1016/j.jcp.2016.10.033
13. Loiseau JC, Brunton SL. Constrained Sparse Galerkin Regression. Journal of Fluid Mechanics. 2018;838:42–67. doi: 10.1017/jfm.2017.823
14. Loiseau JC, Noack BR, Brunton SL. Sparse reduced-order modeling: sensor-based dynamics to full-state estimation. Journal of Fluid Mechanics. 2018;844:459–490. doi: 10.1017/jfm.2018.147
15. Nair AG, Taira K. Network-theoretic approach to sparsified discrete vortex dynamics. Journal of Fluid Mechanics. 2015;768:549–571. doi: 10.1017/jfm.2015.97
16. Murugesan M, Sujith R. Combustion noise is scale-free: transition from scale-free to order at the onset of thermoacoustic instability. Journal of Fluid Mechanics. 2015;772:225–245. doi: 10.1017/jfm.2015.215
17. Taira K, Nair AG, Brunton SL. Network structure of two-dimensional decaying isotropic turbulence. Journal of Fluid Mechanics. 2016;795. doi: 10.1017/jfm.2016.235
18. Schlueter-Kuck KL, Dabiri JO. Coherent structure colouring: identification of coherent structures from sparse data using graph theory. Journal of Fluid Mechanics. 2017;811:468–486. doi: 10.1017/jfm.2016.755
19. Gopalakrishnan Meena M, Nair AG, Taira K. Network community-based model reduction for vortical flows. Physical Review E. 2018;97(6):063103. doi: 10.1103/PhysRevE.97.063103 30011542
20. Murayama S, Kinugawa H, Tokuda IT, Gotoda H. Characterization and detection of thermoacoustic combustion oscillations based on statistical complexity and complex-network theory. Physical Review E. 2018;97(2):022223. doi: 10.1103/PhysRevE.97.022223 29548163
21. Iacobello G, Scarsoglio S, Kuerten J, Ridolfi L. Lagrangian network analysis of turbulent mixing. Journal of Fluid Mechanics. 2019;865:546–562. doi: 10.1017/jfm.2019.79
22. Newman MEJ. Networks: an introduction. Oxford Univ. Press; 2010.
23. Mesbahi M, Egerstedt M. Graph theoretic methods in multiagent networks. Princeton University Press; 2010.
24. Rahmani A, Ji M, Mesbahi M, Egerstedt M. Controllability of multi-agent systems from a graph-theoretic perspective. SIAM J Control and Optimization. 2009;48(1):162–186. doi: 10.1137/060674909
25. Low SH, Paganini F, Doyle JC. Internet congestion control. Control Systems, IEEE. 2002;22(1):28–43. doi: 10.1109/37.980245
26. Doyle JC, Alderson DL, Li L, Low S, Roughan M, Shalunov S, et al. The “robust yet fragile” nature of the Internet. Proceedings of the National Academy of Sciences of the United States of America. 2005;102(41):14497–14502. doi: 10.1073/pnas.0501426102
27. Susuki Y, Mezić I, Hikihara T. Coherent swing instability of power grids. Journal of nonlinear science. 2011;21(3):403–439. doi: 10.1007/s00332-010-9087-5
28. Leonard NE, Fiorelli E. Virtual leaders, artificial potentials and coordinated control of groups. In: Decision and Control, 2001. Proceedings of the 40th IEEE Conference on. vol. 3. IEEE; 2001. p. 2968–2973.
29. Olfati-Saber R. Flocking for multi-agent dynamic systems: Algorithms and theory. Automatic Control, IEEE Transactions on. 2006;51(3):401–420. doi: 10.1109/TAC.2005.864190
30. Balch T, Arkin RC. Behavior-based formation control for multirobot teams. Robotics and Automation, IEEE Transactions on. 1998;14(6):926–939. doi: 10.1109/70.736776
31. Cortes J, Martinez S, Karatas T, Bullo F. Coverage control for mobile sensing networks. In: IEEE International Conference on Robotics and Automation (ICRA). vol. 2. IEEE; 2002. p. 1327–1332.
32. Leonard NE, Paley DA, Lekien F, Sepulchre R, Fratantoni DM, Davis RE. Collective motion, sensor networks, and ocean sampling. Proceedings of the IEEE. 2007;95(1):48–74. doi: 10.1109/JPROC.2006.887295
33. Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U. Network motifs: simple building blocks of complex networks. Science. 2002;298(5594):824–827. doi: 10.1126/science.298.5594.824 12399590
34. Luscombe NM, Babu MM, Yu H, Snyder M, Teichmann SA, Gerstein M. Genomic analysis of regulatory network dynamics reveals large topological changes. Nature. 2004;431(7006):308–312. doi: 10.1038/nature02782 15372033
35. Nair AG, Taira K, Brunton SL. Networked oscillator based modeling and control of unsteady wake flows. Physical Review E. 2018;97(063107).
36. Halko N, Martinsson PG, Tropp JA. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review. 2011;53(2):217–288. doi: 10.1137/090771806
37. Drineas P, Mahoney MW. RandNLA: Randomized Numerical Linear Algebra. Commun ACM. 2016;59(6):80–90. doi: 10.1145/2842602
38. Kannan R, Vempala S. Randomized algorithms in numerical linear algebra. Acta Numerica. 2017;26:95–135. doi: 10.1017/S0962492917000058
39. Woodruff DP, et al. Sketching as a tool for numerical linear algebra. Foundations and Trends® in Theoretical Computer Science. 2014;10(1–2):1–157.
40. Erichson NB, Voronin S, Brunton SL, Kutz JN. Randomized Matrix Decompositions Using R. Journal of Statistical Software. 2019;89(11):1–48. doi: 10.18637/jss.v089.i11
41. Nair AG, Yeh CA, Kaiser E, Noack BR, Brunton SL, Taira K. Cluster-based feedback control of turbulent post-stall separated flows. Journal of Fluid Mechanics, accepted. 2019. doi: 10.1017/jfm.2019.469
42. Page L, Brin S, Motwani R, Winograd T. The PageRank citation ranking: Bringing order to the web. Stanford InfoLab; 1999.
43. Kolaczyk ED, Csárdi G. Statistical analysis of network data with R. vol. 65. Springer; 2014.
44. Clauset A, Newman ME, Moore C. Finding community structure in very large networks. Physical review E. 2004;70(6):066111. doi: 10.1103/PhysRevE.70.066111
45. Leicht EA, Newman ME. Community structure in directed networks. Physical review letters. 2008;100(11):118703. doi: 10.1103/PhysRevLett.100.118703 18517839
46. Trefethen LN, Bau D III. Numerical Linear Algebra. vol. 50. SIAM; 1997.
47. Bryan K, Leise T. The $25,000,000,000 eigenvector: The linear algebra behind Google. SIAM Review. 2006;48(3):569–581. doi: 10.1137/050623280
48. Mahoney MW. Randomized Algorithms for Matrices and Data. Foundations and Trends in Machine Learning. 2011;3:123–224.
49. Drineas P, Mahoney MW. RandNLA: Randomized Numerical Linear Algebra. Commun ACM. 2016;59(6):80–90. doi: 10.1145/2842602
50. Liberty E, Woolfe F, Martinsson PG, Rokhlin V, Tygert M. Randomized algorithms for the low-rank approximation of matrices. Proceedings of the National Academy of Sciences. 2007;104(51):20167–20172. doi: 10.1073/pnas.0709640104
51. Sarlos T. Improved Approximation Algorithms for Large Matrices via Random Projections. In: Foundations of Computer Science. 47th Annual IEEE Symposium on; 2006. p. 143–152.
52. Martinsson PG, Rokhlin V, Tygert M. A Randomized Algorithm for the Decomposition of Matrices. Applied and Computational Harmonic Analysis. 2011;30:47–68. doi: 10.1016/j.acha.2010.02.003
53. Erichson NB, Brunton SL, Kutz JN. Compressed singular value decomposition for image and video processing. In: Proceedings of the IEEE International Conference on Computer Vision; 2017. p. 1880–1888.
54. Woolfe F, Liberty E, Rokhlin V, Tygert M. A Fast Randomized Algorithm for the Approximation of Matrices. Journal of Applied and Computational Harmonic Analysis. 2008;25:335–366. doi: 10.1016/j.acha.2007.12.002
55. Liberty E. Simple and Deterministic Matrix Sketching. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM; 2013. p. 581–588.
56. Erichson NB, Donovan C. Randomized low-rank dynamic mode decomposition for motion detection. Computer Vision and Image Understanding. 2016;146:40–50. doi: 10.1016/j.cviu.2016.02.005
57. Erichson NB, Manohar K, Brunton SL, Kutz JN. Randomized CP tensor decomposition. arXiv preprint arXiv:170309074. 2017.
58. Erichson NB, Mendible A, Wihlborn S, Kutz JN. Randomized nonnegative matrix factorization. Pattern Recognition Letters. 2018;104:1–7. doi: 10.1016/j.patrec.2018.01.007
59. Erichson NB, Brunton SL, Kutz JN. Compressed dynamic mode decomposition for background modeling. Journal of Real-Time Image Processing. 2016; p. 1–14.
60. Shabat G, Shmueli Y, Aizenbud Y, Averbuch A. Randomized LU decomposition. Applied and Computational Harmonic Analysis. 2018;44(2):246–272. doi: 10.1016/j.acha.2016.04.006
61. Rokhlin V, Szlam A, Tygert M. A Randomized Algorithm for Principal Component Analysis. SIAM Journal on Matrix Analysis and Applications. 2009;31:1100–1124. doi: 10.1137/080736417
62. Frieze A, Kannan R, Vempala S. Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. Journal of the ACM. 2004;51(6):1025–1041. doi: 10.1145/1039488.1039494
63. Ma P, Mahoney MW, Yu B. A statistical perspective on algorithmic leveraging. Journal of Machine Learning Research. 2015;16(1):861–911.
64. Drineas P, Mahoney MW, Muthukrishnan S. Sampling algorithms for l 2 regression and applications. In: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. Society for Industrial and Applied Mathematics; 2006. p. 1127–1136.
65. Drineas P, Magdon-Ismail M, Mahoney MW, Woodruff DP. Fast approximation of matrix coherence and statistical leverage. Journal of Machine Learning Research. 2012;13(Dec):3475–3506.
66. Talwalkar A, Kumar S, Mohri M, Rowley H. Large-scale SVD and manifold learning. Journal of Machine Learning Research. 2013;14(1):3129–3152.
67. Niederreiter H. Random number generation and quasi-Monte Carlo methods. SIAM; 1992.
68. Halton JH. Algorithm 247: Radical-inverse Quasi-random Point Sequence. Commun ACM. 1964;7(12):701–702. doi: 10.1145/355588.365104
69. Williams CK, Seeger M. Using the Nyström method to speed up kernel machines. In: Advances in neural information processing systems; 2001. p. 682–688.
70. Drineas P, Mahoney MW. On the Nyström method for approximating a Gram matrix for improved kernel-based learning. journal of machine learning research. 2005;6(Dec):2153–2175.
71. Zhang K, Tsang IW, Kwok JT. Improved Nyström low-rank approximation and error analysis. In: Proceedings of the 25th international conference on Machine learning. ACM; 2008. p. 1232–1239.
72. Gittens A, Mahoney MW. Revisiting the Nyström method for improved large-scale machine learning. The Journal of Machine Learning Research. 2016;17(1):3977–4041.
73. Kumar S, Mohri M, Talwalkar A. Sampling methods for the Nyström method. Journal of Machine Learning Research. 2012;13(Apr):981–1006.
74. Gopalakrishnan Meena M, Taira K, Asai K. Airfoil-Wake Modification with Gurney Flap at Low Reynolds Number. AIAA Journal. 2017;56(4):1348–1359. doi: 10.2514/1.J056260
75. Williamson CH, Roshko A. Vortex formation in the wake of an oscillating cylinder. Journal of Fluids and Structures. 1988;2(4):355–381. doi: 10.1016/S0889-9746(88)90058-8
76. Taira K, Colonius T. The immersed boundary method: a projection approach. Journal of Computational Physics. 2007;225(2):2118–2137. doi: 10.1016/j.jcp.2007.03.005
77. Colonius T, Taira K. A fast immersed boundary method using a nullspace approach and multi-domain far-field boundary conditions. Computer Methods in Applied Mechanics and Engineering. 2008;197:2131–2146. doi: 10.1016/j.cma.2007.08.014
78. Boffetta G, Ecke RE. Two-dimensional turbulence. Annual Review of Fluid Mechanics. 2012;44:427–451. doi: 10.1146/annurev-fluid-120710-101240
79. Kida S. Numerical simulation of two-dimensional turbulence with high-symmetry. Journal of the Physical Society of Japan. 1985;54(8):2840–2854. doi: 10.1143/JPSJ.54.2840
80. Dellnitz M, Froyland G, Junge O. The algorithms behind GAIO—Set oriented numerical methods for dynamical systems. In: Ergodic theory, analysis, and efficient simulation of dynamical systems. Springer; 2001. p. 145–174.
81. Dellnitz M, Junge O. Set oriented numerical methods for dynamical systems. Handbook of dynamical systems. 2002;2:221–264.
82. Froyland G, Padberg K. Almost-invariant sets and invariant manifolds—Connecting probabilistic and geometric descriptions of coherent structures in flows. Physica D. 2009;238:1507–1523. doi: 10.1016/j.physd.2009.03.002
83. Froyland G, Santitissadeekorn N, Monahan A. Transport in time-dependent dynamical systems: Finite-time coherent sets. Chaos. 2010;20(4):043116–1–043116–16. doi: 10.1063/1.3502450
84. Tallapragada P, Ross SD. A set oriented definition of finite-time Lyapunov exponents and coherent sets. Communications in Nonlinear Science and Numerical Simulation. 2013;18(5):1106–1126. doi: 10.1016/j.cnsns.2012.09.017
85. Kaiser E, Noack BR, Cordier L, Spohn A, Segond M, Abel M, et al. Cluster-based reduced-order modelling of a mixing layer. J Fluid Mech. 2014;754:365–414. doi: 10.1017/jfm.2014.355
86. Amsallem D, Zahr MJ, Farhat C. Nonlinear model order reduction based on local reduced-order bases. International Journal for Numerical Methods in Engineering. 2012;92(10):891–916. doi: 10.1002/nme.4371
Článok vyšiel v časopise
PLOS One
2019 Číslo 11
- Metamizol jako analgetikum první volby: kdy, pro koho, jak a proč?
- Nejasný stín na plicích – kazuistika
- Masturbační chování žen v ČR − dotazníková studie
- Úspěšná resuscitativní thorakotomie v přednemocniční neodkladné péči
- Dlouhodobá recidiva a komplikace spojené s elektivní operací břišní kýly
Najčítanejšie v tomto čísle
- A daily diary study on maladaptive daydreaming, mind wandering, and sleep disturbances: Examining within-person and between-persons relations
- A 3’ UTR SNP rs885863, a cis-eQTL for the circadian gene VIPR2 and lincRNA 689, is associated with opioid addiction
- A substitution mutation in a conserved domain of mammalian acetate-dependent acetyl CoA synthetase 2 results in destabilized protein and impaired HIF-2 signaling
- Molecular validation of clinical Pantoea isolates identified by MALDI-TOF