Article Contents
Article Contents

Multilinear POD-DEIM model reduction for 2D and 3D semilinear systems of differential equations

The author is a member of Indam-GNCS, which support is gratefully acknowledged

• We are interested in the numerical solution of coupled semilinear partial differential equations (PDEs) in two and three dimensions. Under certain assumptions on the domain, we take advantage of the Kronecker structure arising in standard space discretizations of the differential operators and illustrate how the resulting system of ordinary differential equations (ODEs) can be treated directly in matrix or tensor form. Moreover, in the framework of the proper orthogonal decomposition (POD) and the discrete empirical interpolation method (DEIM) we derive a two- and three-sided model order reduction strategy that is applied directly to the ODE system in matrix and tensor form respectively. We discuss how to integrate the reduced order model and, in particular, how to solve the tensor-valued linear system arising at each timestep of a semi-implicit time discretization scheme. We illustrate the efficiency of the proposed method through a comparison to existing techniques on classical benchmark problems such as the two- and three-dimensional Burgers equation.

Mathematics Subject Classification: Primary: 37M99, 15A21, 15A24, 15A69 65N06.

 Citation:

• Figure 1.  Example 1: Average relative error 28 (left) and online computational time (right) of the reduced order model and the full order model for different values of $\tau$

Figure 2.  Example 2: $u_1(x,y,0.5)$ discretized with $n = 200$. The exact solution (left), the $\mathsf{ho-pod-deim}$ approximation (middle), and the relative error mesh between the two (right)

Figure 3.  Example 2: $u_2(x,y,0.5)$ discretized with $n = 200$. The exact solution (left), the $\mathsf{ho-pod-deim}$ approximation (middle), and the relative error mesh between the two (right)

Figure 4.  Example 2: The average relative error through $n_{\mathfrak t} = 2n$ timesteps between the $\mathsf{ho-pod-deim}$ approximation $\widetilde{\bf U}_1(t)$ ($\widetilde{\bf U}_2(t)$) and the exact solution $u_1(x,y,t)$ ($u_2(x,y,t)$)

Figure 5.  Example 2: A comparison of the time required offline for basis construction (left) and online for integration (right) between $\mathsf{ho-pod-deim}$ and $\mathsf{pod-deim}$ [53] for increasing $n$

Figure 6.  Example 3: A comparison of the offline time for increasing dimension $n$, between $\mathsf{ho-pod}$ and $\mathsf{pod}$ (left) and $\mathsf{ho-deim}$ and $\mathsf{deim}$ (right)

Figure 7.  Example 3: A comparison of the time to solve all linear systems of the form 25, for different values of $\tau$, between $\mathsf{t3-sylv}$ and Vec-lin. The $x-$axis displays the maximum dimension of the three vectorized equations for different values of $\tau$

Table 1.  Example 1. Dim. of ${\textsf{ho-pod}}$ and ${\textsf{ho-deim}}$ bases obtained for different $\tau$. The full order model has dimension $n = 1200$

 $\tau$ ${\bf U}_i$ left dim. $\mathsf{ho-pod}$ right dim. $\mathsf{ho-pod}$ left dim. $\mathsf{ho-deim}$ right dim. $\mathsf{ho-deim}$ $10^{-2}$ ${\mathbf{U}}_1$ 7 7 11 11 ${\mathbf{U}}_2$ 9 10 - - $10^{-4}$ ${\mathbf{U}}_1$ 18 20 23 23 ${\mathbf{U}}_2$ 19 20 - - $10^{-6}$ ${\mathbf{U}}_1$ 31 33 32 34 ${\mathbf{U}}_2$ 29 31 - - $10^{-8}$ ${\mathbf{U}}_1$ 43 46 44 47 ${\mathbf{U}}_2$ 37 40 - -

