Abstract
We consider KKT systems of linear equations with a 2 × 2 block indefinite matrix whose (2, 2) block is zero. Such systems arise in many applications. Treating such matrices would encounter some intricacies, especially when its (1, 1) block, i.e., the stiffness matrix in term of computational mechanics, is rank-deficient. It is the rank-deficiency of the stiffness matrix that leads to the so-called rigid-displacement issue. This is believed to be one of the main reasons that many programmers would unwillingly give up the Lagrange multiplier method but select the penalty method. Based on the Sherman–Morrison formula and the conventional LDLT decomposition for symmetric positive definite matrices, a robust direct solution is proposed, which is amenable to the conventional finite element codes, competent for both nonsingular and singular stiffness matrices, and particularly suitable to parallel computation. As a paradigm, the application to the element-free Galerkin method (EFGM) with the moving least squares interpolation is illustrated.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York (1999)
Zienkiewicz, O.C., Taylor, R.L.: The Finite Element Method, vol. 1, 4th edition. McGraw-Hill, London (1989)
Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1–137 (2005)
Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipes in C++, 2nd edition. Cambridge University Press, Cambridge (2002)
Golub, G.H., Loan, C.F.V.: Matrix Computations, 2nd edition. The Johns Hopkins University Press, Baltimore (1989)
Duff, I.S., Reid, J.K.: Exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric linear systems. ACM Trans. Math. Softw. 22, 227–257 (1996)
Nicholson, D.W.: Non-iterative solution of finite element equations in incompressible solids. Acta Mech. 167, 189–195 (2004)
Simo, J.C., Laursen, T.A.: An augmented Lagrangian treatment of contact problems involving friction. Comput. Struct. 42, 97–116 (1992)
Zheng, H., Liu, D.F., Lee, C.F., Yue, Z.Q.: A sophisticated node-pair model for interface problems. Comput. Geotech. 31, 137–153 (2004)
Golub, G.H., Greif, C.: On solving block-structured indefinite linear systems. SIAM J. Sci. Comput. 24, 2076–2092 (2003)
Heath, M.T.: Scientific Computing, An Introductory Survey, 2nd edition. McGraw-Hill, London (2002)
Luis, M.H.: Alternating oblique projections for coupled linear systems, Numer. Algorithms 38, 285–303 (2005)
Wu, X., Silva, B.P.B., Yuan, J.Y.: Conjugate gradient method for rank deficient saddle point problems. Numer. Algorithms 35, 139–154 (2004)
Axelsson, O., Barker, V.A.: Finite Element Solution of Boundary Value Problems: Theory and Computation. Academic, Orlando, FL (1984)
Henderson, H.V., Searle, S.R.: On deriving the inverse of a sum of matrices. SIAM Rev. 23, 53–60 (1981)
Zheng, H., Liu, D.F., Lee, C.F., Tham, L.G.: Displacement-controlled method and its applications to material nonlinearity. Int. J. Numer. Anal. Methods Geomech. 29, 209–226 (2005)
Akgun, M.A., Garcelon, J.H., Haftka, R.T.: Fast exact linear and non-linear structural reanalysis and the Sherman–Morrison–Woodburg formulas. Int. J. Numer. Methods Eng. 50, 1587–1606 (2001)
Stewart G.W.: Modifying pivot elements in Gaussian elimination. Math. Comput. 28, 527–542 (1974)
Li, S.F., Liu, W.K.: Meshfree Particle Methods. Springer, New York (2004)
Atluri, S.N.: The Meshless Method (MLPG) for Domain & BIE Discretizations. Tech Science Press, Forsyth (2004)
Belytschko, T., Lu, Y.Y., Gu, L.: Element free Galerkin methods. Int. J. Numer. Methods Eng. 37, 229–256 (1994)
Zhu, T., Atluri, S.N.: A modified collocation method and a penalty formulation for enforcing the essential boundary conditions in the element free Galerkin method. Comput. Mech. 21, 211–222 (1998)
Author information
Authors and Affiliations
Corresponding author
Additional information
Funded by the National Natural Science Foundation of China (NSFC), Project no. 90510019.
Rights and permissions
About this article
Cite this article
Zheng, H., Li, J. A practical solution for KKT systems. Numer Algor 46, 105–119 (2007). https://doi.org/10.1007/s11075-007-9129-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-007-9129-8