×

Error estimates for projection-based dynamic augmented Lagrangian boundary condition enforcement, with application to fluid-structure interaction. (English) Zbl 1411.74059

Summary: In this work, we analyze the convergence of the recent numerical method for enforcing fluid-structure interaction (FSI) kinematic constraints in the immersogeometric framework for cardiovascular FSI. In the immersogeometric framework, the structure is modeled as a thin shell, and its influence on the fluid subproblem is imposed as a forcing term. This force has the interpretation of a Lagrange multiplier field supplemented by penalty forces, in an augmented Lagrangian formulation of the FSI kinematic constraints. Because of the non-matching fluid and structure discretizations used, no discrete inf-sup condition can be assumed. To avoid solving (potentially unstable) discrete saddle point problems, the penalty forces are treated implicitly and the multiplier field is updated explicitly. In the present contribution, we introduce the term dynamic augmented Lagrangian (DAL) to describe this time integration scheme. Moreover, to improve the stability and conservation of the DAL method, in a recently-proposed extension we projected the multiplier onto a coarser space and introduced the projection-based DAL method. In this paper, we formulate this projection-based DAL algorithm for a linearized parabolic model problem in a domain with an immersed Lipschitz surface, analyze the regularity of solutions to this problem, and provide error estimates for the projection-based DAL method in both the \(L^\infty(H^1)\) and \(L^\infty(L^2)\) norms. Numerical experiments indicate that the derived estimates are sharp and that the results of the model problem analysis can be extrapolated to the setting of nonlinear FSI, for which the numerical method was originally proposed.

MSC:

