We consider saddle point problem and proposed an updating $ QR $ factorization technique for its solution. In this approach, instead of working with large system which may have a number of complexities such as memory consumption and storage requirements, we computed $ QR $ factorization of matrix $ A $ and then updated its upper triangular factor $ R $ by appending the matrices $ B $ and $ \left(\begin{array}{cc} B^T & -C \\ \end{array} \right) $ to obtain the solution. The $ QR $ factorization updated process consisting of updating of the upper triangular factor $ R $ and avoid the involvement of orthogonal factor $ Q $ due to its expensive storage requirements. This technique is also suited as an updating strategy when $ QR $ factorization of matrix $ A $ is available and it is required that matrices of similar nature be added to its right end or at bottom position for solving the modified problems. Numerical tests are carried out to demonstrate the applications and accuracy of the proposed approach.
Citation: Salman Zeb, Muhammad Yousaf, Aziz Khan, Bahaaeldin Abdalla, Thabet Abdeljawad. Updating $ QR $ factorization technique for solution of saddle point problems[J]. AIMS Mathematics, 2023, 8(1): 1672-1681. doi: 10.3934/math.2023085
We consider saddle point problem and proposed an updating $ QR $ factorization technique for its solution. In this approach, instead of working with large system which may have a number of complexities such as memory consumption and storage requirements, we computed $ QR $ factorization of matrix $ A $ and then updated its upper triangular factor $ R $ by appending the matrices $ B $ and $ \left(\begin{array}{cc} B^T & -C \\ \end{array} \right) $ to obtain the solution. The $ QR $ factorization updated process consisting of updating of the upper triangular factor $ R $ and avoid the involvement of orthogonal factor $ Q $ due to its expensive storage requirements. This technique is also suited as an updating strategy when $ QR $ factorization of matrix $ A $ is available and it is required that matrices of similar nature be added to its right end or at bottom position for solving the modified problems. Numerical tests are carried out to demonstrate the applications and accuracy of the proposed approach.
| [1] |
F. Brezzi, On the existence, uniqueness and approximation of saddle-point problems arising from lagrangian multipliers, ESAIM Math. Model. Num., 8 (1974), 129–151. https://doi.org/10.1051/m2an/197408R201291 doi: 10.1051/m2an/197408R201291
|
| [2] | F. Brezzi, M. Fortin, Mixed and hybrid finite element methods, New York: Springer, 1991. |
| [3] | A. Quarteroni, A. Valli, Numerical approximation of partial differential equations, Cham: Springer, 1994. |
| [4] |
M. Burger, W. Mühlhuber, Iterative regularization of parameter identification problems by sequential quadratic programming methods, Inverse Probl., 18 (2002), 943–969. https://doi.org/10.1088/0266-5611/18/4/301 doi: 10.1088/0266-5611/18/4/301
|
| [5] |
E. Haber, U. M. Ascher, Preconditioned all-at-once methods for large sparse parameter estimation problems, Inverse Probl., 17 (2001), 1847–1864. https://doi.org/10.1088/0266-5611/17/6/319 doi: 10.1088/0266-5611/17/6/319
|
| [6] | G. H. Golub, C. F. Van Loan, Matrix computations, Baltimore: Johns Hopkins University Press, 1996. |
| [7] | Å. Björck, Numerical methods for least squares problems, Philadelphia: SIAM, 1996. |
| [8] |
R. W. Freund, Model reduction methods based on krylov subspaces, Acta Numer., 12 (2003), 267–319. https://doi.org/10.1017/S0962492902000120 doi: 10.1017/S0962492902000120
|
| [9] |
T. Stykel, Balanced truncation model reduction for semidiscretized stokes equation, Linear Algebra Appl., 415 (2006), 262–289. https://doi.org/10.1016/j.laa.2004.01.015 doi: 10.1016/j.laa.2004.01.015
|
| [10] | R. Glowinski, Lectures on numerical methods for non-linear variational problems, Berlin, Heidelberg: Springer, 2008. |
| [11] | S. Turek, Efficient solvers for incompressible flow problems: An algorithmic and computational approache, Berlin, Heidelberg: Springer, 1999. |
| [12] | P. Wesseling, Principles of computational fluid dynamics, Berlin, Heidelberg: Springer, 2009. |
| [13] |
P. E. Gill, W. Murray, D. B. Ponceleón, M. A. Saunders, Preconditioners for indefinite systems arising in optimization, SIAM J. Matrix Anal. Appl., 13 (1992), 292–311. https://doi.org/10.1137/0613022 doi: 10.1137/0613022
|
| [14] | P. E. Gill, W. Murray, M. H. Wright, Practical optimization, New York: Academic Press, 1981. |
| [15] | S. J. Wright, Primal-dual interior-point methods, Philadelphia: SIAM, 1997. |
| [16] |
E. Haber, J. Modersitzki, Numerical methods for volume preserving image registration, Inverse Probl., 20 (2004), 1621–1638. https://doi.org/10.1088/0266-5611/20/5/018 doi: 10.1088/0266-5611/20/5/018
|
| [17] | E. Hall, Computer image processing and recognition, New York: Academic Press, 1979. |
| [18] | J. Modersitzki, Numerical methods for image registration, New York: Oxford University Press, 2003. https://doi.org/10.1093/acprof:oso/9780198528418.001.0001 |
| [19] | A. Battermann, M. Heinkenschloss, Preconditioners for Karush-Kuhn-Tucker matrices arising in the optimal control of distributed systems, In: Control and estimation of distributed parameter systems, Basel: Birkhäuser, 1998. https://doi.org/10.1007/978-3-0348-8849-3-2 |
| [20] | G. Biros, O. Ghattas, Parallel preconditioners for KKT systems arising in optimal control of viscous incompressible flows, In: Parallel computational fluid dynamics, Amsterdam: North Holland, 2000. https://doi.org/10.1016/B978-044482851-4/50017-7 |
| [21] | A. Battermann, E. W. Sachs, Block preconditioners for KKT systems in PDE-governed optimal control problems, In: Fast solution of discretized optimization problems, Basel: Birkhäuser, 2001. https://doi.org/10.1007/978-3-0348-8233-0-1 |
| [22] |
M. Benzi, G. H. Golub, J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), 1–137. https://doi.org/10.1017/S0962492904000212 doi: 10.1017/S0962492904000212
|
| [23] | J. M. Dłużewski, Nonlinear problems during consolidation process, In: Advanced numerical applications and plasticity in geomechanics, Vienna: Springer, 2001. https://doi.org/10.1007/978-3-7091-2578-6-4 |
| [24] | F. Okulicka, Solving coupled consolidation equations, In: Numerical methods and applications, Berlin, Heidelberg: Springer, 2007. https://doi.org/10.1007/978-3-540-70942-8-11 |
| [25] |
F. Okulicka, A. Smoktunowicz, Numerical solution of $2\times 2$ block linear systems by block Gram-Schmidt methods, Int. J. Comput. Math., 94 (2016), 1562–1573. https://doi.org/10.1080/00207160.2016.1226287 doi: 10.1080/00207160.2016.1226287
|
| [26] |
J. W. Daniel, W. B. Gragg, L. Kaufman, G. W. Stewart, Reorthogonalization and stable algorithms for updating the Gram-Schmidt $QR$ factorization, Math. Comput., 30 (1976), 772–795. https://doi.org/10.1090/S0025-5718-1976-0431641-8 doi: 10.1090/S0025-5718-1976-0431641-8
|
| [27] | P. E. Gill, G. H. Golub, W. Murray, M. A. Saunders, Methods for modifying matrix factorizations, Math. Comput., 28 (1974), 505–535. |
| [28] |
L. Reichel, W. B. Gragg, Algorithm 686: FORTRAN subroutines for updating the $QR$ decomposition, ACM T. Math. Software, 16 (1990), 369–377. https://doi.org/10.1145/98267.98291 doi: 10.1145/98267.98291
|
| [29] | S. Hammarling, C. Lucas, Updating the $QR$ factorization and the least squares problem, Univ. Manchester, 2008. |
| [30] | M. Yousaf, Repeated updating as a solution tool for linear least squares problems, Univ. Essex, 2010. |
| [31] |
R. Andrew, N. Dingle, Implementing $QR$ factorization updating algorithms on GPUs, Parallel Comput., 40 (2014), 161–172. https://doi.org/10.1016/j.parco.2014.03.003 doi: 10.1016/j.parco.2014.03.003
|
| [32] |
S. Zeb, M. Yousaf, Updating $QR$ factorization procedure for solution of linear least squares problem with equality constraints, J. Inequal. Appl., 2017 (2017), 281. https://doi.org/10.1186/s13660-017-1547-0 doi: 10.1186/s13660-017-1547-0
|
| [33] |
A. Kamitani, T. Takayama, A. Saitoh, H. Nakamura, Linear-system solver for EFG-type saddle-point problem without using QR decomposition, Plasma Fusion Res., 17 (2022), 2403014. https://doi.org/10.1585/pfr.17.2403014 doi: 10.1585/pfr.17.2403014
|
| [34] | F. O. Dluzewska, Applying the GSVD to the analysis of the augmented Lagrangian method for symmetric saddle point problem, In: Novel research aspects in mathematical and computer science, 2022. https://doi.org/10.9734/bpi/nramcs/v3/2072A |
| [35] |
J. Scott, M. Tuma, A null-space approach for large-scale symmetric saddle point systems with a small and non zero (2, 2) block, Numer. Algor., 90 (2022), 1639–1667. https://doi.org/10.1007/s11075-021-01245-z doi: 10.1007/s11075-021-01245-z
|
| [36] |
B. N. Parlett, Analysis of algorithms for reflections in bisectors, SIAM Rev., 13 (1971), 197–208. https://doi.org/10.1137/1013037 doi: 10.1137/1013037
|
Salman Zeb, Muhammad Yousaf, Aziz Khan, Bahaaeldin Abdalla, Thabet Abdeljawad. Updating $ QR $ factorization technique for solution of saddle point problems[J]. AIMS Mathematics, 2023, 8(1): 1672-1681. doi: 10.3934/math.2023085
DownLoad: