×

On normwise structured backward errors for the generalized saddle point systems. (English) Zbl 1369.65048

The author considers the problem of solving generalized saddle point systems. These are systems of linear equations whose coefficient matrix is in the form of a \(2 \times 2\) block matrix whose principal blocks are square and whose off-diagonal blocks are transposes of each other. When the trailing subblock is zero this is a saddle point system. If, in addition, the leading subblock is symmetric, one obtains what is often referred to as a Karush-Kuhn-Tucker system. The author obtains explicit and computable formula for the structured backward errors of the generalized saddle point system. Using numerical examples, it is shown that these expressions are handy in testing the stability of practical algorithms.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion

Software:

mctoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bunch, J.R.: The weak and strong stability of algorithms in numerical linear algebra. Linear Algebra Appl. 88(89), 49-66 (1987) · Zbl 0652.65032 · doi:10.1016/0024-3795(87)90102-9
[2] Botchev, M.A., Golub, G.H.: A class of nonsymmetric preconditioners for saddle point problems. SIAM J. Matrix Anal. Appl. 27, 1125-1149 (2006) · Zbl 1104.65038 · doi:10.1137/040618680
[3] Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1-137 (2005) · Zbl 1115.65034 · doi:10.1017/S0962492904000212
[4] Bao, G., Sun, W.: A fast algorithmfor the electromagnetic scatting from a large cavity. SIAM J. Sci. Comput. 27, 553-574 (2005) · Zbl 1089.78024 · doi:10.1137/S1064827503428539
[5] Chen, X.S., Li, W.: Structured backward errors for a class of linear systems. Math. Numer. Sinica. 29, 433-438 (2007). (in Chinese) · Zbl 1143.65340
[6] 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, 170-189 (2006) · Zbl 1104.65310 · doi:10.1137/05063427X
[7] Higham, N.J.: Accuracy and stability of numerical algorithms, 2nd edn. SIAM, Philadelphia (2002) · Zbl 1011.65010 · doi:10.1137/1.9780898718027
[8] Li, X.X., Liu, X.G.: Structured backward errors for structured KKT systems. J. Comput. Math. 22, 605-610 (2004) · Zbl 1140.65322
[9] Oettli, W., Prager, W.: Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Numer. Math. 6, 405-409 (1964) · Zbl 0133.08603 · doi:10.1007/BF01386090
[10] Rigal, J.L., Gaches, J.: On the compatibility of a given solution with data of a linear system. J. Assoc. Comput. Mach. 14, 543-548 (1967) · Zbl 0183.17704 · doi:10.1145/321406.321416
[11] Sun, J.G.: Backward perturbation analysis of certain characteristic subspaces. Numer. Math. 65, 357-382 (1993) · Zbl 0791.65023 · doi:10.1007/BF01385757
[12] Sun, J.G.: Structured backward errors for KKT systems. Linear Algebra Appl. 288, 75-88 (1999) · Zbl 0936.65070 · doi:10.1016/S0024-3795(98)10184-2
[13] Sun, J.G.: A note on backward errors for structured linear systems. Numer. Linear Algebra Appl. 12, 585-603 (2005) · Zbl 1164.65389 · doi:10.1002/nla.422
[14] Stewart, G.W., Sun, J.G.: Matrix perturbation theory. Academic Press, New York (1990) · Zbl 0706.65013
[15] Xu, W.W., Li, W.: New perturbation analysis for generalized saddle point systems. Calcolo 46, 25-36 (2009) · Zbl 1176.65056 · doi:10.1007/s10092-009-0157-8
[16] Xiang, H., Wei, Y.M.: On normwise structured backward errors for saddle point systems. SIAM J. Matrix Anal. Appl. 29, 838-849 (2007) · Zbl 1185.65074 · doi:10.1137/060663684
[17] Xiang, H., Wei, Y.M., Diao, H.A.: Perturbation analysis of generalized saddle point systems. Linear Algebra Appl. 419, 8-23 (2006) · Zbl 1109.65043 · doi:10.1016/j.laa.2006.03.041
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.