Table 2.  A breakdown of the $\mathsf{(ho)-pod}$ and $\mathsf{(ho)-deim}$ basis dimensions and the memory requirements for four different state space dimensions. Note that $\tau = 1/n^2$

 $n$ $\mathsf{algorithm}$ ${\bf U}_i$ $\mathsf{pod dim.}$ $\mathsf{deim dim.}$ ${\textsf{offline}}$$\mathsf{memory} \mathsf{online}$$\mathsf{memory}$ $60$ $\mathsf{ho-pod-deim}$ ${\bf U}_1$ 9/9 18/18 $98 n$ $54n$ ${\bf U}_2$ 9/9 18/18 $98n$ $54n$ $\mathsf{pod-deim}$ [53] ${\bf U}_1$ 5 14 $400n^2$ $19n^2$ ${\bf U}_2$ 4 14 $400n^2$ $18n^2$ $200$ $\mathsf{ho-pod-deim}$ ${\bf U}_1$ 13/13 24/25 $153n$ $75n$ ${\bf U}_2$ 12/12 24/25 $153n$ $73n$ $\mathsf{pod-deim}$ [53] ${\bf U}_1$ 9 23 $400n^2$ $32n^2$ ${\bf U}_2$ 8 23 $400n^2$ $31n^2$ $600$ $\mathsf{ho-pod-deim}$ ${\bf U}_1$ 16/17 32/32 $196n$ $97n$ ${\bf U}_2$ 16/16 32/32 $194n$ $96n$ $\mathsf{pod-deim}$ [53] ${\bf U}_1$ 15 28 $400 n^2$ $43n^2$ ${\bf U}_2$ 14 28 $400n^2$ $42n^2$ $1200$ $\mathsf{ho-pod-deim}$ ${\bf U}_1$ 19/19 36/39 $219n$ $113n$ ${\bf U}_2$ 19/19 36/39 $215n$ $113 n$ $\mathsf{pod-deim}$ [53] ${\bf U}_1$ 19 31 $400n^2$ $50 n^2$ ${\bf U}_2$ 18 31 $400 n^2$ $50 n^2$

Table 3.  Example 3. Dim. of $\mathsf{ho-pod}$ and $\mathsf{ho-deim}$ bases and the average error at 300 timesteps for increasing $r$. The full order model has dimension $n = 150$ and $\tau = 10^{-4}$

 $r$ $u$ $k_1$ $k_2$ $k_3$ $p_1$ $p_2$ $p_3$ $\mathsf{error} \bar{\mathcal{E}}(\pmb{\mathcal{ U}})$ $10$ $u_1$ 4 7 10 7 12 16 $1\cdot 10^{-4}$ $u_2$ 7 7 7 9 12 13 $6\cdot 10^{-5}$ $u_3$ 8 12 8 9 16 13 $1\cdot 10^{-4}$ $100$ $u_1$ 6 11 15 10 17 20 $3\cdot 10^{-5}$ $u_2$ 10 11 11 12 17 17 $4\cdot 10^{-5}$ $u_3$ 10 16 12 12 21 17 $4\cdot 10^{-5}$ $500$ $u_1$ 9 15 19 13 23 26 $2\cdot 10^{-5}$ $u_2$ 11 16 17 14 23 23 $3\cdot 10^{-5}$ $u_3$ 12 19 16 14 25 23 $4\cdot 10^{-5}$

Table 4.  Example 3. Memory and CPU time required for basis construction and integration. The full order model has dimension $n = 150$ and $\tau = 10^{-4}$

 r Online memory Basis time(s) FOM time(s) ROM time(s) 10 $177n$ 20 1641 1.9 100 $245n$ 20 1641 2.2 500 $318n$ 20 1641 3.3