74S05 Finite element methods applied to problems in solid mechanics
76M10 Finite element methods applied to problems in fluid mechanics
65M60 Finite element, Rayleigh-Ritz and Galerkin methods for initial value and initial-boundary value problems involving PDEs
65M12 Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs
65M15 Error bounds for initial value and initial-boundary value problems involving PDEs
74F10 Fluid-solid interactions (including aero- and hydro-elasticity, porosity, etc.)
76Z05 Physiological flows
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bazilevs, Y., Takizawa, K. and Tezduyar, T. E., Computational Fluid-Structure Interaction: Methods and Applications (Wiley, 2013). · Zbl 1286.74001
[2] Peskin, C. S., Flow patterns around heart valves: A numerical method, J. Comput. Phys.10 (1972) 252-271. · Zbl 0244.92002
[3] Griffith, B. E., Immersed boundary model of aortic heart valve dynamics with physiological driving and loading conditions, Int. J. Numer. Methods Biomed. Eng.28 (2012) 317-345. · Zbl 1243.92017
[4] Nobile, F., Coupling strategies for the numerical simulation of blood flow in deformable arteries by 3D and 1D models, Math. Comput. Model.49 (2009) 2152-2160. · Zbl 1171.76436
[5] Nobile, F. and Vergara, C., An effective fluid-structure interaction formulation for vascular dynamics by generalized Robin conditions, SIAM J. Sci. Comput.30 (2008) 731-763. · Zbl 1168.74038
[6] Astorino, M., Chouly, F. and Fernández, M. A., Robin based semi-implicit coupling in fluid-structure interaction: Stability analysis and numerics, SIAM J. Sci. Comput.31 (2009) 4041-4065. · Zbl 1323.74099
[7] Badia, S., Nobile, F. and Vergara, C., Fluid-structure partitioned procedures based on Robin transmission conditions, J. Comput. Phys.227 (2008) 7027-7051. · Zbl 1140.74010
[8] Badia, S., Nobile, F. and Vergara, C., Robin-Robin preconditioned Krylov methods for fluid-structure interaction problems, Comput. Methods Appl. Mech. Eng.198 (2009) 2768-2784. · Zbl 1228.76079
[9] Gee, M. W., Kuttler, U. and Wall, W. A., Truly monolithic algebraic multigrid for fluid-structure interaction, Int. J. Numer. Methods Eng.85 (2011) 987-1016. · Zbl 1217.74121
[10] Degroote, J. and Vierendeels, J., Multi-solver algorithms for the partitioned simulation of fluid-structure interaction, Comput. Methods Appl. Mech. Eng.200 (2011) 2195-2210. · Zbl 1230.74243
[11] Joosten, M. M., Dettmer, W. G. and Peric, D., Analysis of the block Gauss-Seidel solution procedure for a strongly coupled model problem with reference to fluid-structure interaction, Int. J. Numer. Methods Eng.78 (2009) 757-778. · Zbl 1183.74347
[12] Guidoboni, G., Glowinski, R., Cavallini, N. and Canic, S., Stable loosely-coupled-type algorithm for fluid-structure interaction in blood flow, J. Comput. Phys.228 (2009) 6916-6937. · Zbl 1261.76056
[13] Michler, C., van Brummelen, H. and de Borst, R., An investigation of interface-GMRES(R) for fluid-structure interaction problems with flutter and divergence, Comput. Mech.47 (2011) 17-29. · Zbl 1398.74086
[14] Roux, F. X. and Garaud, J. D., Domain decomposition methodology with Robin interface matching conditions for solving strongly coupled fluid-structure problems, Int. J. Multiscale Comput. Eng.7 (2009) 29-38.
[15] Baek, H. and Karniadakis, G. E., A convergence study of a new partitioned fluid-structure interaction algorithm based on fictitious mass and damping, J. Comput. Phys.231 (2012) 629-652. · Zbl 1426.76496
[16] Peskin, C. S., The immersed boundary method, Acta Numer.11 (2002) 479-517. · Zbl 1123.74309
[17] Mittal, R. and Iaccarino, G., Immersed boundary methods, Ann. Rev. Fluid Mech.37 (2005) 239-261. · Zbl 1117.76049
[18] Sotiropoulos, F. and Yang, X., Immersed boundary methods for simulating fluid-structure interaction, Prog. Aerosp. Sci.65 (2014) 1-21.
[19] Takizawa, K. and Tezduyar, T. E., Computational methods for parachute fluid-structure interactions, Arch. Comput. Methods Eng.19 (2012) 125-169. · Zbl 1354.76113
[20] Bazilevs, Y., Gohean, J. R., Hughes, T. J. R., Moser, R. D. and Zhang, Y., Patient-specific isogeometric fluid-structure interaction analysis of thoracic aortic blood flow due to implantation of the Jarvik 2000 left ventricular assist device, Comput. Methods Appl. Mech. Eng.198 (2009) 3534-3550. · Zbl 1229.74096
[21] Hsu, M.-C. and Bazilevs, Y., Fluid-structure interaction modeling of wind turbines: Simulating the full machine, Comput. Mech.50 (2012) 821-833. · Zbl 1311.74038
[22] Boffi, D. and Gastaldi, L., A fictitious domain approach with Lagrange multiplier for fluid-structure interactions, Numer. Math.135 (2017) 711-732. · Zbl 1457.65097
[23] Bengzon, F. and Larson, M. G., Adaptive finite element approximation of multiphysics problems: A fluid-structure interaction model problem, Int. J. Numer. Methods Eng.84 (2010) 1451-1465. · Zbl 1202.74161
[24] Burman, E. and Fernández, M. A., Stabilization of explicit coupling in fluid-structure interaction involving fluid incompressibility, Comput. Methods Appl. Mech. Eng.198 (2009) 766-784. · Zbl 1229.76045
[25] Bukač, M., Yotov, I., Zakerzadeh, R. and Zunino, P., Partitioning strategies for the interaction of a fluid with a poroelastic material based on a nitsches coupling approach, Comput. Methods Appl. Mech. Eng.292 (2015) 138-170. · Zbl 1423.76419
[26] Lozovskiy, A., Olshanskii, M. A., Salamatova, V. and Vassilevski, Y. V., An unconditionally stable semi-implicit FSI finite element method, Comput. Methods Appl. Mech. Eng.297 (2015) 437-454. · Zbl 1423.76256
[27] Wang, C., Wu, M. C. H., Xu, F., Hsu, M.-C. and Bazilevs, Y., Modeling of a hydraulic arresting gear using fluid-structure interaction and isogeometric analysis, Comput. Fluids142 (2017) 3-14. · Zbl 1390.76013
[28] Wu, M. C. H., Kamensky, D., Wang, C., Herrema, A. J., Xu, F., Pigazzini, M. S., Verma, A., Marsden, A. L., Bazilevs, Y. and Hsu, M.-C., Optimizing fluid-structure interaction systems with immersogeometric analysis and surrogate modeling: Application to a hydraulic arresting gear, Comput. Methods Appl. Mech. Eng.316 (2017) 668-693. · Zbl 1439.74117
[29] Quarteroni, A. and Formaggia, L., Mathematical modeling and numerical simulation of the cardiovascular system, in Computational Models for the Human Body, ed. Ayachc, N., , Vol. 12 (Elsevier, 2004), pp. 3-127.
[30] Yu, Y., Xie, F., Yan, H., Constantinides, Y., Oakley, O. and Karniadakis, G. E., Suppression of vortex-induced vibrations by fairings: A numerical study, J. Fluids Struct.54 (2015) 679-700.
[31] Kamensky, D., Hsu, M.-C., Schillinger, D., Evans, J. A., Aggarwal, A., Bazilevs, Y., Sacks, M. S. and Hughes, T. J. R., An immersogeometric variational framework for fluid-structure interaction: Application to bioprosthetic heart valves, Comput. Methods Appl. Mech. Eng.284 (2015) 1005-1053. · Zbl 1423.74273
[32] Hsu, M.-C., Kamensky, D., Bazilevs, Y., Sacks, M. S. and Hughes, T. J. R., Fluid-structure interaction analysis of bioprosthetic heart valves: Significance of arterial wall deformation, Comput. Mech.54 (2014) 1055-1071. · Zbl 1311.74039
[33] Hsu, M.-C., Kamensky, D., Xu, F., Kiendl, J., Wang, C., Wu, M. C. H., Mineroff, J., Reali, A., Bazilevs, Y. and Sacks, M. S., Dynamic and fluid-structure interaction simulations of bioprosthetic heart valves using parametric design with T-splines and Fung-type material models, Comput. Mech.55 (2015) 1211-1225. · Zbl 1325.74048
[34] Kamensky, D., Evans, J. A. and Hsu, M.-C., Stability and conservation properties of collocated constraints in immersogeometric fluid-thin structure interaction analysis, Commun. Comput. Phys.18 (2015) 1147-1180. · Zbl 1373.76093
[35] Kamensky, D., Hsu, M.-C., Yu, Y., Evans, J. A., Sacks, M. S. and Hughes, T. J. R., Immersogeometric cardiovascular fluid-structure interaction analysis with divergence-conforming B-splines, Comput. Methods Appl. Mech. Eng.314 (2017) 408-472. · Zbl 1439.76077
[36] Kamensky, D., Evans, J. A., Hsu, M.-C. and Bazilevs, Y., Projection-based stabilization of interface Lagrange multipliers in immersogeometric fluid-thin structure interaction analysis, with application to heart valve modeling, Comput. Math. Appl.74 (2017) 2068-2088. · Zbl 1397.65274
[37] Hansbo, P. and Hermansson, J., Nitsche’s method for coupling non-matching meshes in fluid-structure vibrational problems, Comput. Mech.32 (2003) 134-139. · Zbl 1035.74055
[38] Massing, A., Larson, M., Logg, A. and Rognes, M., A nitsche-based cut finite element method for a fluid-structure interaction problem, Commun. Appl. Math. Comput. Sci.10 (2015) 97-120. · Zbl 1326.74122
[39] Burman, E., Hansbo, P., Larson, M. G. and Zahedi, S., Cut finite element methods for coupled bulk-surface problems, Numer. Math.133 (2016) 203-231. · Zbl 1341.65044
[40] Soares, J. S., Feaver, K. R., Zhang, W., Kamensky, D., Aggarwal, A. and Sacks, M. S., Biomechanical behavior of bioprosthetic heart valve heterograft tissues: Characterization, simulation, and performance, Cardiovasc. Eng. Technol.7 (2016) 309-351.
[41] Marom, G., Numerical methods for fluid-structure interaction models of aortic valves, Arch. Comput. Methods Eng.22 (2015) 595-620. · Zbl 1348.74099
[42] Kheradvar, A.et al., Emerging trends in heart valve engineering: Part iv. computational modeling and experimental studies, Ann. Biomed. Eng.43 (2015) 2314-2333.
[43] Kiendl, J., Bletzinger, K.-U., Linhard, J. and Wüchner, R., Isogeometric shell analysis with Kirchhoff-Love elements, Comput. Methods Appl. Mech. Eng.198 (2009) 3902-3914. · Zbl 1231.74422
[44] van Brummelen, E. H., Added mass effects of compressible and incompressible flows in fluid-structure interaction, J. Appl. Mech.76 (2009) 021206.
[45] E. Burman, J. Guzmán, M. A. Sánchez and M. Sarkis, Robust flux error estimation of nitsches method for high contrast interface problems, preprint (2016), arXiv:1602.00603. · Zbl 1412.65204
[46] Hughes, T. J. R., Cottrell, J. A. and Bazilevs, Y., Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement, Comput. Methods Appl. Mech. Eng.194 (2005) 4135-4195. · Zbl 1151.74419
[47] Cottrell, J. A., Hughes, T. J. R. and Bazilevs, Y., Isogeometric Analysis: Toward Integration of CAD and FEA (Wiley, 2009). · Zbl 1378.65009
[48] Xu, F., Schillinger, D., Kamensky, D., Varduhn, V., Wang, C. and Hsu, M.-C., The tetrahedral finite cell method for fluids: Immersogeometric analysis of turbulent flow around complex geometries, Comput. Fluids141 (2016) 135-154. · Zbl 1390.76372
[49] Hsu, M.-C., Wang, C., Xu, F., Herrema, A. J. and Krishnamurthy, A., Direct immersogeometric fluid flow analysis using B-rep CAD models, Comput. Aid. Geom. Des.43 (2016) 143-158. · Zbl 1418.76042
[50] Wang, C., Xu, F., Hsu, M.-C. and Krishnamurthy, A., Rapid B-rep model preprocessing for immersogeometric analysis using analytic surfaces, Comput. Aid. Geom. Des.52-53 (2017) 190-204. · Zbl 1505.65101
[51] Glowinski, R., Pan, T.-W. and Periaux, J., A fictitious domain method for Dirichlet problem and applications, Comput. Methods Appl. Mech. Eng.111 (1994) 283-303. · Zbl 0845.73078
[52] Glowinski, R., Pan, T.-W., Hesla, T. I. and Joseph, D. D., A distributed Lagrange multiplier/fictitious domain method for particulate flows, Int. J. Multiphase Flow25 (1999) 755-794. · Zbl 1137.76592
[53] Boffi, D., Cavallini, N. and Gastaldi, L., The finite element immersed boundary method with distributed Lagrange multiplier, SIAM J. Numer. Anal.53 (2015) 2584-2604. · Zbl 1330.65147
[54] Hestenes, M. R., Multiplier and gradient methods, J. Optim. Theory Appl.4 (1969) 303-320. · Zbl 0174.20705
[55] Powell, M. J. D., A method for nonlinear constraints in minimization problems, in Optimization, ed. Fletcher, R. (Academic Press, 1969), pp. 283-298.
[56] Simo, J. C. and Laursen, T. A., An augmented Lagrangian treatment of contact problems involving friction, Comput. Struct.42 (1992) 97-116. · Zbl 0755.73085
[57] Goldstein, D., Handler, R. and Sirovich, L., Modeling a no-slip flow boundary with an external force field, J. Comput. Phys.105 (1993) 354-366. · Zbl 0768.76049
[58] Goldstein, D. B. and Tuan, T.-C., Secondary flow induced by riblets, J. Fluid Mech.363 (1998) 115-151. · Zbl 0924.76038
[59] Strand, J. S. and Goldstein, D. B., Application of passive surface textures to control the growth of turbulent spots at moderately high reynolds numbers, Int. J. Flow Control2 (2010) 73-89.
[60] Strand, J. S. and Goldstein, D. B., Direct numerical simulations of riblets to constrain the growth of turbulent spots, J. Fluid Mech.668 (2011) 267-292. · Zbl 1225.76166
[61] Doolittle, C. J., Drews, S. D. and Goldstein, D. B., Near-field flow structures about subcritical surface roughness, Phys. Fluids26 (2014) 124106.
[62] Benson, D. J. and Okazawa, S., Contact in a multi-material Eulerian finite element formulation, Comput. Methods Appl. Mech. Eng.193 (2004) 4277-4298. · Zbl 1068.74069
[63] Haufe, A., Weimar, K. and Göhner, U., Advanced airbag simulation using fluid-structure-interaction and the Eluerian method in LS-DYNA, in Proc. of LS-DYNA Anwenderforum (2004).
[64] Chew, G. G., Howard, I. C. and Patterson, E. A., Simulation of damage in a porcine prosthetic heart valve, J. Med. Eng. Technol.23 (1999) 178-189.
[65] Carmody, C. J., Burriesci, G., Howard, I. C. and Patterson, E. A., An approach to the simulation of fluid-structure interaction in the aortic valve, J. Biomech.39 (2006) 158-169.
[66] Sturla, F., Votta, E., Stevanella, M., Conti, C. A. and Redaelli, A., Impact of modeling fluid-structure interaction in the computational analysis of aortic root biomechanics, Med. Eng. Phys.35 (2013) 1721-1730.
[67] Wu, W., Pott, D., Mazza, B., Sironi, T., Dordoni, E., Chiastra, C., Petrini, L., Pennati, G., Dubini, G., Steinseifer, U., Sonntag, S., Kuetting, M. and Migliavacca, F., Fluid-structure interaction model of a percutaneous aortic valve: Comparison with an in vitro test and feasibility study in a patient-specific case, Ann. Biomed. Eng.44 (2016) 590-603.
[68] Souli, M., Sofiane, Y. and Olovsson, L., ALE and fluid/structure interaction in LS-DYNA, in Proc. Emerging Technology in Fluids, Structures, and Fluid-Structure Interactions (ASME, 2004).
[69] Souli, M., Capron, N. and Khan, U., Fluid structure interaction and airbag ALE for out of position, in Proc. of ASME Pressure Vessels and Piping Conf. (AMSE, 2005).
[70] Souli, M., Wang, J., Do, I. and Hao, C., ALE and fluid structure interaction in LS-DYNA, in Proc. 8th Int. LS-DYNA Users Conf. (2011).
[71] Mitrea, M., The initial Dirichlet boundary value problem for general second order parabolic systems in nonsmooth manifolds, Commun. Partial Differential Equations26 (2001) 1975-2036. · Zbl 0993.35038
[72] Bazilevs, Y., Hsu, M.-C. and Scott, M. A., Isogeometric fluid-structure interaction analysis with emphasis on non-matching discretizations, and with application to wind turbines, Comput. Methods Appl. Mech. Eng.249-252 (2012) 28-41. · Zbl 1348.74094
[73] Esmaily-Moghadam, M., Bazilevs, Y., Hsia, T.-Y., Vignon-Clementel, I. E., Marsden, A. L., and , A comparison of outlet boundary treatments for prevention of backflow divergence with relevance to blood flow simulations, Comput. Mech.48 (2011) 277-291. · Zbl 1398.76102
[74] J. A. Evans, Divergence-free B-spline discretizations for viscous incompressible flows, Ph.D. thesis, University of Texas at Austin, Austin, Texas, United States (2011).
[75] Evans, J. A. and Hughes, T. J. R., Isogeometric divergence-conforming B-splines for the steady Navier-Stokes equations, Math. Models Methods Appl. Sci.23 (2013) 1421-1478. · Zbl 1383.76337
[76] Evans, J. A. and Hughes, T. J. R., Isogeometric divergence-conforming B-splines for the unsteady Navier-Stokes equations, J. Comput. Phys.241 (2013) 141-167. · Zbl 1349.76054
[77] Buffa, A., Sangalli, G. and Vázquez, R., Isogeometric analysis in electromagnetics: B-splines approximation, Comput. Methods Appl. Mech. Eng.199 (2010) 1143-1152. · Zbl 1227.78026
[78] Buffa, A., Rivas, J., Sangalli, G. and Vásquez, R., Isogeometric discrete differential forms in three dimensions, SIAM J. Numer. Anal.49 (2011) 814-844. · Zbl 1225.65100
[79] J. Kiendl, Isogeometric analysis and shape optimal design of shell structures, PhD thesis, Lehrstuhl für Statik, Technische Universität München (2011).
[80] Kiendl, J., Hsu, M.-C., Wu, M. C. H. and Reali, A., Isogeometric Kirchhoff-Love shell formulations for general hyperelastic materials, Comput. Methods Appl. Mech. Eng.291 (2015) 280-303. · Zbl 1423.74177
[81] Bazilevs, Y. and Hughes, T. J. R., Weak imposition of Dirichlet boundary conditions in fluid mechanics, Comput. Fluids36 (2007) 12-26. · Zbl 1115.76040
[82] Bazilevs, Y., Michler, C., Calo, V. M. and Hughes, T. J. R., Weak Dirichlet boundary conditions for wall-bounded turbulent flows, Comput. Methods Appl. Mech. Eng.196 (2007) 4853-4862. · Zbl 1173.76397
[83] Bazilevs, Y., Michler, C., Calo, V. M. and Hughes, T. J. R., Isogeometric variational multiscale modeling of wall-bounded turbulent flows with weakly enforced boundary conditions on unstretched meshes, Comput. Methods Appl. Mech. Eng.199 (2010) 780-790. · Zbl 1406.76023
[84] Hsu, M.-C., Akkerman, I. and Bazilevs, Y., Wind turbine aerodynamics using ALE-VMS: Validation and the role of weakly enforced boundary conditions, Comput. Mech.50 (2012) 499-511.
[85] Pinsky, P. M., A finite element formulation for elastoplasticity based on a three-field variational equation, Comput. Methods Appl. Mech. Eng.61 (1987) 41-60. · Zbl 0591.73082
[86] Hager, C. and Wohlmuth, B. I., Nonlinear complementarity functions for plasticity problems with frictional contact, Comput. Methods Appl. Mech. Eng.198 (2009) 3411-3427. · Zbl 1230.74225
[87] Chung, J. and Hulbert, G. M., A time integration algorithm for structural dynamics with improved numerical dissipation: The generalized-\( \alpha\) method, J. Appl. Mech.60 (1993) 371-75. · Zbl 0775.73337
[88] Bazilevs, Y., Calo, V. M., Hughes, T. J. R. and Zhang, Y., Isogeometric fluid-structure interaction: Theory, algorithms, and computations, Comput. Mech.43 (2008) 3-37. · Zbl 1169.74015
[89] Lions, J. L. and Magenes, E., Non-Homogeneous Boundary Value Problems and Applications (Springer, 1972). · Zbl 0227.35001
[90] Babuška, I.. The finite element method with Lagrangian multipliers, Numer. Math.20 (1973) 179-192. · Zbl 0258.65108
[91] Patel, A., Lagrange multiplier method with penalty for elliptic and parabolic interface problems, J. Appl. Math. Comput.37 (2011) 37-56. · Zbl 1291.65270
[92] Jerison, D. and Kenig, C. E., The inhomogeneous Dirichlet problem in Lipschitz domains, J. Funct. Anal.130 (1995) 161-219. · Zbl 0832.35034
[93] S. E. Mikhailov, Traces, extensions, co-normal derivatives and solution regularity of elliptic systems with smooth and non-smooth coefficients, http://www.science direct.com/science/article/pii/S0022247X10010358. · Zbl 1308.35086
[94] Costabel, M., Dauge, M. and Nicaise, S., Analytic regularity for linear elliptic systems in polygons and polyhedra, Math. Models Methods Appl. Sci.22 (2012) 1250015. · Zbl 1257.35056
[95] Lai, M.-C. and Peskin, C. S., An immersed boundary method with formal second-order accuracy and reduced numerical viscosity, J. Comput. Phys.160 (2000) 705-719. · Zbl 0954.76066
[96] Evans, L. C., Partial Differential Equations, , Vol. 19 (Amer. Math. Soc., 2002).
[97] Puso, M. A., Sanders, J., Settgast, R. and Liu, B., An embedded mesh method in a multiple material ALE, Comput. Methods Appl. Mech. Eng.245-246 (2012) 273-289. · Zbl 1354.74294
[98] Hsu, M.-C. and Bazilevs, Y., Blood vessel tissue prestress modeling for vascular fluid-structure interaction simulations, Finite Elem. Anal. Des.47 (2011) 593-599.
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.