Numerical solution of saddle point problems by block Gram-Schmidt orthogonalization

By Felicja Okulicka-Dlu.zewska, A. Smoktunowicz. 2013

948 citations recorded by the source corpus.

AbstractSaddle point problems arise in many important practical appli-cations. In this paper we propose and analyze some algorithms forsolving symmetric saddle point problems which are based upon theblock Gram-Schmidt method. In particular, we prove that the al-gorithm BCGS2 (Reorthogonalized Block Classical Gram-Schmidt)using Householder Q-R decomposition implemented in ﬂoating pointarithmetic is backward stable, under a mild assumption on the ma-trix M. This means that the computed vector ˜zis the exact solutionto a slightly perturbed linear system of equations Mz= f. Keywords: saddle point problem, block Q-R factorization, Householdertransformation, condition number, numerical stability. AMS Subj. Classiﬁcation: 15A12, 15A23, 15A60, 65H10. 1 Introduction We consider a symmetric saddle point problemMz = f ⇔A BB T −C xy=bc, (1)where A ∈ R m×m is symmetric positive deﬁnite (A > 0), C ∈ R n×n issymmetric semipositive deﬁnite (C ≥ 0), B ∈ R m×n has full column rank, ∗ Faculty of Mathematics and Information Science, Warsaw University of Tech-nology, Koszykowa 75, Warsaw, 00-662 Poland, e-mails: F.Okulicka@mini.pw.edu.pl,A.Smoktunowicz@mini.pw.edu.pl

Subfields: Atomic and Molecular Physics, and Optics, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/01e43d68b25cbcbb1f8acfeb6edb464e132eae19

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Atomic and Molecular Physics, and Optics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Regularized HSS iteration methods for saddle-point linear systems (2017, neutral): “These assumptions guarantee the existence and uniqueness of the solution of the saddle-point linear system (1.1); see [9].”
Local Saddle Point Optimization: A Curvature Exploitation Approach (2018, neutral): “(98) yields The choice of α = − λ/ (2 ρ x ) leads to further simpliﬁcation of the above bound: proof follows the argument from [5] Theorem 3.6.”
Generalized locally Toeplitz sequences : Theory and applications (2017, positive): “The resulting discretization matrices show up in saddle point form [9], and we will see the way to compute the asymptotic spectral distribution of their Schur complements using the theory of GLT sequences.”
ℋ︁‐LU factorization in preconditioners for augmented Lagrangian and grad‐div stabilized saddle point systems (2012, neutral): “A comprehensive survey [1] reviews many of the most promising solution methods with an emphasis on the iterative solution of these large, sparse, indefinite problems.”
MIMETIC FINITE DIFFERENCE APPROXIMATION OF FLOWS IN FRACTURED POROUS MEDIA (2016, positive): “We can exploit a well known result for saddle point problems [18].”
On iterative methods for the incompressible Stokes problem (2011, neutral): “As such, an iterative method that is developed for one type of saddle-point problem can often be applied in other areas as well [1].”
Interior point methods 25 years later (2012, neutral): “The reader interested in such approaches should consult an excellent survey of Benzi, Golub and Liesen [8].”
Dealing with Zero Flows in Solving the Nonlinear Equations for Water Distribution Systems (2011, neutral): “Theorem 1 (Benzi et al. 2005) Assume that the diagonal matrix F is non–negative definite and that A1 has full column rank.”
Efficient methods for large‐scale linear inversion using a geostatistical approach (2012, positive): “We use the block diagonal form [Benzi et al., 2005], which is commonly used in preconditioning matrices arising from saddle point problems.”
FAST ITERATIVE SOLVERS FOR CONVECTION-DIFFUSION CONTROL PROBLEMS ∗ (2013, neutral): “For an overview of properties and solution methods for such systems, we refer the reader to [3].”
Inexact Coordinate Descent: Complexity and Preconditioning (2013, neutral): “Finding good preconditioners is an active area of research; see for example [2, 10, 12].”
Linear Algebra and its Applications (2010, positive): “The Schur complement approach for solving saddle point systems, possibly in combination with CG, is well known (see e.g. [3]).”
Efficient augmented Lagrangian‐type preconditioning for the Oseen problem using Grad‐Div stabilization (2013, positive): “A good overview for solvers for saddle point problems is given in [8].”
A dimensional split preconditioner for Stokes and linearized Navier-Stokes equations (2011, neutral): “Much work has been done in developing efficient preconditioners for Krylov subspace methods applied to this problem; see, e.g., [4] [5] [8] [14] [15] [17] [18] [22].”
A Relaxed HSS Preconditioner for Saddle Point Problems from Meshfree Discretization (2013, neutral): “In [14], Benzi, Golub and Liesen discussed a selection of numerical methods and useful preconditioners for saddle point problems.”
INEXACT AND TRUNCATED PARAREAL-INTIME KRYLOV SUBSPACE METHODS FOR PARABOLIC OPTIMAL CONTROL PROBLEMS (2012, neutral): “Other approaches can be used as well (see, e.g., the survey [2]), however, here we focus on the reduced Hessian approach for two reasons.”
qpOASES: a parametric active-set algorithm for quadratic programming (2014, positive): “In qpOASES , for solving the saddle-point problem K W we implement a null-space method that can be expected to be numerically stable [6].”