The discrete empirical interpolation method: canonical structure and formulation in weighted inner product spaces. (English) Zbl 1415.65107
Summary: New contributions are offered to the theory and numerical implementation of the discrete empirical interpolation method (DEIM). A substantial tightening of the error bound for the DEIM oblique projection is achieved by index selection via a strong rank revealing QR factorization. This removes the exponential factor in the dimension of the search space from the DEIM projection error and allows sharper a priori error bounds. A well-known canonical structure of pairs of projections is used to reveal canonical structure of DEIM. Further, the DEIM approximation is formulated in weighted inner product defined by a real symmetric positive-definite matrix \(W\). The weighted DEIM (\(W\)-DEIM) can be interpreted as a numerical implementation of the generalized empirical interpolation method (GEIM) and the more general parametrized-background data-weak (PBDW) approach. Also, it can be naturally deployed in the framework when the POD Galerkin projection is formulated in a discretization of a suitable energy (weighted) inner product such that the projection preserves important physical properties, e.g., stability. While the theoretical foundations of weighted POD and the GEIM are available in the more general setting of function spaces, this paper focuses to the gap between sound functional analysis and the core numerical linear algebra. The new proposed algorithms allow different forms of \(W\)-DEIM for pointwise and generalized interpolation. For the generalized interpolation, our bounds show that the condition number of \(W\) does not affect the accuracy, and for pointwise interpolation the condition number of the weight matrix \(W\) enters the bound essentially as \(\sqrt{\min_{D=\mathrm{diag}}\kappa_2(DWD)}\), where \(\kappa_2(W)=\|W\|_2 \|W^{-1}\|_2\) is the spectral condition number.
MSC:
| 65F99 | Numerical linear algebra |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65M20 | Method of lines for initial value and initial-boundary value problems involving PDEs |
| 65M22 | Numerical solution of discretized equations for initial value and initial-boundary value problems involving PDEs |
| 65M60 | Finite element, Rayleigh-Ritz and Galerkin methods for initial value and initial-boundary value problems involving PDEs |
Keywords:
empirical interpolation; Galerkin projection; generalized empirical interpolation; nonlinear model reduction; oblique projection; proper orthogonal decomposition; parametrized-background data-weak approach; rank revealing QR factorization; weighted inner productReferences:
| [1] | D. Amsallem and J. Nordström, Energy stable model reduction of neurons by nonnegative discrete empirical interpolation, SIAM J. Sci. Comput., 38 (2016), pp. B297–B326, . · Zbl 1359.37145 |
| [2] | E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. J. Dongarra, J. Du Croz, S. Hammarling, A. Greenbaum, A. McKenney, and D. Sorensen, LAPACK Users’ Guide, 3rd ed., SIAM, Philadelphia, 1999. · Zbl 0934.65030 |
| [3] | P. Astrid, S. Weiland, K. Willcox, and T. Backx, Missing point estimation in models described by proper orthogonal decomposition, IEEE Trans. Automat. Control, 53 (2008), pp. 2237–2251, . · Zbl 1367.93110 |
| [4] | M. F. Barone, I. Kalashnikova, D. J. Segalman, and H. K. Thornquist, Stable Galerkin reduced order models for linearized compressible flow, J. Comput. Phys., 228 (2009), pp. 1932–1946. · Zbl 1162.76025 |
| [5] | M. Barrault, N. C. Nguyen, Y. Maday, and A. T. Patera, An empirical interpolation method: Application to efficient reduced-basis discretization of partial differential equations, C. R. Acad. Sci. Paris Sér. I, 339 (2004), pp. 667–672. · Zbl 1061.65118 |
| [6] | P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, and P. Wojtaszczyk, Data assimilation in reduced modeling, SIAM/ASA J. Uncertain. Quantif., 5 (2017), pp. 1–29, . · Zbl 06736493 |
| [7] | \AA. Björck, Numerical Methods in Matrix Computations, Springer, New York, 2015. · Zbl 1322.65047 |
| [8] | \AA. Björck and G. H. Golub, Numerical methods for computing angles between linear subspaces, Math. Comp., 27 (1973), pp. 579–594. · Zbl 0282.65031 |
| [9] | L. S. Blackford, J. Choi, A. Cleary, E. D’Azeuedo, J. Demmel, I. Dhillon, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, and R. C. Whaley, ScaLAPACK User’s Guide, SIAM, Philadelphia, 1997. · Zbl 0886.65022 |
| [10] | M. E. Broadbent, M. Brown, and K. Penner, Subset selection algorithms: Randomized vs. deterministic, SIAM Undergrad. Res. Online, 3 (2010), pp. 50–71. |
| [11] | P. A. Businger and G. H. Golub, Linear least squares solutions by Householder transformations, Numer. Math., 7 (1965), pp. 269–276. · Zbl 0142.11503 |
| [12] | V. M. Calo, Y. Efendiev, J. Galvis, and M. Ghommem, Multiscale empirical interpolation for solving nonlinear PDEs, J. Comput. Phys., 278 (2014), pp. 204–220. · Zbl 1349.65612 |
| [13] | F. Casenave, A. Ern, and T. Lelièvre, Variants of the empirical interpolation method: Symmetric formulation, choice of norms and rectangular extension, Appl. Math. Lett., 56 (2016), pp. 23–28. · Zbl 1337.65014 |
| [14] | S. Chandrasekaran and I. C. F. Ipsen, On rank-revealing QR factorisations, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 592–622. · Zbl 0796.65030 |
| [15] | S. Chaturantabut and D. C. Sorensen, Nonlinear model reduction via discrete empirical interpolation, SIAM J. Sci. Comput., 32 (2010), pp. 2737–2764. · Zbl 1217.65169 |
| [16] | M. Condon and R. Ivanov, Empirical balanced truncation of nonlinear systems, J. Nonlinear Sci., 14 (2004), pp. 405–414. · Zbl 1080.93006 |
| [17] | F. Deutsch, Best Approximation in Inner Product Spaces, CMS Books Math./Ouvrages Math. SMC 7, Springer, New York, 2001. · Zbl 0980.41025 |
| [18] | Z. Drmač and Z. Bujanović, On the failure of rank revealing QR factorization software—A case study, ACM Trans. Math. Software, 35 (2008), pp. 1–28. |
| [19] | Z. Drmač and S. Gugercin, A new selection operator for the discrete empirical interpolation method—Improved a priori error bound and extensions, SIAM J. Sci. Comput., 38 (2016), pp. A631–A648. · Zbl 1382.65193 |
| [20] | C. Farhat, T. Chapman, and P. Avery, Structure-preserving, stability, and accuracy properties of the energy-conserving sampling and weighting method for the hyper reduction of nonlinear finite element dynamic models, Internat. J. Numer. Methods Engrg., 102 (2015), pp. 1077–1110, . · Zbl 1352.74349 |
| [21] | J. B. Freund and T. Colonius, POD analysis of sound generation by a turbulent jet, in Proceedings of the 40th AIAA Aerospace Sciences Meeting, 2002. |
| [22] | G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037 |
| [23] | S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, A theory of pseudoskeleton approximations, Linear Algebra Appl., 261 (1997), pp. 1–21. · Zbl 0877.65021 |
| [24] | M. Grepl, Y. Maday, N. Nguyen, and A. Patera, Efficient reduced–basis treatment of nonaffine and nonlinear partial differential equations, ESAIM Math. Model. Numer. Anal., 41 (2007), pp. 575–605. · Zbl 1142.65078 |
| [25] | M. Gu and S. C. Eisenstat, Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM J. Sci. Comput., 17 (1996), pp. 848–869. · Zbl 0858.65044 |
| [26] | B. Haasdonk, M. Ohlberger, and G. Rozza, A reduced basis method for evolution schemes with parameter-dependent explicit operators, Electron. Trans. Numer. Anal., 32 (2008), pp. 145–161. · Zbl 1391.76413 |
| [27] | P. Holmes, J. Lumley, G. Berkooz, and C. Rowley, Turbulence, Coherent Structures, Dynamical Systems and Symmetry, Cambridge Monogr. Mech., Cambridge University Press, Cambridge, 2014. · Zbl 1251.76001 |
| [28] | I. C. F. Ipsen, Numerical Matrix Analysis, SIAM, Philadelphia, 2009. · Zbl 1173.65023 |
| [29] | I. C. F. Ipsen and C. D. Meyer, The angle between complementary subspaces, Amer. Math. Monthly, 102 (1995), pp. 904–911. · Zbl 0842.15002 |
| [30] | W. Kahan, Numerical linear algebra, Canad. Math. Bull., 9 (1965), pp. 757–801. · Zbl 0236.65025 |
| [31] | I. Kalashnikova and S. Arunajatesan, A stable Galerkin reduced order modeling (ROM) for compressible flow, in Proceedings of the 10th Wold Congress on Computational Mechanics, Blucher Mechanical Engineering Proceedings, 2014. |
| [32] | I. Kalashnikova, S. Arunajatesan, M. F. Barone, B. G. van Bloemen Waanders, and J. A. Fike, Reduced Order Modeling for Prediction and Control of Large–Scale Systems, Sandia report SAND2014–4693, Sandia National Laboratories, 2014. · Zbl 1296.93165 |
| [33] | I. Kalashnikova, M. F. Barone, S. Arunajatesan, and B. G. van Bloemen Waanders, Construction of energy-stable projection-based reduced order models, App. Math. Comput., 249 (2014), pp. 569–596. · Zbl 1339.65174 |
| [34] | D. E. Knuth, Semi-optimal bases for linear dependencies, Linear Multilinear Algebra, 17 (1985), pp. 1–4. · Zbl 0556.15001 |
| [35] | A. Kolmogoroff, Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse, Ann. of Math., 37 (1936), pp. 107–110. · JFM 62.0283.02 |
| [36] | M. A. Kowalski, K. A. Sikorski, and F. Stenger, Selected Topics in Approximation and Computation, Oxford University Press, Oxford, 1995. · Zbl 0839.41001 |
| [37] | C.-J. Lin and R. Saigal, An incomplete Cholesky factorization for dense symmetric positive definite matrices, BIT, 40 (2000), pp. 536–558. · Zbl 0960.65033 |
| [38] | B. R. Lowery and J. Langou, Stability Analysis of QR Factorization in an Oblique Inner Product, preprint, arXiv:1401.5171, 2014. |
| [39] | Y. Maday and O. Mula, A generalized empirical interpolation method : Application of reduced basis techniques to data assimilation, in Analysis and Numerics of Partial Differential Equations, Springer INdAM Ser., Springer, New York, 2013, pp. 221–235. · Zbl 1267.62013 |
| [40] | Y. Maday, O. Mula, A. T. Patera, and M. Yano, The generalized empirical interpolation method: Stability theory on Hilbert spaces with an application to the Stokes equation, Comput. Methods Appl. Mech. Engrg., 287 (2015), pp. 310–334. · Zbl 1423.76346 |
| [41] | Y. Maday, O. Mula, and G. Turinici, Convergence analysis of the generalized empirical interpolation method, SIAM J. Numer. Anal., 54 (2016), pp. 1713–1731, . · Zbl 1347.41044 |
| [42] | Y. Maday, N. C. Nguyen, A. T. Patera, and S. H. Pau, A general multipurpose interpolation procedure: The magic points, Commun. Pure Appl. Anal., 8 (2009), pp. 383–404, . · Zbl 1184.65020 |
| [43] | Y. Maday, A. T. Patera, J. D. Penn, and M. Yano, A parameterized-background data-weak approach to variational data assimilation: Formulation, analysis, and application to acoustics, Internat. J. Numer. Methods Engrg., 102 (2015), pp. 933–965, . · Zbl 1352.65529 |
| [44] | Y. Maday, A. T. Patera, J. D. Penn, and M. Yano, PBDW state estimation: Noisy observations; configuration-adaptive background spaces; physical interpretations, ESAIM Proc., 50 (2015), pp. 144–168, . · Zbl 1342.82116 |
| [45] | O. Mula, Some Contributions Towards the Parallel Simulation of Time Dependent Neutron Transport and the Integration of Observed Data in Real Time, Ph.D. thesis, Université Pierre et Marie Curie—Paris VI, 2014, . |
| [46] | F. Negri, A. Manzoni, and D. Amsallem, Efficient model reduction of parametrized systems by matrix discrete empirical interpolation, J. Comput. Phys., 303 (2015), pp. 431–454. · Zbl 1349.65154 |
| [47] | B. R. Noack, M. Schlegel, B. Ahlborn, G. Mutschke, M. Morzyński, P. Comte, and G. Tadmor, A finite-time thermodynamics of unsteady fluid flows, J. Non-Equil. Thermody., 33 (2008), pp. 103–148. · Zbl 1148.80302 |
| [48] | B. Peherstorfer, D. Butnaru, K. Willcox, and H.-J. Bungartz, Localized discrete empirical interpolation method, SIAM J. Sci. Comput., 36 (2014), pp. A168–A192. · Zbl 1290.65080 |
| [49] | B. Peherstorfer and K. Willcox, Online adaptive model reduction for nonlinear systems via low-rank updates, SIAM J. Sci. Comput., 37 (2015), pp. A2123–A2150, . · Zbl 1323.65102 |
| [50] | A. Quarteroni, A. Manzoni, and F. Negri, Reduced Basis Methods for Partial Differential Equations: An Introduction, Vol. 92, Springer, New York, 2015. · Zbl 1337.65113 |
| [51] | S. C. Reddy, P. J. Schmid, and D. S. Henningson, Pseudospectra of the Orr–Sommerfeld operator, SIAM J. Appl. Math., 53 (1993), pp. 15–47, . · Zbl 0778.34060 |
| [52] | C. W. Rowley, Model reduction for fluids, using balanced proper orthogonal decomposition, Internat. J. Bifur. Chaos Appl. Sci. Engrg., 15 (2005), pp. 997–1013. · Zbl 1140.76443 |
| [53] | C. W. Rowley, T. Colonius, and R. M. Murray, Model reduction for compressible flows using POD and Galerkin projection, Phys. D, 189 (2004), pp. 115–129. · Zbl 1098.76602 |
| [54] | G. Serre, P. Lafon, X. Gloerfelt, and C. Bailly, Reliable reduced-order models for time-dependent linearized Euler equations, J. Comput. Phys., 231 (2012), pp. 5176–5194. · Zbl 1248.35155 |
| [55] | G. W. Stewart, Computing the CS decomposition of a partitioned orthonormal matrix, Numer. Math., 40 (1982), pp. 297–306. · Zbl 0516.65016 |
| [56] | G. W. Stewart and J.-G. Sun, Matrix Perturbation Theory, Academic Press, New York, 1990. · Zbl 0706.65013 |
| [57] | D. B. Szyld, The many proofs of an identity on the norm of oblique projections, Numer. Algorithms, 42 (2006), pp. 309–323. · Zbl 1102.47002 |
| [58] | M. Tabandeh and M. Wei, On the symmetrization in POD-Galerkin model for linearized compressible flows, in Proceedings of the 54th AIAA Aerospace Sciences Meeting, 2016. |
| [59] | P. Tiso, R. Dedden, and D. Rixen, A modified discrete empirical interpolation method for reducing non-linear structural finite element models, in Proceedings of the International Design Engineering Technical Conferences & Computers and Information in Engineering Conference, ASME, 2013. |
| [60] | P. Tiso and D. J. Rixen, Discrete Empirical Interpolation Method for Finite Element Structural Dynamics, Springer, New York, 2013, pp. 203–212, . |
| [61] | A. van der Sluis, Condition numbers and equilibration of matrices, Numer. Math., 14 (1969), pp. 14–23. · Zbl 0182.48906 |
| [62] | C. F. Van Loan, Generalizing the singular value decomposition, SIAM J. Numer. Anal., 13 (1976), pp. 76–83. · Zbl 0338.65022 |
| [63] | S. Volkwein, Model reduction using proper orthogonal decomposition, in Proceedings of CMCS 2011, . · Zbl 1007.49019 |
| [64] | P. \AA. Wedin, Perturbation bounds in connection with singular value decomposition, BIT, 12 (1972), pp. 99–111, . · Zbl 0239.15015 |
| [65] | P. \AA. Wedin, On angles between subspaces of a finite dimensional inner product space, in Matrix Pencils, Lecture Notes in Math. 973, Springer, New York, 1982, pp. 263–285. · Zbl 0507.15002 |
| [66] | D. Wirtz, D. C. Sorensen, and B. Haasdonk, A posteriori error estimation for DEIM reduced nonlinear dynamical systems, SIAM J. Sci. Comput., 36 (2014), pp. A311–A338, . · Zbl 1312.65127 |
| [67] | P. Zhu and A. V. Knyazev, Angles between subspaces and their tangents, J. Numer. Math., 21 (2013), pp. 325–340. · Zbl 1286.65052 |
| [68] | R. Zimmermann, A locally parametrized reduced-order model for the linear frequency domain approach to time-accurate computational fluid dynamics, SIAM J. Sci. Comput., 36 (2014), pp. B508–B537, . · Zbl 1347.76032 |
| [69] | R. Zimmermann and S. Görtz, Non-linear reduced order models for steady aerodynamics, Procedia Comput. Sci., 1 (2010), pp. 165–174. |
| [70] | R. Zimmermann, B. Peherstorfer, and K. Willcox, Geometric Subspace Updates with Applications to Online Adaptive Nonlinear Model Reduction, ACDL report TR15-3, Massachusetts Institute of Technology, Cambridge, MA, 2015. · Zbl 1383.65034 |
| [71] | R. Zimmermann and K. Willcox, An accelerated greedy missing point estimation procedure, SIAM J. Sci. Comput., 38 (2016), pp. A2827–A2850, . · Zbl 1348.65045 |
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.
