×

Randomized model order reduction. (English) Zbl 1418.65193

Summary: The singular value decomposition (SVD) has a crucial role in model order reduction. It is often utilized in the offline stage to compute basis functions that project the high-dimensional nonlinear problem into a low-dimensional model which is then evaluated cheaply. It constitutes a building block for many techniques such as the proper orthogonal decomposition (POD) and dynamic mode decomposition (DMD). The aim of this work is to provide an efficient computation of low-rank POD and/or DMD modes via randomized matrix decompositions. This is possible due to the randomized singular value decomposition (rSVD) which is a fast and accurate alternative of the SVD. Although this is considered an offline stage, this computation may be extremely expensive; therefore, the use of compressed techniques drastically reduce its cost. Numerical examples show the effectiveness of the method for both POD and DMD.

MSC:

65P99 Numerical problems in dynamical systems
37M05 Simulation of dynamical systems
65F30 Other matrix algorithms (MSC2010)
15B52 Random matrices (algebraic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Alla, A., Nathan Kutz, J.: Nonlinear model reduction via dynamic mode decomposition. SIAM J. Sci. Comput. 39, B778-B796 (2017) · Zbl 1373.65090 · doi:10.1137/16M1059308
[2] Barrault, M., Maday, Y., Nguyen, N.C., Patera, A.T.: An empirical interpolation method: application to efficient reduced-basis discretization of partial differential equations Comptes Rendus Mathematique, 339, pp. 667-672 (2004) · Zbl 1061.65118
[3] Benner, P., Gugercin, S., Willcox, K.: A survey of Projection-Based model reduction methods for parametric dynamical systems. SIAM Rev. 57, 483-531 (2015) · Zbl 1339.37089 · doi:10.1137/130932715
[4] Brunton, S.L., Proctor, J.L., Kutz, J.N.: Compressive sampling and dynamic mode decomposition. J. Comp. Dyn. 2, 165-191 (2015) · Zbl 1347.94012
[5] Chatarantabut, S., Sorensen, D.: Nonlinear model reduction via discrete empirical interpolation. SIAM J. Sci. Comput. 32, 2737-2764 (2010) · Zbl 1217.65169 · doi:10.1137/090766498
[6] Drineas, P., Mahoney, M.W.: RandNLA: randomized numerical linear algebra. Communications of the ACM 59.6, 80-90 (2016) · doi:10.1145/2842602
[7] Drmac, Z., Gugercin, S.: A new selection operator for the discrete empirical interpolation method - improved a priori error bound and extensions. SIAM J. S.i. Comput. 38, A631-A648 (2016) · Zbl 1382.65193 · doi:10.1137/15M1019271
[8] Duersch, J., Gu, M. (2015)
[9] Erichson, N.B., Voronin, S., Brunton, S.L., Kutz, J.N.: Randomized matrix decompositions using R, arXiv:1608.02148 (2016)
[10] Everson, R., Sirovich, L.: Karhunen-loéve procedure for gappy data. J. Opt. Soc. Am. A 12, 1657-1664 (1995) · doi:10.1364/JOSAA.12.001657
[11] Frieze, A., Ravi, K., Vempala, S.: Fast Monte-Carlo algorithms for finding low-rank approximations. Journal of the ACM (JACM) 51.6, 1025-1041 (2004) · Zbl 1125.65005 · doi:10.1145/1039488.1039494
[12] Gavish, M., Donoho, D.L.: The optimal hard threshold for singular values is \(4/\sqrt{3}4/\sqrt{3} \). IEEE Trans Inform. Theory 60, 5040-5053 (2014) · Zbl 1360.94071 · doi:10.1109/TIT.2014.2323359
[13] Halko, N., Martinsson, P.-G., Tropp, J.: Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53, 217-288 (2011) · Zbl 1269.65043 · doi:10.1137/090771806
[14] Isaac, T., Petra, N., Stadler, G., Ghattas, O.: Scalable and efficient algorithms for the propagation of uncertainty from data through inference to prediction for large-scale problems, with application to flow of the Antarctic ice sheet. J. Comp. Phys. 296, 348-368 (2015) · Zbl 1352.86017 · doi:10.1016/j.jcp.2015.04.047
[15] Koopman, B.O.: Hamiltonian systems and transformation in hilbert space. PNAS 17, 315-318 (1931) · Zbl 0002.05701 · doi:10.1073/pnas.17.5.315
[16] Kutz, J.N., Brunton, S., Brunton, B., Proctor, J.: Dynamic mode decomposition: Data-driven modeling of complex systems. SIAM Press (2016) · Zbl 1365.65009
[17] Liberty, E., Woolfe, F., Martinsson, P.-G., Rokhlin, V.: Randomized algorithms for the low-rank approximation of matrices. Proc. Natl. Acad. Sci. 104, 20167-20172 (2007) · Zbl 1215.65080 · doi:10.1073/pnas.0709640104
[18] Mahoney, M.W.: Randomized algorithms for matrices and data. Found. Trends Mach. Learn. 3.2, 123-224 (2011) · Zbl 1232.68173
[19] Martinsson, P.-G.: factorizations, blocked rank-revealing QR: how randomized sampling can be used to avoid single-vector pivoting. arXiv:1505.08115 (2015)
[20] Martinsson, P.-G., Rokhlin, V., Tygert, M.: A randomized algorithm for the decomposition of matrices. Appl. Comput. Harmon. Anal. 30, 47-68 (2011) · Zbl 1210.65095 · doi:10.1016/j.acha.2010.02.003
[21] Martinsson, P.-G.: Randomized methods for matrix computations and analysis of high dimensional data, arXiv:1607.01649 (2016)
[22] Martinsson, P.-G., Quintana-Orti, G., Heavner, N.: randUTV: A blocked randomized algorithm for computing a rank-revealing UTV factorization, arXiv:1703.00998 (2017) · Zbl 1471.65031
[23] Mezić, I., Banaszuk, A.: Comparison of systems with complex behavior. Physica D: Nonlinear Phenomena 197, 101-133 (2004) · Zbl 1059.37072 · doi:10.1016/j.physd.2004.06.015
[24] Mezić, I.: Spectral properties of dynamical systems, model reduction and decompositions. Nonlinear Dyn. 41, 309-325 (2005) · Zbl 1098.37023 · doi:10.1007/s11071-005-2824-x
[25] Mezić, I.: Analysis of fluid flows via spectral properties of the Koopman operator. Annu. Rev. Fluid Mech. 45, 357-378 (2013) · Zbl 1359.76271 · doi:10.1146/annurev-fluid-011212-140652
[26] Sirovich, L.: Turbulence and the dynamics of coherent structures. Parts I-II Q. Appl. Math. XVL, 561-590 (1987) · Zbl 0676.76047
[27] Szlam, A., Kluger, Y., Tygert, M.: An implementation of a randomized algorithm for principal component analysis, arXiv:1412.3510(2014) · Zbl 1391.65085
[28] Tu, J., Rowley, C., Luchtenberg, D., Brunton, S., Kutz, J.N.: On dynamic mode decomposition theory and applications. J. Comput. Dyn. 1, 391-421 (2014) · Zbl 1346.37064 · doi:10.3934/jcd.2014.1.391
[29] Volkwein, S.: Model Reduction Using Proper Orthogonal Decomposition. Lecture Notes, University of Konstanz (2013)
[30] Voronin, S., Martinsson, P.-G.: RSVDPACK: Subroutines for computing partial singular value decompositions via randomized sampling on single core, multi core, and GPU architectures, arXiv:1502.05366 (2015)
[31] Woolfe, F., Liberty, E., Rokhlin, V., Tygert, M.: A fast randomized algorithm for the approximation of matrices. Appl. Comput. Harmon. Anal. 25, 335-366 (2008) · Zbl 1155.65035 · doi:10.1016/j.acha.2007.12.002
[32] Zahm, O., Nouy, A.: Interpolation of inverse operators for precoditioning parameter-dependent equations. SIAM J. Sci. Comput. 38, 1004-1074 (2016) · Zbl 1382.65035 · doi:10.1137/15M1019210
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.