Skip to main content
SpringerLink
Log in

Randomized model order reduction

  • Published:
Advances in Computational Mathematics Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alla, A., Nathan Kutz, J.: Nonlinear model reduction via dynamic mode decomposition. SIAM J. Sci. Comput. 39, B778–B796 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  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)

    Article  MathSciNet  MATH  Google Scholar 

  4. Brunton, S.L., Proctor, J.L., Kutz, J.N.: Compressive sampling and dynamic mode decomposition. J. Comp. Dyn. 2, 165–191 (2015)

    MATH  Google Scholar 

  5. Chatarantabut, S., Sorensen, D.: Nonlinear model reduction via discrete empirical interpolation. SIAM J. Sci. Comput. 32, 2737–2764 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  6. Drineas, P., Mahoney, M.W.: RandNLA: randomized numerical linear algebra. Communications of the ACM 59.6, 80–90 (2016)

    Article  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gavish, M., Donoho, D.L.: The optimal hard threshold for singular values is \(4/\sqrt {3}\). IEEE Trans Inform. Theory 60, 5040–5053 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  15. Koopman, B.O.: Hamiltonian systems and transformation in hilbert space. PNAS 17, 315–318 (1931)

    Article  MATH  Google Scholar 

  16. Kutz, J.N., Brunton, S., Brunton, B., Proctor, J.: Dynamic mode decomposition: Data-driven modeling of complex systems. SIAM Press (2016)

  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)

    Article  MathSciNet  MATH  Google Scholar 

  18. Mahoney, M.W.: Randomized algorithms for matrices and data. Found. Trends Mach. Learn. 3.2, 123–224 (2011)

    MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  23. Mezić, I., Banaszuk, A.: Comparison of systems with complex behavior. Physica D: Nonlinear Phenomena 197, 101–133 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  24. Mezić, I.: Spectral properties of dynamical systems, model reduction and decompositions. Nonlinear Dyn. 41, 309–325 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  25. Mezić, I.: Analysis of fluid flows via spectral properties of the Koopman operator. Annu. Rev. Fluid Mech. 45, 357–378 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  26. Sirovich, L.: Turbulence and the dynamics of coherent structures. Parts I-II Q. Appl. Math. XVL, 561–590 (1987)

    MathSciNet  MATH  Google Scholar 

  27. Szlam, A., Kluger, Y., Tygert, M.: An implementation of a randomized algorithm for principal component analysis, arXiv:1412.3510(2014)

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  32. Zahm, O., Nouy, A.: Interpolation of inverse operators for precoditioning parameter-dependent equations. SIAM J. Sci. Comput. 38, 1004–1074 (2016)

    Article  MATH  Google Scholar 

Download references

Funding

This study is supported by the Department of Energy (grant no. DE-SC0009324) and the U.S. Air Force Office of Scientific Research (FA9550-15-1-0385).

Author information

Authors and Affiliations

  1. Department of Mathematics, PUC-Rio, Rio de Janeiro, 22451-900, Brazil

    Alessandro Alla

  2. Department of Applied Mathematics, University of Washington, Seattle, WA, 98195-3925, USA

    J. Nathan Kutz

Authors
  1. Alessandro Alla
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. Nathan Kutz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alessandro Alla.

Additional information

Communicated by: Anthony Patera

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Alla, A., Kutz, J.N. Randomized model order reduction. Adv Comput Math 45, 1251–1271 (2019). https://doi.org/10.1007/s10444-018-09655-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10444-018-09655-9

Keywords

Mathematics Subject Classification (2010)

Search

Navigation