Table 5.  Example 4. Dim. of ${\mathsf{ho-pod}}$ and ${\mathsf{ho-deim }}$ bases and further computational detalis for $\tau = 10^{-2}$ and $n = 150$

 $r_0$ ${\bf U}_i$ $\mathsf{pod dim.}$ ($k_1/k_2/k_3$) $\mathsf{deim dim.}$ ($p_1/p_2/p_3$) $\mathsf{online}$ $\mathsf{memory}$ $\mathsf{online}$ $\mathsf{time (s)}$ $\mathsf{error}$ $0.1$ ${\mathbf{U}}_1$ 2/2/2 5/5/5 $21n$ 1.29 $3\cdot10^{-4}$ ${\mathbf{U}}_2$ 2/2/2 3/3/3 $15n$ 1.20 $4\cdot10^{-4}$ ${\mathbf{U}}_3$ 18/18/18 - $54n$ 1.50 $3\cdot10^{-4}$ ${\mathbf{U}}_4$ 9/9/9 - $27n$ 0.63 $1\cdot10^{-2}$ $0.3$ ${\mathbf{U}}_1$ 8/8/8 9/9/9 $51n$ 1.56 $3\cdot10^{-4}$ ${\mathbf{U}}_2$ 8/8/8 9/9/9 $51n$ 1.13 $3\cdot10^{-4}$ ${\mathbf{U}}_3$ 43/43/42 - $128n$ 11.25 $3\cdot10^{-3}$ ${\mathbf{U}}_4$ 31/31/30 - $92n$ 4.27 $5\cdot10^{-3}$
