Train small, model big: scalable physics simulators via reduced order modeling and domain decomposition. (English) Zbl 07867432
Summary: Numerous cutting-edge scientific technologies originate at the laboratory scale, but transitioning them to practical industry applications is a formidable challenge. Traditional pilot projects at intermediate scales are costly and time-consuming. An alternative, the pilot-scale model, relies on high-fidelity numerical simulations, but even these simulations can be computationally prohibitive at larger scales. To overcome these limitations, we propose a scalable, physics-constrained reduced order model (ROM) method. The ROM identifies critical physics modes from small-scale unit components, projecting governing equations onto these modes to create a reduced model that retains essential physics details. We also employ Discontinuous Galerkin Domain Decomposition (DG-DD) to apply ROM to unit components and interfaces, enabling the construction of large-scale global systems without data at such large scales. This method is demonstrated on the Poisson and Stokes flow equations, showing that it can solve equations about 15-40 times faster with only \(\sim 1\)% relative error. Furthermore, ROM takes one order of magnitude less memory than the full order model, enabling larger scale predictions at a given memory limitation.
Keywords:
reduced order model; E-pilot; domain decomposition; Stokes flow; Poisson equation; scalable physics simulatorReferences:
| [1] | Gross, R.; Hanna, R.; Gambhir, A.; Heptonstall, P.; Speirs, J., How long does innovation and commercialisation in the energy sectors take? Historical case studies of the timescale from invention to widespread commercialisation in energy supply and end use technology, Energy Policy, 123, 682-699, 2018, URL https://www.sciencedirect.com/science/article/pii/S0301421518305901 |
| [2] | Chaouki, J.; Sotudeh-Gharebagh, R., Scale-Up Processes: Iterative Methods for the Chemical, Mineral and Biological Industries, 2021, Walter de Gruyter GmbH & Co KG |
| [3] | Toselli, A., hp discontinuous Galerkin approximations for the Stokes problem, Math. Models Methods Appl. Sci., 12, 11, 1565-1597, 2002 · Zbl 1041.76045 |
| [4] | Cockburn, B.; Kanschat, G.; Schötzau, D.; Schwab, C., Local discontinuous Galerkin methods for the Stokes system, SIAM J. Numer. Anal., 40, 1, 319-343, 2002 · Zbl 1032.65127 |
| [5] | Wagner, G. J.; Moës, N.; Liu, W. K.; Belytschko, T., The extended finite element method for rigid particles in Stokes flow, Internat. J. Numer. Methods Engrg., 51, 3, 293-313, 2001 · Zbl 0998.76054 |
| [6] | Pozrikidis, C., Boundary Integral and Singularity Methods for Linearized Viscous Flow, 1992, Cambridge University Press · Zbl 0772.76005 |
| [7] | Singh, R. K.; Fu, Y.; Zeng, C.; Roy, P.; Bao, J.; Xu, Z.; Panagakos, G., Hydrodynamics of countercurrent flow in an additive-manufactured column with triply periodic minimal surfaces for carbon dioxide capture, Chem. Eng. J., 450, Article 138124 pp., 2022 |
| [8] | TIC - Petra Nova carbon capture project, URL https://ticus.com/markets/power/coal-retrofit/petra-nova-carbon-capture-project/. |
| [9] | Brunton, S. L.; Proctor, J. L.; Kutz, J. N., Discovering governing equations from data by sparse identification of nonlinear dynamical systems, Proc. Natl. Acad. Sci., 113, 15, 3932-3937, 2016 · Zbl 1355.94013 |
| [10] | Raissi, M.; Perdikaris, P.; Karniadakis, G. E., Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations, J. Comput. Phys., 378, 686-707, 2019 · Zbl 1415.68175 |
| [11] | Li, Z.; Kovachki, N.; Azizzadenesheli, K.; Liu, B.; Bhattacharya, K.; Stuart, A.; Anandkumar, A., Fourier neural operator for parametric partial differential equations, 2020, arXiv preprint arXiv:2010.08895 |
| [12] | Wang, H.; Planas, R.; Chandramowlishwaran, A.; Bostanabad, R., Mosaic flows: A transferable deep learning framework for solving pdes on unseen domains, Comput. Methods Appl. Mech. Engrg., 389, Article 114424 pp., 2022 · Zbl 1507.65215 |
| [13] | Rowley, C. W.; Dawson, S. T., Model reduction for flow analysis and control, Annu. Rev. Fluid Mech., 49, 387-417, 2017 · Zbl 1359.76111 |
| [14] | Taira, K.; Brunton, S. L.; Dawson, S. T.; Rowley, C. W.; Colonius, T.; McKeon, B. J.; Schmidt, O. T.; Gordeyev, S.; Theofilis, V.; Ukeiley, L. S., Modal analysis of fluid flows: An overview, Aiaa J., 55, 12, 4013-4041, 2017 |
| [15] | Choi, Y.; Carlberg, K., Space-time least-squares Petrov-Galerkin projection for nonlinear model reduction, SIAM J. Sci. Comput., 41, 1, A26-A58, 2019 · Zbl 1405.65140 |
| [16] | Choi, Y.; Brown, P.; Arrighi, W.; Anderson, R.; Huynh, K., Space-time reduced order model for large-scale linear dynamical systems with application to Boltzmann transport problems, J. Comput. Phys., 424, Article 109845 pp., 2021 · Zbl 07508450 |
| [17] | Choi, Y.; Boncoraglio, G.; Anderson, S.; Amsallem, D.; Farhat, C., Gradient-based constrained optimization using a database of linear reduced-order models, J. Comput. Phys., 423, Article 109787 pp., 2020 · Zbl 07508406 |
| [18] | Copeland, D. M.; Cheung, S. W.; Huynh, K.; Choi, Y., Reduced order models for Lagrangian hydrodynamics, Comput. Methods Appl. Mech. Engrg., 388, Article 114259 pp., 2022 · Zbl 1507.76179 |
| [19] | Cheung, S. W.; Choi, Y.; Copeland, D. M.; Huynh, K., Local Lagrangian reduced-order modeling for the Rayleigh-Taylor instability by solution manifold decomposition, J. Comput. Phys., 472, Article 111655 pp., 2023 · Zbl 07620355 |
| [20] | Kim, Y.; Choi, Y.; Widemann, D.; Zohdi, T., A fast and accurate physics-informed neural network reduced order model with shallow masked autoencoder, J. Comput. Phys., 451, Article 110841 pp., 2022 · Zbl 07517153 |
| [21] | Carlberg, K.; Choi, Y.; Sargsyan, S., Conservative model reduction for finite-volume models, J. Comput. Phys., 371, 280-314, 2018 · Zbl 1415.65208 |
| [22] | Kim, Y.; Wang, K.; Choi, Y., Efficient space-time reduced order model for linear dynamical systems in python using less than 120 lines of code, Mathematics, 9, 14, 1690, 2021 |
| [23] | McBane, S.; Choi, Y., Component-wise reduced order model lattice-type structure design, Comput. Methods Appl. Mech. Engrg., 381, Article 113813 pp., 2021 · Zbl 1506.74290 |
| [24] | McBane, S.; Choi, Y.; Willcox, K., Stress-constrained topology optimization of lattice-like structures using component-wise reduced order models, Comput. Methods Appl. Mech. Engrg., 400, Article 115525 pp., 2022 · Zbl 1507.74323 |
| [25] | Eftang, J. L.; Patera, A. T., A port-reduced static condensation reduced basis element method for large component-synthesized structures: Approximation and a posteriori error estimation, Adv. Model. Simul. Eng. Sci., 1, 1, 1-49, 2014 |
| [26] | Maday, Y.; Ronquist, E. M., The reduced basis element method: Application to a thermal fin problem, SIAM J. Sci. Comput., 26, 1, 240-258, 2004 · Zbl 1077.65120 |
| [27] | Huynh, D. B.P.; Knezevic, D. J.; Patera, A. T., A static condensation reduced basis element method: Approximation and a posteriori error estimation, ESAIM Math. Model. Numer. Anal., 47, 1, 213-251, 2013 · Zbl 1276.65082 |
| [28] | Smetana, K., A new certification framework for the port reduced static condensation reduced basis element method, Comput. Methods Appl. Mech. Engrg., 283, 352-383, 2015 · Zbl 1425.65179 |
| [29] | Vallaghé, S.; Patera, A. T., The static condensation reduced basis element method for a mixed-mean conjugate heat exchanger model, SIAM J. Sci. Comput., 36, 3, B294-B320, 2014 · Zbl 1298.80016 |
| [30] | Huynh, D. B.P.; Knezevic, D. J.; Patera, A. T., A static condensation reduced basis element method: Complex problems, Comput. Methods Appl. Mech. Engrg., 259, 197-216, 2013 · Zbl 1286.65160 |
| [31] | Iapichino, L.; Quarteroni, A.; Rozza, G., Reduced basis method and domain decomposition for elliptic problems in networks and complex parametrized geometries, Comput. Math. Appl., 71, 1, 408-430, 2016 · Zbl 1443.65340 |
| [32] | Wicke, M.; Stanton, M.; Treuille, A., Modular bases for fluid dynamics, ACM Trans. Graph., 28, 3, 1-8, 2009 |
| [33] | Hoang, C.; Choi, Y.; Carlberg, K., Domain-decomposition least-squares Petrov-Galerkin (DD-LSPG) nonlinear model reduction, Comput. Methods Appl. Mech. Engrg., 384, Article 113997 pp., 2021 · Zbl 1507.65242 |
| [34] | Diaz, A. N.; Choi, Y.; Heinkenschloss, M., A fast and accurate domain-decomposition nonlinear manifold reduced order model, Comput. Methods Appl. Mech. Engrg., 425, Article 116943 pp., 2024 · Zbl 1539.65189 |
| [35] | Smetana, K.; Taddei, T., Localized model reduction for nonlinear elliptic partial differential equations: Localized training, partition of unity, and adaptive enrichment, SIAM J. Sci. Comput., 45, 3, A1300-A1331, 2023 · Zbl 1517.65117 |
| [36] | Hansbo, P., Nitsche’s method for interface problems in computational mechanics, GAMM-Mitt., 28, 2, 183-206, 2005 · Zbl 1179.65147 |
| [37] | Antonietti, P. F.; Pacciarini, P.; Quarteroni, A., A discontinuous Galerkin reduced basis element method for elliptic problems, ESAIM: Math. Model. Numer. Anal.-Modél. Math. Anal. Numér., 50, 2, 337-360, 2016 · Zbl 1343.65132 |
| [38] | Pacciarini, P.; Gervasio, P.; Quarteroni, A., Spectral based discontinuous Galerkin reduced basis element method for parametrized Stokes problems, Comput. Math. Appl., 72, 8, 1977-1987, 2016 · Zbl 1365.76125 |
| [39] | Yano, M., Discontinuous Galerkin reduced basis empirical quadrature procedure for model reduction of parametrized nonlinear conservation laws, Adv. Comput. Math., 45, 2287-2320, 2019 · Zbl 1435.65213 |
| [40] | Lassila, T.; Manzoni, A.; Quarteroni, A.; Rozza, G., Model order reduction in fluid dynamics: challenges and perspectives, (Reduced Order Methods for Modeling and Computational Reduction, 2014, Springer), 235-273 · Zbl 1395.76058 |
| [41] | Willcox, K., Unsteady flow sensing and estimation via the gappy proper orthogonal decomposition, Comput. & Fluids, 35, 2, 208-226, 2006 · Zbl 1160.76394 |
| [42] | Chaturantabut, S.; Sorensen, D. C., Nonlinear model reduction via discrete empirical interpolation, SIAM J. Sci. Comput., 32, 5, 2737-2764, 2010 · Zbl 1217.65169 |
| [43] | Yano, M.; Patera, A. T., An LP empirical quadrature procedure for reduced basis treatment of parametrized nonlinear PDEs, Comput. Methods Appl. Mech. Engrg., 344, 1104-1123, 2019 · Zbl 1440.65238 |
| [44] | Lauzon, J. T.; Cheung, S. W.; Shin, Y.; Choi, Y.; Copeland, D. M.; Huynh, K., S-OPT: A points selection algorithm for hyper-reduction in reduced order models, 2022, arXiv preprint arXiv:2203.16494 |
| [45] | Arnold, D. N., An interior penalty finite element method with discontinuous elements, SIAM J. Numer. Anal., 19, 4, 742-760, 1982 · Zbl 0482.65060 |
| [46] | Farhat, C.; Roux, F.-X., A method of finite element tearing and interconnecting and its parallel solution algorithm, Int. J. Numer. Methods Eng., 32, 6, 1205-1227, 1991 · Zbl 0758.65075 |
| [47] | Farhat, C.; Chen, P.-S.; Mandel, J., A scalable Lagrange multiplier based domain decomposition method for time-dependent problems, Internat. J. Numer. Methods Engrg., 38, 22, 3831-3853, 1995 · Zbl 0844.73077 |
| [48] | Hesthaven, J. S.; Warburton, T., Nodal Discontinuous Galerkin Methods: Algorithms, Analysis, and Applications, 2007, Springer Science & Business Media |
| [49] | Cockburn, B.; Karniadakis, G. E.; Shu, C.-W., Discontinuous Galerkin Methods: Theory, Computation and Applications, 2012, Springer Science & Business Media |
| [50] | Rivière, B., Discontinuous Galerkin methods for solving elliptic and parabolic equations: theory and implementation, 2008, SIAM · Zbl 1153.65112 |
| [51] | Rivière, B.; Wheeler, M. F.; Girault, V., A priori error estimates for finite element methods based on discontinuous approximation spaces for elliptic problems, SIAM J. Numer. Anal., 39, 3, 902-931, 2001 · Zbl 1010.65045 |
| [52] | Hansbo, P.; Larson, M. G., Discontinuous Galerkin and the Crouzeix-Raviart element: Application to elasticity, ESAIM Math. Model. Numer. Anal., 37, 1, 63-72, 2003 · Zbl 1137.65431 |
| [53] | Dawson, C.; Sun, S.; Wheeler, M. F., Compatible algorithms for coupled flow and transport, Comput. Methods Appl. Mech. Engrg., 193, 23-26, 2565-2580, 2004 · Zbl 1067.76565 |
| [54] | Grote, M. J.; Schneebeli, A.; Schötzau, D., Discontinuous Galerkin finite element method for the wave equation, SIAM J. Numer. Anal., 44, 6, 2408-2431, 2006 · Zbl 1129.65065 |
| [55] | Nguyen, N. C.; Peraire, J.; Cockburn, B., An implicit high-order hybridizable discontinuous Galerkin method for the incompressible Navier-Stokes equations, J. Comput. Phys., 230, 4, 1147-1170, 2011 · Zbl 1391.76353 |
| [56] | Hartmann, R.; Houston, P., Adaptive discontinuous Galerkin finite element methods for the compressible Euler equations, J. Comput. Phys., 183, 2, 508-532, 2002 · Zbl 1057.76033 |
| [57] | Lv, Y.; Ihme, M., Discontinuous Galerkin method for multicomponent chemically reacting flows and combustion, J. Comput. Phys., 270, 105-137, 2014 · Zbl 1349.76239 |
| [58] | Noels, L.; Radovitzky, R., A general discontinuous Galerkin method for finite hyperelasticity. Formulation and numerical applications, Internat. J. Numer. Methods Engrg., 68, 1, 64-97, 2006 · Zbl 1145.74039 |
| [59] | Heath, R. E.; Gamba, I. M.; Morrison, P. J.; Michler, C., A discontinuous Galerkin method for the Vlasov-Poisson system, J. Comput. Phys., 231, 4, 1140-1174, 2012 · Zbl 1244.82081 |
| [60] | Haikal, G.; Hjelmstad, K., An enriched discontinuous Galerkin formulation for the coupling of non-conforming meshes, Finite Elem. Anal. Des., 46, 6, 496-503, 2010 |
| [61] | Laughton, E.; Tabor, G.; Moxey, D., A comparison of interpolation techniques for non-conformal high-order discontinuous Galerkin methods, Comput. Methods Appl. Mech. Engrg., 381, Article 113820 pp., 2021 · Zbl 1506.65170 |
| [62] | Chatterjee, A., An introduction to the proper orthogonal decomposition, Curr. Sci., 808-817, 2000 |
| [63] | Liang, Y.; Lee, H.; Lim, S.; Lin, W.; Lee, K.; Wu, C., Proper orthogonal decomposition and its applications—Part I: Theory, J. Sound Vib., 252, 3, 527-544, 2002 · Zbl 1237.65040 |
| [64] | Babuška, I., Error-bounds for finite element method, Numer. Math., 16, 4, 322-333, 1971 · Zbl 0214.42001 |
| [65] | Brezzi, F., On the existence, uniqueness and approximation of saddle-point problems arising from Lagrangian multipliers, Publ. Sém. Math. Inform. Rennes, S4, 1-26, 1974 |
| [66] | Ladyzhenskaya, O., The Mathematical Theory of Incompressible Viscous Flows, 1963, Gordon and Breach, New York · Zbl 0121.42701 |
| [67] | Taylor, C.; Hood, P., A numerical solution of the Navier-Stokes equations using the finite element technique, Comput. & Fluids, 1, 1, 73-100, 1973 · Zbl 0328.76020 |
| [68] | Anderson, R.; Andrej, J.; Barker, A.; Bramwell, J.; Camier, J.-S.; Cerveny, J.; Dobrev, V.; Dudouit, Y.; Fisher, A.; Kolev, T.; Pazner, W.; Stowell, M.; Tomov, V.; Akkerman, I.; Dahm, J.; Medina, D.; Zampini, S., MFEM: A modular finite element methods library, Comput. Math. Appl., 81, 42-74, 2021 · Zbl 1524.65001 |
| [69] | Choi, Y.; Arrighi, W. J.; Copeland, D. M.; Anderson, R. W.; Oxberry, G. M., Librom, 2019, [Computer Software] |
| [70] | Livermore computing – quartz, URL https://hpc.llnl.gov/hardware/compute-platforms/quartz. |
| [71] | Amestoy, P. R.; Duff, I. S.; L’Excellent, J.-Y.; Koster, J., A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl., 23, 1, 15-41, 2001 · Zbl 0992.65018 |
| [72] | Amestoy, P. R.; Buttari, A.; L’excellent, J.-Y.; Mary, T., Performance and scalability of the block low-rank multifrontal factorization on multicore architectures, ACM Trans. Math. Softw., 45, 1, 1-26, 2019 · Zbl 1471.65025 |
| [73] | Trottenberg, U.; Oosterlee, C. W.; Schuller, A., Multigrid, 2000, Elsevier |
| [74] | Stüben, K., A review of algebraic multigrid, (Numerical Analysis: Historical Developments in the 20th Century, 2001, Elsevier), 331-359 |
| [75] | Kay, D.; Loghin, D.; Wathen, A., A preconditioner for the steady-state Navier-Stokes equations, SIAM J. Sci. Comput., 24, 1, 237-256, 2002 · Zbl 1013.65039 |
| [76] | Elman, H. C.; Silvester, D. J.; Wathen, A. J., Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, 2014, Oxford University Press · Zbl 1304.76002 |
| [77] | Farrell, P. E.; Mitchell, L.; Wechsung, F., An augmented Lagrangian preconditioner for the 3D stationary incompressible Navier-Stokes equations at high Reynolds number, SIAM J. Sci. Comput., 41, 5, A3073-A3096, 2019 · Zbl 1448.65261 |
| [78] | Elman, H. C.; Forstall, V., Preconditioning techniques for reduced basis methods for parameterized elliptic partial differential equations, SIAM J. Sci. Comput., 37, 5, S177-S194, 2015 · Zbl 1457.65174 |
| [79] | Lindsay, P.; Fike, J.; Tezaur, I.; Carlberg, K., Preconditioned least-squares Petrov-Galerkin reduced order models, Internat. J. Numer. Methods Engrg., 123, 20, 4809-4843, 2022 · Zbl 07769311 |
| [80] | Carlberg, K.; Forstall, V.; Tuminaro, R., Krylov-subspace recycling via the POD-augmented conjugate-gradient method, SIAM J. Matrix Anal. Appl., 37, 3, 1304-1336, 2016 · Zbl 1348.15005 |
| [81] | Toro, E. F., Riemann Solvers and Numerical Methods for Fluid Dynamics: A Practical Introduction, 2013, Springer Science & Business Media |
| [82] | Shahbazi, K.; Fischer, P. F.; Ethier, C. R., A high-order discontinuous Galerkin method for the unsteady incompressible Navier-Stokes equations, J. Comput. Phys., 222, 1, 391-407, 2007 · Zbl 1216.76034 |
| [83] | Franca, L. P.; Frey, S. L.; Hughes, T. J., Stabilized finite element methods: I. Application to the advective-diffusive model, Comput. Methods Appl. Mech. Engrg., 95, 2, 253-276, 1992 · Zbl 0759.76040 |
| [84] | Harari, I.; Hughes, T. J., Stabilized finite element methods for steady advection—diffusion with production, Comput. Methods Appl. Mech. Engrg., 115, 1-2, 165-191, 1994 |
| [85] | Cockburn, B.; Dawson, C., Some extensions of the local discontinuous Galerkin method for convection-diffusion equations in multidimensions, (Mathematics of Finite Elements and Applications, vol. 10, 1999), 225-238 · Zbl 0960.65107 |
| [86] | Houston, P.; Schwab, C.; Süli, E., Discontinuous hp-finite element methods for advection-diffusion-reaction problems, SIAM J. Numer. Anal., 39, 6, 2133-2163, 2002 · Zbl 1015.65067 |
| [87] | Ayuso, B.; Marini, L. D., Discontinuous Galerkin methods for advection-diffusion-reaction problems, SIAM J. Numer. Anal., 47, 2, 1391-1420, 2009 · Zbl 1205.65308 |
| [88] | Borggaard, J.; Duggleby, A.; Hay, A.; Iliescu, T.; Wang, Z., Reduced-order modeling of turbulent flows, (Proceedings of MTNS, vol. 2008, 2008) |
| [89] | Stabile, G.; Ballarin, F.; Zuccarino, G.; Rozza, G., A reduced order variational multiscale approach for turbulent flows, Adv. Comput. Math., 45, 2349-2368, 2019 · Zbl 1435.65165 |
| [90] | Hijazi, S.; Stabile, G.; Mola, A.; Rozza, G., Data-driven POD-Galerkin reduced order model for turbulent flows, J. Comput. Phys., 416, Article 109513 pp., 2020 · Zbl 1437.76015 |
| [91] | Amsallem, D.; Zahr, M. J.; Farhat, C., Nonlinear model order reduction based on local reduced-order bases, Internat. J. Numer. Methods Engrg., 92, 10, 891-916, 2012 · Zbl 1352.65212 |
| [92] | K. Washabaugh, D. Amsallem, M. Zahr, C. Farhat, Nonlinear model reduction for CFD problems using local reduced-order bases, in: 42nd AIAA Fluid Dynamics Conference and Exhibit, 2012, p. 2686. |
| [93] | Kalashnikova, I.; Barone, M. F., On the stability and convergence of a Galerkin reduced order model (ROM) of compressible flow with solid wall and far-field boundary treatment, Int. J. Numer. Methods Eng., 83, 10, 1345-1375, 2010 · Zbl 1202.74123 |
| [94] | Gassner, G. J., A skew-symmetric discontinuous Galerkin spectral element discretization and its relation to SBP-SAT finite difference methods, SIAM J. Sci. Comput., 35, 3, A1233-A1253, 2013 · Zbl 1275.65065 |
| [95] | Svärd, M.; Nordström, J., Review of summation-by-parts schemes for initial-boundary-value problems, J. Comput. Phys., 268, 17-38, 2014 · Zbl 1349.65336 |
| [96] | Lerat, A.; Wu, Z., Stable conservative multidomain treatments for implicit Euler solvers, J. Comput. Phys., 123, 1, 45-64, 1996 · Zbl 0839.76065 |
| [97] | Nordström, J.; Gong, J.; Van der Weide, E.; Svärd, M., A stable and conservative high order multi-block method for the compressible Navier-Stokes equations, J. Comput. Phys., 228, 24, 9020-9035, 2009 · Zbl 1375.76036 |
| [98] | Harari, I.; Franca, L. P.; Oliveira, S. P., Streamline design of stability parameters for advection-diffusion problems, J. Comput. Phys., 171, 1, 115-131, 2001 · Zbl 0985.65146 |
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.
