ELo ELSEVIER Applied Mathematics and Computation 92(1998)49 58 The generalized Cholesky factorization method for saddle point problems Jinxi Zhao Department of Mathematics. Nanjing Unicersity. Nanjing 210 008. China Abstract Over the past 10 years. a variety of iterative methods for saddle point problems have been proposed. In this paper, we present a class of direct methods, the so-called gener- alized Cholesky factorization method. for solving linear systems arising from saddle point problems or discretization of the Stokes equations. Numerical results illustrate the efficiency of new methods given in this paper. 1998 Elsevier Science Inc. All rights reserved. Keywords: Saddle point problem: Generalized Cholesky factorization: Condition I: Generalized positive definite 1.Introduction Consider the linear system of equations )-( where A is symmetric positive definite, B of full row rank, and C symmetric positive semi-definite. Problems in this class arise frequently in the context of minimization of quadratic forms subject to linear constraints [8]. An important example arises from the numerical discretization of the Stokes equations. In particular, we are concerned with the discretization of Project supported by the Science Foundation of the State Education Commission of China and the "863" plan of China. 0096-3003/98/S19.00 1998 Elsevier Science Inc. All rights reserved. PII: S0096-3003(97)10040-6
50 .wf,.1th.(au.2190g)495N -A4-下pf. Vu -0).on 2. 4=0.oni2. (2) /P=0 where is a simply connected bounded domain in R.s==2 or 3.This system of the Stokes equations is a fundamental problem arising in computational fluid dynamics [4].Discretization of Eq.(2)by finite difference or finite element techniques leads to a linear system of equations of (1). In recent years.a variety of iterative algorithms have been devised for solving saddle point problems [1.3.4.6.7].In this paper.we have developed the generalized Cholesky factorization for four typical matrices arising in numerical optimization and computational fluid dynamics.Using the matrix factorization.we establish a class of direct methods for solving the corre- sponding linear system.New methods proposed in this paper remain main advantages of the classical Cholesky factorization for positive definite sys- tems.Hence the new method is referred to as the generalized Cholesky fac- torization method. In the following we always assume that matrices 4E R"".BR",and C"satisly the following condition. Condition I.A is symmetric positive definite.B is of full row rank and C is symmetrie semi-positive definite. 2.Symmetric indefinite case Let us assume that G is an (m+n)*(m+n)matrix and express it as 3 where A.B and C satisfy Condition I.It is easy to see that G is symmetric in- definite.The purpose of this section is based on the matrix factorization of G to give a new algorithm for solving the linear system (1). Firstly.we can prove the following theorem. Theorem 1.Ler G he an (m+*im+n)matrix expressed hy Ey.(3)and A.B.C sutisfr Condition I.Then there ahuvs exists the factorizution form G=B B (4)
J.Zhuo Appl.Muth.Comput.92 (1998)49.58 51 where andL1∈Rmwi8 low triangular,.Ln∈is low triangular..Lg∈R×m. Proof.Since 4 is symmetric positive definite,there always exists the Cholesky factorization A=LiLi where LE Ris nonsingular low triangular.Take La B(LI) (51 so that B=LgLi It follows that Le is full row rank because B is full row rank.Because C is sym- metric semi-positive definite,the matrix C+LaL must be symmetric positive definite.Hence we have the Cholesky factorization LuL=C+LaLg (6) also let 4=(2)=(日) Thus we have L1L=（ Remark 1.From Theorem 1.we set that matrices Li and L can be obtained conveniently as long as submatrices L.Lg and L have been computed.This is why our method is as fast as the classical Cholesky factorization for symmetric positive definite. We now discuss the realization of the generalized Cholesky factorization (4) of G.Let A=a∈Rmxm.L=l, Using the Cholesky factorization of A,the elements of L can be computed from
52 J.Zhao Appl.Math.Comput.92 (1998:49 58 i<i. i=j. (7) (au-∑laly)/ln.i>i月 i.j=1: Set LB=lg,=B(L)∈R"m Then all elements g;can be obtained from the following: (8) Since LyLT=C+LaLg let Lw=比∈E”“ be low triangular. Hence i<j. +- i=1 (c+∑gag-∑Crn)/r元 i>1: i=1:n.j=1:n (9) From the above discussion.the triangular factor of G can be obtained pro- vided that submatrices L.L and L have been formed.i.e.. 4=(位) and =(日)》 Using the factorization expression G=LiL
J.Zhuo Appl.Muth.Comput.92 (1998;49 58 53 it is easy to give the solution procedure of the linear system (1).Here we des- cribe the following. Algorithm 1. 1.Given 4=[d E R*",B=b,ER"and C=Ci E R"satisfying Con- dition I and given f∈Rm,g∈R”. 2.L==chol(A)or using expression (7). 3.Computing L8 =[g from LaL=B or using expression (8). 4.L =[v]chol(C+LgL)or using expression (9). 5.Computing from ,2)0)() 6.Obtained the final solution of the linear system (1)from (日))-) As a special case,if we have C=0 in the linear system (1).i.e.. -(8) then we can obtain the analogous factorization form. Using matrices La and La obtained in Theorem I,and Lg full row rank.we have the Cholesky factorization of LaL.i.e.. L,LX=LBL牙 where LER"*"is low triangular.Hence the following theorem is proved Theorem 2.Let A G- B B O and matrices A and B sutisfy Condition I.then there always exists a factorizution G:=L2Lg, (10) where