Classification of Double Saddle-Point Systems

Technical Summary: Classification of Double Saddle-Point Systems

Problem Statement
Double (or twofold) saddle-point systems are linear systems characterized by $3 \times 3$ block matrices. While these systems have appeared in diverse applications since the early 2000s—ranging from liquid crystal modeling to PDE-constrained optimization and multiphysics problems like poroelasticity—the literature lacks a unified, formal definition and systematic characterization. Existing terminology has been applied to systems with varying algebraic structures and symmetry levels, creating a gap in the coherent classification of these matrices. This paper addresses that gap by providing a clear classification framework, analyzing their structural and spectral properties, and discussing preconditioning strategies within a general mathematical setting.

Methodology and Classification Framework
The authors define a broad class of symmetric nonsingular $3 \times 3$ block matrices, denoted as the family $\mathcal{S}_3$. This family is divided into two canonical forms, which cannot be converted into one another via simple symmetric permutations due to dimension and definiteness constraints:

1. Block-Arrow Form ($A$):
   $$A = \begin{bmatrix} A_1 & B_1^T & B_2^T \\ B_1 & -A_2 & 0 \\ B_2 & 0 & -A_3 \end{bmatrix}$$
2. Block-Tridiagonal Form ($T$):
   $$T = \begin{bmatrix} A_1 & B_1^T & 0 \\ B_1 & -A_2 & B_2^T \\ 0 & B_2 & A_3 \end{bmatrix}$$

The classification relies on specific conditions:

• [C1] The leading block $A_1$ is symmetric positive definite (SPD) and at least as large as the other diagonal blocks.
• [C2] The diagonal blocks $A_2$ and $A_3$ are symmetric positive semidefinite (SPSD).
• [C3] The off-diagonal coupling blocks $B_1$ and $B_2$ have full rank or small nullity.

The paper unifies these forms by interpreting them through the lens of constrained optimization. The block-arrow form arises from minimizing a quadratic objective subject to two sets of equality constraints, while the block-tridiagonal form arises from minimizing a sum of two quadratic objectives subject to a single coupling constraint. This perspective connects double saddle-point systems to classical saddle-point systems and their generalizations (multiple saddle-point systems).

Key Results and Contributions

• Invertibility and Dimension Constraints: The paper establishes necessary and sufficient conditions for the invertibility of matrices in $\mathcal{S}_3$. Crucially, it derives dimension restrictions: for the block-arrow form $A$ (when $A_2=A_3=0$), invertibility requires $n_1 \ge n_2 + n_3$; for the block-tridiagonal form $T$ (when $A_3=0$), it requires $n_1 \ge n_2 \ge n_3$.
• Block-LDL Factorizations: The authors present explicit block-LDL decompositions for both forms. These factorizations reveal the Schur complements ($S_{a,1}, S_{a,2}$ for $A$ and $S_{t,1}, S_{t,2}$ for $T$) and establish their definiteness properties. For instance, $S_{a,2}$ is shown to be positive semidefinite and positive definite if and only if $A$ is nonsingular.
• Spectral Properties:
  • Inertia: The paper determines the inertia of nonsingular matrices in $\mathcal{S}_3$. A nonsingular block-arrow matrix $A$ has $n_1$ positive and $n_2+n_3$ negative eigenvalues. A nonsingular block-tridiagonal matrix $T$ has $n_1+n_3$ positive and $n_2$ negative eigenvalues.
  • Eigenvalue Bounds: Using energy estimates and the "R-matrix method," the paper derives upper and lower bounds for the eigenvalues of both forms. These bounds are expressed in terms of the eigenvalues of the diagonal blocks ($A_i$) and the singular values of the off-diagonal blocks ($B_i$). For the block-arrow form, the bounds are derived via cubic polynomials related to reduced matrices.
• Preconditioning: The structural properties are leveraged to analyze Schur complement-based block preconditioners.
  • For the block-arrow form, the paper analyzes block-diagonal and block-triangular preconditioners. It shows that while block-diagonal preconditioners yield specific eigenvalue clusters (including the Golden Ratio $\frac{1\pm\sqrt{5}}{2}$), block-triangular preconditioners based on exact LDL factors result in a minimal polynomial of $(\lambda-1)^3$, though they are computationally expensive due to fill-in.
  • For the block-tridiagonal form, the block-diagonal Schur complement preconditioner is shown to yield constant spectral bounds even when regularization terms ($A_2, A_3$) are non-zero. The paper details the specific eigenvalue distributions (including roots of cubic polynomials like $\lambda^3 - \lambda^2 - 2\lambda + 1$) for various cases of $A_2$ and $A_3$.
  • The discussion also briefly covers alternative approaches such as operator preconditioning and shift-splitting methods.

Significance and Scope
The paper's primary contribution is the provision of a "clear and coherent classification" of double saddle-point systems, moving beyond the disparate terminology found in application-specific literature. By establishing a unified framework, the authors demonstrate that these systems share common algebraic and spectral properties that underpin existing numerical solvers.

The authors explicitly state that their discussion remains within a general framework rather than being tailored to specific applications. They acknowledge that while many double saddle-point systems arise from constrained optimization, others (particularly from PDE discretizations) do not; however, their algebraic structure admits an interpretation equivalent to optimality conditions. The work serves as a foundational reference for understanding the invertibility, spectral behavior, and preconditioning of these systems, setting the stage for future research into properties intrinsic to double and multiple saddle-point systems that are not merely inherited from classical saddle-point theory.