Stanford 50: State of the Art and Future Directions of Computational Mathematics and Numerical Computing


  • March 30, 2007
  • 11:00 am - 11:25 am

Block preconditioners for saddle point systems: a junction of linear algebra, constrained optimization, and PDEs

Chen Greif (University of British Columbia)

Saddle point linear systems are ubiquitous in science and engineering applications. The matrices associated with such systems are symmetric and indefinite, and have a 2x2 block structure with a zero block. These systems arise in constrained optimization, in variational formulation of PDEs, and in many other situations. In a large-scale setting it is desirable to take advantage of the block structure, and doing this requires knowing something about the underlying continuous problem and about the spectral structure of the operators involved.

In this talk we discuss solution techniques, addressing the question of which preconditioners should be used. We focus on an augmentation preconditioning technique in which the preconditioners are block diagonal with symmetric positive definite blocks and are based on augmented Lagrangian techniques. Interestingly, it is possible to show analytically that the more rank-deficient the (1,1) block of the original matrix is, the faster a preconditioned iterative scheme converges. Saddle point systems that arise in the time-harmonic Maxwell equations and interior-point methods in optimization are just two examples of situations where this feature of the preconditioner may come in handy. We discuss algebraic connections with other preconditioning approaches, and provide a few numerical examples.

Stanford University Home Page