New Preconditioners for Nonsymmetric Saddle Point Systems with Singular Block

We investigate the solution of large linear systems of saddle point type with singular block by preconditioned iterative methods and consider two parameterized block triangular preconditioners used with Krylov subspace methods which have the attractive property of improved eigenvalue clustering with increased ill-conditioning of the block of the saddle point matrix, including the choice of the parameter. Meanwhile, we analyze the spectral characteristics of two preconditioners and give the optimal parameter in practice. Numerical experiments that validate the analysis are presented. 1. Introduction We study preconditioners for general nonsingular linear systems of the type Such systems arise in a large number of applications, for example, the (linearized) Navier-Stokes equations and other physical problems with conservation laws as well as constrained optimization problems [1–5]. As such systems are typically large and sparse, solution by iterative methods has been studied extensively [1, 5–16]. Much attention has focused on the Navier-Stokes problem; see, for example, [1, 2, 5, 17, 18]. The techniques for solving systems like (1) are so numerous that it is almost impossible to give an overview. In addition to the methods developed specifically for Navier-Stokes problems, existing techniques also include splitting schemes [2, 6, 12, 19, 20], constraint preconditioning [2, 20, 21], Uzawa-type algorithms [2, 12, 22], and (preconditioned) Krylov subspace methods based on (approximations to) the Schur complement [2, 16, 23]. We start with augmentation block triangular preconditioners for the general system (1); see Section 2 for our assumptions. When is nonsingular, results for the general system have been obtained before; for example, Murphy et al. [23, 24] propose the block diagonal Schur complement preconditioner and the block triangular Schur complement preconditioner as follows: If defined, it has been shown that the preconditioned matrices (cf. [24]) are diagonalizable and have only three distinct eigenvalues , and two distinct eigenvalues , , respectively. However, when is singular, it cannot be inverted and the Schur complement does not exist. For symmetric saddle point systems, that is, and is symmetric, one possible way of dealing with the systems is by augmentation, that is, by replacing with , where is an symmetric positive definite weight matrix [4, 7, 9, 14, 17, 18, 25–27]. Recently, for symmetric saddle point systems with block that has a high nullity, Greif and Sch？tzau [25, 26] studied the application of the following block diagonal