Threshold incomplete factorization constraint preconditioners for saddle-point matrices. (English) Zbl 1390.15045
Summary: This paper presents a drop-threshold incomplete \(\mathrm{LD}^{-1}\mathrm{L}^{\mathrm{T}}(\delta)\) factorization constraint preconditioner for saddle-point systems using a threshold parameter \(\delta\). A transformed saddle-point matrix is partitioned into a block structure with blocks of order 1 and 2 constituting ‘a priori pivots’. Based on these pivots an incomplete \(\mathrm{LD}^{-1}\mathrm{L}^{\mathrm{T}}(\delta)\) factorization constraint preconditioner is computed that approaches an exact form as \(\delta\) approaches zero. We prove that both the exact and incomplete factorizations exist such that the entries of the constraint block remain unaltered in the triangular factors. Numerical results are presented for validation.
MSC:
| 15A23 | Factorization of matrices |
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
| 65F50 | Computational methods for sparse matrices |
References:
| [1] | Schilders, W. H.A., Solution of indefinite linear systems using an LQ decomposition for the linear constraints, Linear Algebra Appl., 431, 381-395 (2009) · Zbl 1169.65039 |
| [2] | De Neit, A. C.; Wubs, F. W., Numerically stable \(L D L^T\)-factorization of \(F\)-type saddle point matrices, IMA J. Numer. Anal., 29, 208-234 (2009) · Zbl 1161.65022 |
| [3] | Lungten, S.; Schilders, W. H.A.; Maubach, J. M.L., Sparse inverse incidence matrices for Schilders’ factorization applied to resistor network modeling, Numer. Algebra Control Optim., 4, 227-239 (2014) · Zbl 1333.65049 |
| [4] | Davis, T. A., Direct Methods for Sparse Linear Systems (2006), SIAM · Zbl 1119.65021 |
| [5] | Golub, G. H.; Van Loan, C. F., Matrix Computations (2013), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore · Zbl 1268.65037 |
| [6] | Lungten, S., Solution Methods for Indefinite Systems of Linear Equations in Saddle-Point Form (2016), Ph.D. thesis, The Netherlands |
| [7] | Mastronardi, N.; Dooren, P. V., The antitriangular factorization of symmetric matrices, SIAM J. Matrix Anal. Appl., 34, 1, 173-196 (2013) · Zbl 1272.65031 |
| [8] | Pestana, J.; Wathen, A. J., The antitriangular factorization of saddle point matrices, SIAM J. Matrix Anal. Appl., 35, 2, 339-353 (2014) · Zbl 1385.65027 |
| [9] | Pestana, J.; Rees, T., Null-space preconditioners for saddle point systems, SIAM J. Matrix Anal. Appl., 37, 3, 1103-1128 (2016) · Zbl 1347.65060 |
| [10] | Lungten, S.; Schilders, W. H.A.; Maubach, J. M.L., Sparse block factorization of saddle point matrices, Linear Algebra Appl., 502, 214-242 (2016) · Zbl 1386.65128 |
| [11] | Gould, N. I.M., On modified factorizations for large-scale linearly constrained optimization, SIAM J. Optim., 9, 4, 1041-1063 (1999) · Zbl 0957.65063 |
| [12] | Golub, G. H.; Greif, C., On solving block-structured indefinite linear systems, SIAM J. Sci. Comput., 24, 6, 2076-2092 (2003) · Zbl 1036.65033 |
| [13] | Benzi, M.; Liu, J., Block preconditioning for saddle point systems with indefinite (1, 1) block, Int. J. Comput. Math., 84, 8, 1117-1129 (2007) · Zbl 1123.65028 |
| [14] | Bramble, J. H.; Pasciak, J. E., A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems, Math. Comp., 50, 181, 1-17 (1988) · Zbl 0643.65017 |
| [15] | de Sturler, E.; Liesen, J., Block-diagonal and constraint preconditioners for nonsymmetric indefinite linear systems. Part I: theory, SIAM J. Sci. Comput., 26, 5, 1598-1619 (2005) · Zbl 1078.65027 |
| [16] | Fairag, F. A.; Wathen, A. J., A block preconditioning technique for the streamfunction-vorticity formulation of the Navier-Stokes equations, Numer. Methods Partial Differential Equations, 28, 3, 888-898 (2012) |
| [17] | Komzsik, L.; Poschmann, P.; Sharapov, I., A preconditioning technique for indefinite linear systems, Finite Elem. Anal. Des., 26, 3, 253-258 (1997) · Zbl 0896.65029 |
| [18] | Melchior, S. A.; Legat, V.; Van Dooren, P.; Wathen, A. J., Analysis of preconditioned iterative solvers for incompressible flow problems, Internat. J. Numer. Methods Fluids, 68, 3, 269-286 (2012) · Zbl 1426.76290 |
| [19] | Murphy, M. F.; Golub, G. H.; Wathen, A. J., A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput., 21, 6, 1969-1972 (2000) · Zbl 0959.65063 |
| [20] | Perugia, I.; Simoncini, V., Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations, Numer. Linear Algebra Appl., 7, 7-8, 585-616 (2000) · Zbl 1051.65038 |
| [21] | Rees, T.; Wathen, A. J., Preconditioning iterative methods for the optimal control of the Stokes equations, SIAM J. Sci. Comput., 33, 5, 2903-2926 (2011) · Zbl 1300.49009 |
| [22] | Schöberl, J.; Zulehner, W., Symmetric indefinite preconditioners for saddle point problems with applications to PDE-constrained optimization problems, SIAM J. Matrix Anal. Appl., 29, 3, 752-773 (2007) · Zbl 1154.65029 |
| [23] | Stoll, M.; Wathen, A. J., Preconditioning for partial differential equation constrained optimization with control constraints, Numer. Linear Algebra Appl., 19, 1, 53-71 (2012) · Zbl 1274.65189 |
| [24] | Gould, N. I.M.; Hribar, M. E.; Nocedal, J., On the solution of equality constrained quadratic programming problems arising in optimization, SIAM J. Sci. Comput., 23, 4, 1376-1395 (2001) · Zbl 0999.65050 |
| [25] | Rozlozník, M.; Simoncini, V., Krylov subspace methods for saddle point problems with indefinite preconditioning, SIAM J. Matrix Anal. Appl., 24, 2, 368-391 (2002) · Zbl 1021.65016 |
| [26] | Gould, N. I.M.; Orban, D.; Rees, T., Projected Krylov methods for saddle-point systems, SIAM J. Matrix Anal. Appl., 35, 4, 1329-1343 (2014) · Zbl 1312.65043 |
| [27] | Keller, C.; Gould, N. I.M.; Wathen, A. J., Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl., 21, 4, 1300-1317 (2000) · Zbl 0960.65052 |
| [28] | Luksan, L.; Vlcek, J., Indefinitely preconditioned inexact Newton method for large sparse equality constrained nonlinear programming problems, Numer. Linear Algebra Appl., 5, 3, 219-247 (1998) · Zbl 0937.65066 |
| [29] | Benzi, M.; Golub, G. H.; Liesen, J., Numerical solution of saddle point problems, Acta Numer., 14, 1-137 (2005) · Zbl 1115.65034 |
| [30] | Benzi, M.; Wathen, A. J., Some preconditioning techniques for saddle point problems, (Model Order Reduction: Theory, Research Aspects and Applications. Model Order Reduction: Theory, Research Aspects and Applications, Series: Mathematics in Industry (2008), Springer-Verlag), 195-211 · Zbl 1152.65425 |
| [31] | Ewing, R. E.; Lazarov, R. D.; Lu, P.; Vassilevski, P. S., Preconditioning indefinite systems arising from mixed finite element discretization of second-order elliptic problems, (Preconditioned Conjugate Gradient Methods (1990), Springer), 28-43 · Zbl 0719.65024 |
| [32] | Dollar, H. S.; Gould, N. I.M.; Schilders, W. H.A.; Wathen, A. J., Implicit-factorization preconditioning and iterative solvers for regularized saddle-point systems, SIAM J. Matrix Anal. Appl., 28, 1, 170-189 (2006) · Zbl 1104.65310 |
| [33] | Dollar, H. S.; Gould, N. I.M.; Schilders, W. H.A.; Wathen, A. J., Using constraint preconditioners with regularized saddle-point problems, Comput. Optim. Appl., 36, 2-3, 249-270 (2007) · Zbl 1124.65033 |
| [34] | Dollar, H. S.; Wathen, A. J., Approximate factorization constraint preconditioners for saddle-point matrices, SIAM J. Sci. Comput., 27, 5, 1555-1572 (2006) · Zbl 1105.65047 |
| [35] | Gustafsson, I., A class of first order factorization methods, BIT Numer. Math., 18, 2, 142-156 (1978) · Zbl 0386.65006 |
| [36] | Kershaw, D. S., The incomplete Cholesky—conjugate gradient method for the iterative solution of systems of linear equations, J. Comput. Phys., 26, 1, 43-65 (1978) · Zbl 0367.65018 |
| [37] | Li, N.; Saad, Y., Crout versions of ILU factorization with pivoting for sparse symmetric matrices, Electron. Trans. Numer. Anal., 20, 75-85 (2005) · Zbl 1075.65045 |
| [38] | Li, N.; Saad, Y.; Chow, E., Crout versions of ILU for general sparse matrices, SIAM J. Sci. Comput., 25, 2, 716-728 (2003) · Zbl 1042.65025 |
| [39] | Manteuffel, T. A., An incomplete factorization technique for positive definite linear systems, Math. Comp., 34, 150, 473-497 (1980) · Zbl 0422.65018 |
| [40] | Meijerink, J. A.; van der Vorst, H. A., An iterative solution method for linear systems of which the coefficient matrix is a symmetric \(m\)-matrix, Math. Comp., 31, 137, 148-162 (1977) · Zbl 0349.65020 |
| [41] | Saad, Y., ILUT: a dual threshold incomplete LU factorization, Numer. Linear Algebra Appl., 1, 4, 387-402 (1994) · Zbl 0838.65026 |
| [42] | Scott, J. A.; Tůma, M., On signed incomplete Cholesky factorization preconditioners for saddle-point systems, SIAM J. Sci. Comput., 36, 6, A2984-A3010 (2014) · Zbl 1310.65036 |
| [43] | Eisenstat, S. C., Efficient implementation of a class of preconditioned conjugate gradient methods, SIAM J. Sci. Statist. Comput., 2, 1, 1-4 (1981) · Zbl 0474.65020 |
| [44] | Bunch, J. R.; Parlett, B. N., Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal., 8, 4, 639-655 (1971) · Zbl 0199.49802 |
| [45] | Bunch, J. R.; Kaufman, L., Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comp., 163-179 (1977) · Zbl 0355.65023 |
| [46] | Lipnikov, K.; Manzini, G.; Shashkov, M., Mimetic finite difference method, J. Comput. Phys., 257, 1163-1227 (2014) · Zbl 1352.65420 |
| [47] | Maros, I.; Mészáros, C., A repository of convex quadratic programming problems, Optim. Methods Softw., 11, 1-4, 671-681 (1999) · Zbl 0973.90520 |
| [48] | Davis, T. A.; Hu, Y., The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38, 1, 1-28 (2011) · Zbl 1365.65123 |
| [49] | Elman, H. C.; Ramage, A.; Silvester, D. J., Algorithm 866: IFISS, a MATLAB toolbox for modelling incompressible flow, ACM Trans. Math. Software, 33, 2, 1-18 (2007) · Zbl 1365.65326 |
| [50] | 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: Oxford University Press Oxford, UK · Zbl 1304.76002 |
| [51] | Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), SIAM · Zbl 1011.65010 |
| [52] | Fletcher, R., Practical Methods of Optimization (1987), John Wiley & Sons, Ltd. · Zbl 0905.65002 |
| [53] | Grief, C.; Schötzau, D., Preconditioners for the discretized time-harmonic Maxwell equations in mixed form, Numer. Linear Algebra Appl., 14, 4, 281-297 (2007) · Zbl 1199.78010 |
| [54] | Rommes, J.; Schilders, W. H.A., Efficient methods for large resistor networks, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 29, 28-39 (2010) |
| [55] | Elhay, S.; Simpson, A. R.; Deuerlein, J.; Alexander, B.; Schilders, W. H.A., Reformulate co-tree flows method competitive with the global gradient algorithm for solving water distribution system equations, J. Water Resour. Plan. Manage., 140, 12 (2014) |
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.
