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
doi: 10.1371/journal.pone.0225265


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:

Centrality – Eigenvalues – Eigenvectors – Flow field – Fluid flow – Linear algebra – Turbulence – Singular value decomposition


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ánek vyšel v časopise


2019 Číslo 11