•  [1] A. Antoulas, C. Beattie and S. Gugercin, Interpolatory Methods for Model Reduction, SIAM, Philidelphia, 2020. doi: 10.1137/1.9781611976083. [2] U. M. Ascher, S. J. Ruuth and B. T. Wetton, Implicit-explicit methods for time-dependent partial differential equations, SIAM J. Numer. Anal., 32 (1995), 797-823.  doi: 10.1137/0732037. [3] P. Astrid, S. Weiland, K. Willcox and T. Backx, Missing point estimation in models described by proper orthogonal decomposition, IEEE Trans. Autom. Control, 53 (2008), 2237-2251.  doi: 10.1109/TAC.2008.2006102. [4] M. Barrault, Y. Maday, N. C. Nguyen and A. T. Patera, An 'empirical interpolation' method: Application to efficient reduced-basis discretization of partial differential equations, C. R. Math. Acad. Sci. Paris, 339 (2004), 667-672.  doi: 10.1016/j.crma.2004.08.006. [5] P. Benner, V. Mehrmann and D. Sorensen, Dimension Reduction of Large-scale Systems, Lecture Notes in Computational Science and Engineering, 45. Springer, Berlin, 2005. doi: 10.1007/3-540-27909-1. [6] P. Benner, S. Gugercin and K. Willcox, A survey of projection-based model reduction methods for parametric dynamical systems, SIAM Rev., 57 (2015), 483-531.  doi: 10.1137/130932715. [7] D. Bonomi, A. Manzoni and A. Quarteroni, A matrix DEIM technique for model reduction of nonlinear parametrized problems in cardiac mechanics, Comput. Methods Appl. Mech. Eng., 324 (2017), 300-326.  doi: 10.1016/j.cma.2017.06.011. [8] S. Chaturantabut and D. C. Sorensen, Nonlinear model reduction via discrete empirical interpolation, SIAM J. Sci. Comput., 32 (2010), 2737-2764.  doi: 10.1137/090766498. [9] S. Chaturantabut and D. C. Sorensen, Application of POD and DEIM on dimension reduction of non-linear miscible viscous fingering in porous media, Math. Comput. Modell. Dyn. Syst., 17 (2011), 337-353.  doi: 10.1080/13873954.2011.547660. [10] M. Daub, Mathematical Modeling and Numerical Simulations of the Extrinsic Pro-Apoptotic Signaling Pathway, PhD thesis, University of Stuttgart, 2013. [11] M. Daub, S. Waldherr, F. Allgöwer, P. Scheurich and G. Schneider, Death wins against life in a spatially extended apoptosis model, Biosystems, 108 (2012), 45-51. [12] M. C. D'Autilia, I. Sgura and V. Simoncini, Matrix-oriented discretization methods for reaction–diffusion PDEs: Comparisons and applications, Comput. Math. Appl., 79 (2020), 2067-2085.  doi: 10.1016/j.camwa.2019.10.020. [13] A. De Wit, Spatial patterns and spatiotemporal dynamics in chemical systems, Advances in Chemical Physics, 109 (1999), 435-513.  doi: 10.1002/9780470141687.ch5. [14] 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), A631-A648.  doi: 10.1137/15M1019271. [15] C. A. Fletcher, Generating exact solutions of the two-dimensional Burgers' equations, Int. J. Numer. Methods Fluids, 3 (1983), 213-216. [16] G. Gambino, M. Lombardo and M. Sammartino, Pattern selection in the 2D FitzHugh–Nagumo model, Ric. Mat., 68 (2019), 535-549.  doi: 10.1007/s11587-018-0424-6. [17] Q. Gao and M. Zou, An analytical solution for two and three dimensional nonlinear Burgers' equation, Appl. Math. Modell., 45 (2017), 255-270.  doi: 10.1016/j.apm.2016.12.018. [18] U. Z. George, A. Stéphanou and A. Madzvamuse, Mathematical modelling and numerical simulations of actin dynamics in the eukaryotic cell, J. Math. Biol., 66 (2013), 547-593.  doi: 10.1007/s00285-012-0521-1. [19] G. H. Golub and  C. F. van Loan,  Matrix Computations, 4$^{th}$ edition, Johns Hopkins University Press, Baltimore, 2013. [20] C. Gu, QLMOR: A projection-based nonlinear model order reduction approach using quadratic-linear representation of nonlinear systems, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 30 (2011), 1307-1320. [21] N. Halko, P.-G. Martinsson and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53 (2011), 217-288.  doi: 10.1137/090771806. [22] M. Hinze and S. Volkwein, Proper orthogonal decomposition surrogate models for nonlinear dynamical systems: Error estimates and suboptimal control, Dimension Reduction of Large-Scale Systems, 45 (2005), 261-306.  doi: 10.1007/3-540-27909-1_10. [23] A. L. Hodgkin and A. F. Huxley, A quantitative description of membrane current and its application to conduction and excitation in nerve, The Journal of physiology, 117 (1952), 500-544. [24] W. Hundsdorfer and J. G. Verwer, Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations, Springer Series in Computational Mathematics, 33. Springer-Verlag, Berlin, 2003. doi: 10.1007/978-3-662-09017-6. [25] B. Karasözen, M. Uzunca and T. Küçükseyhan, Model order reduction for pattern formation in Fitzhugh-Nagumo equations, Numerical Mathematics and Advanced Applications ENUMATH 2015, 112 (2016), 23-31.  doi: 10.1007/978-3-319-39929-4_3. [26] B. Karasözen, M. Uzunca and T. Küçükseyhan, Reduced order optimal control of the convective Fitzhugh–Nagumo equations, Comput. Math. Appl., 79 (2020), 982-995.  doi: 10.1016/j.camwa.2019.08.009. [27] B. Karasözen, S. Yıldız and M. Uzunca, Structure preserving model order reduction of shallow water equations, Math. Methods Appl. Sci., 44 (2021), 476-492.  doi: 10.1002/mma.6751. [28] G. Kirsten and V. Simoncini, A matrix-oriented POD-DEIM algorithm applied to nonlinear differential matrix equations, preprint, arXiv: 2006.13289. [29] T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM Rev., 51 (2009), 455-500.  doi: 10.1137/07070111X. [30] B. Kramer, Model Reduction of the Coupled Burgers Equation in Conservation Form, PhD thesis, Virginia Tech, 2011. [31] B. Kramer and K. E. Willcox, Nonlinear model order reduction via lifting transformations and proper orthogonal decomposition, AIAA Journal, 57 (2019), 2297-2307.  doi: 10.2514/1.J057791. [32] K. Kunisch and S. Volkwein, Control of the Burgers equation by a reduced-order approach using proper orthogonal decomposition, J. Optim. Theory Appl., 102 (1999), 345-371.  doi: 10.1023/A:1021732508059. [33] P. K. Maini and H. G. Othmer, Mathematical Models for Biological Pattern Formation, The IMA Volumes in Mathematics and its Applications - Frontiers in application of Mathematics, Springer-Verlag, New York, 2001. [34] H. Malchow, S. Petrovskii and E. Venturino, Spatiotemporal Patterns in Ecology and Epidemiology: Theory, Models, and Simulations, Chapman & Hall, CRC, Boca Raton, FL, 2008. [35] The MathWorks, MATLAB 7, r2013b edition, 2013. [36] R. Minster, A. K. Saibaba and M. E. Kilmer, Randomized algorithms for low-rank tensor decompositions in the Tucker format, SIAM J. Math. Data Sci., 2 (2020), 189-215.  doi: 10.1137/19M1261043. [37] J. Murray, Mathematical Biology II: Spatial Models and Biomedical Applications, 3$^{rd}$ edition, Interdisciplinary Applied Mathematics, 18. Springer-Verlag, New York, 2003. [38] F. Negri, A. Manzoni and D. Amsallem, Efficient model reduction of parametrized systems by matrix discrete empirical interpolation, J. Comput. Phys., 303 (2015), 431-454.  doi: 10.1016/j.jcp.2015.09.046. [39] N.-C. Nguyen, A. T. Patera and J. Peraire, A 'best points' interpolation method for efficient approximation of parametrized functions, Internat. J. Numer. Methods Engrg., 73 (2008), 521-543.  doi: 10.1002/nme.2086. [40] D. Palitta and V. Simoncini, Matrix-equation-based strategies for convection–diffusion equations, BIT, 56 (2016), 751-776.  doi: 10.1007/s10543-015-0575-8. [41] A. T. Patera and G. Rozza, Reduced Basis Approximation and A posteriori Error Estimation for Parametrized Partial Differential Equations, MIT Cambridge, MA, USA, 2007. [42] A. Quarteroni, Numerical Models for Differential Problems, vol. 8 of MS & A - Modeling, Simulation and Applications, Springer-Verlag, Milan, 2014. doi: 10.1007/978-88-470-5522-3. [43] S. J. Ruuth, Implicit-explicit methods for reaction-diffusion problems in pattern formation, J. Math. Biol., 34 (1995), 148-176.  doi: 10.1007/BF00178771. [44] S. Sahyoun and S. M. Djouadi, Nonlinear model reduction using space vectors clustering POD with application to the Burgers' equation, 2014 American Control Conference, IEEE, (2014), 1661–1666. doi: 10.1109/ACC.2014.6859104. [45] J. A. Sherratt and M. A. Chaplain, A new mathematical model for avascular tumour growth, J. Math. Biol., 43 (2001), 291-312.  doi: 10.1007/s002850100088. [46] V. Simoncini, Numerical solution of a class of third order tensor linear equations, BUMI, 13 (2020), 429-439.  doi: 10.1007/s40574-020-00247-4. [47] V. Simoncini, Computational methods for linear matrix equations, SIAM Rev., 58 (2016), 377-441.  doi: 10.1137/130912839. [48] R. Ştefănescu, A. Sandu and I. M. Navon, Comparison of POD reduced order strategies for the nonlinear 2D shallow water equations, Internat. J. Numer. Methods Fluids, 76 (2014), 497-521.  doi: 10.1002/fld.3946. [49] J. C. Strikwerda, Finite Difference Schemes and Partial Differential Equations, SIAM, 2004. doi: 10.1137/1.9780898717938. [50] A. Tveito, H. P. Langtangen, B. F. Nielsen and X. Cai, Elements of Scientific Computing, Texts in Computational Science and Engineering, Springer-Verlag, Berlin, 2010. doi: 10.1007/978-3-642-11299-7. [51] V. K. Vanag, Waves and patterns in reaction–diffusion systems. Belousov–Zhabotinsky reaction in water-in-oil microemulsions, Phys. Usp., 47 (2004), 923. [52] N. Vannieuwenhoven, R. Vandebril and K. Meerbergen, A new truncation strategy for the higher-order singular value decomposition, SIAM J. Sci. Comput., 34 (2012), A1027-A1052.  doi: 10.1137/110836067. [53] Y. Wang, I. M. Navon, X. Wang and Y. Cheng, 2D Burgers equation with large Reynolds number using POD/DEIM and calibration, Internat. J. Numer. Methods Fluids, 82 (2016), 909-931.  doi: 10.1002/fld.4249.

Figures(7)

Tables(5)