×

Uzawa methods for a class of block three-by-three saddle-point problems. (English) Zbl 1463.65046

The paper deals with a class of block three-by-three saddle-point problems which appear when finite element methods are used to solve time-dependent Maxwell equations with discontinuous coefficients. Even though the considered block three-by-three linear system can be seen as a special case of the classical saddle-point problem, well known numerical methods cannot be used directly. Indeed, the considered linear system needs numerical methods based on its specific structure. Therefore the authors extend the Uzawa method, already presented in literature. Such extension requires the exact solution of a symmetric indefinite system of linear equations at each step. To avoid heavy computations at each step, an inexact Uzawa method is proposed. Theoretical analysis is provided to show that the inexact Uzawa method converges to the unique solution of the considered linear system under suitable assumptions. Four algorithms are presented and studied in details and then compared. Their performance is tested and significant numerical examples are reported to enlighten the features of the presented approach. Remarkably, numerical results also show that the inexact Uzawa method is more effective that the MINRES method.

MSC:

65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices

Software:

IFISS; Matlab
Full Text: DOI

References:

[1] ChenZM, DuQ, ZouJ. Finite element methods with matching and nonmatching meshes for Maxwell equations with discontinuous coefficients. SIAM J Numer Anal. 2000;37:1542-1570. · Zbl 0964.78017
[2] HanDR, YuanXM. Local linear convergence of the alternating direction method of multipliers for quadratic programs. SIAM J Numer Anal. 2013;51:3446-3457. · Zbl 1285.90033
[3] ArridgeSR. Optical tomography in medical imaging. Inverse Problems. 1999;15:41-93. · Zbl 0926.35155
[4] BrezziF, FortinM. Mixed and hybrid finite element methods. New York, NY: Springer‐Verlag; 1991. · Zbl 0788.73002
[5] ChristiansenSH. Discrete Fredholm properties and convergence estimates for the electric field integral equation. Math Comput. 2004;73:143-167. · Zbl 1034.65089
[6] DayD, HerouxMA. Solving complex‐valued linear systems via equivalent real formulations. SIAM J Sci Comput. 2001;23:480-498. · Zbl 0992.65020
[7] ElmanHC, RamageA, SilvesterDJ. Algorithm 866: IFISS, a Matlab toolbox for modelling incompressible flow. ACM Trans Math Softw. 2007;33:1-18. · Zbl 1365.65326
[8] PerugiaI, SimonciniV. Block‐diagonal and indefinite symmetric preconditioners for mixed finite element formulations. Numer Linear Algebra Appl. 2000;7:585-616. · Zbl 1051.65038
[9] HestenesMR, StiefelE. Methods of conjugate gradients for solving linear systems. J Res Nat Bur Stand. 1952;49:409-436. · Zbl 0048.09901
[10] Van der VorstH. Iterative Krylov methods for large linear systems. Cambridge, UK:Cambridge University Press; 2003. · Zbl 1023.65027
[11] BacutaC. A unified approach for Uzawa algorithms. SIAM J Numer Anal. 2006;44:2633-2649. · Zbl 1128.76052
[12] BacutaC. Schur complements on Hilbert spaces and saddle point systems. J Comput Appl Math. 2009;225:581-593. · Zbl 1163.65028
[13] BacutaC, MccrackenB, ShuL. Residual reduction algorithms for non‐symmetric saddle point problems. J Comput Appl Math. 2011;235:1614-1628. · Zbl 1206.65244
[14] BrambleJH, PasciakJE, VassilevAT. Analysis of the inexact Uzawa algorithm for saddle point problems. SIAM J Numer Anal. 1997;34:1072-1092. · Zbl 0873.65031
[15] BrambleJH, PasciakJE, VassilevAT. Uzawa type algorithms for nonsymmetric saddle point problems. Math Comput. 2000;69:667-689. · Zbl 0951.65122
[16] ChengX. On the nonlinear inexact Uzawa algorithm for saddle‐point problems. SIAM J Numer Anal. 2000;37:1930-1934. · Zbl 0960.65032
[17] ElmanHC, GolubGH. Inexact and preconditioned Uzawa algorithms for saddle point problems. SIAM J Numer Anal. 1994;31:1645-1661. · Zbl 0815.65041
[18] HuQ, ZouJ. An iterative method with variable relaxation parameters for saddle‐point problems. SIAM J Matrix Anal Appl. 2001;23:317-338. · Zbl 1007.65019
[19] HuQ, ZouJ. Two new variants of nonlinear inexact Uzawa algorithms for saddle‐point problems. Numerische Mathematik. 2002;93:333-359. · Zbl 1019.65024
[20] HuQ, ZouJ. Nonlinear inexact Uzawa algorithms for linear and nonlinear saddle‐point problems. SIAM J Optim. 2006;16:798-825. · Zbl 1098.65034
[21] ZhangG‐F, YangJ‐L, WangS‐S. On generalized parameterized inexact Uzawa method for a block two‐by‐two linear system. J Comput Appl Math. 2014;255:193-207. · Zbl 1291.65115
[22] ZulehnerW. Analysis of iterative methods for saddle point problems: a unified approach. Math Comput. 2002;71:479-505. · Zbl 0996.65038
[23] BaiZ‐Z, GolubGH, LuL‐Z, YinJ‐F. Block triangular and skew‐Hermitian splitting method for positive‐definite linear systems. SIAM J Sci Comput. 2005;26:844-863. · Zbl 1079.65028
[24] BaiZ‐Z, GolubGH, NgMK. Hermitian and skew‐Hermitian splitting methods for non‐Hermitian positive definite linear systems. SIAM J Matrix Anal Appl. 2003;24:603-626. · Zbl 1036.65032
[25] BaiZ‐Z, GolubGH, PanJ‐Y. Preconditioned Hermitian and skew‐Hermitian splitting methods for non‐Hermitian positive semidefinite linear systems. Numerische Mathematik. 2004;98:1-32. · Zbl 1056.65025
[26] DynN, FergusonWE. The numerical solution of equality constrained quadratic programming problems. Math Comput. 1983;41:165-170. · Zbl 0527.49030
[27] GolubGH, WathenAJ. An iteration for indefinite systems and its application to the Navier‐Stokes equations. SIAM J Sci Comput. 1998;19:530-539. · Zbl 0912.76053
[28] GolubGH, WuX, YuanJ‐Y. SOR‐like methods for augmented systems. BIT Numer Math. 2001;41:71-85. · Zbl 0991.65036
[29] ArioliM, ManziniG. A null space algorithm for mixed finite‐element approximations of Darcy’s equation. Commun Numer Meth Eng. 2002;18:645-657. · Zbl 1073.76581
[30] GouldNIM, HribarME, NocedalJ. On the solution of equality constrained quadratic programming problems arising in optimization. SIAM J Sci Comput. 2001;23:1376-1395. · Zbl 0999.65050
[31] SarinV, SamehA. An efficient iterative method for the generalized Stokes problem. SIAM J Sci Comput. 1998;19:206-226. · Zbl 0911.76039
[32] BenziM. Solution of equality‐constrained quadratic programming problems by a projection iterative method. Rend Mat Appl. 1993;13:275-296. · Zbl 0799.65066
[33] ForsgrenA. Inertia‐controlling factorizations for optimization algorithms. Appl Numer Math. 2002;43:91-107. · Zbl 1016.65039
[34] GreifC, MouldingE, OrbanD. Bounds on eigenvalues of matrices arising from interior‐point methods. SIAM J Optim. 2014;24:49-83. · Zbl 1291.15008
[35] MoriniB, SimonciniV, TaniM. Spectral estimates for unreduced symmetric KKT systems arising from interior point methods. Numer Linear Algebra Appl. 2016;23:776-800. · Zbl 1413.65246
[36] MoriniB, SimonciniV, TaniM. A comparison of reduced and unreduced KKT systems arising from interior point methods. Comput Optim Appl. 2017;68:1-27. · Zbl 1406.90088
[37] ArrowK, HurwiczL, UzawaH. Studies in nonlinear programming. Stanford, CA: Stanford University Press; 1958. · Zbl 0091.16002
[38] BaiZ‐Z, WangZ‐Q. On parameterized inexact Uzawa methods for generalized saddle point problems. Linear Algebra Appl. 2008;428:2900-2932. · Zbl 1144.65020
[39] YoungDMJr. Iterative Solution for large linear systems. New York, NY: Academic Press; 1971. · Zbl 0231.65034
[40] BankRE, WelfertBD, YserentantH. A class of iterative methods for solving saddle point problems. Numerische Mathematik. 1990;56:645-666. · Zbl 0684.65031
[41] ChenX. On preconditioned Uzawa methods and SOR methods for saddle‐point problems. J Comput Appl Math. 1998;100:207-224. · Zbl 0935.65055
[42] QueckW. The convergence factor of preconditioned algorithms of the Arrow‐Hurwicz type. SIAM J Numer Anal. 1989;26:1016-1030. · Zbl 0674.65008
[43] NikolovaM, NgMK, ZhangSQ, ChingW‐K. Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization. SIAM J Imaging Sci. 2008;1:2-25. · Zbl 1207.94017
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.