Partitioned linear system

1 Background and Notation

1.1 Linear systems in matrix form

A linear system of equations in unknown vector \(x\in\mathbb{F}^n\) can be written compactly as \[ Ax=b, \] where \(A\in\mathbb{F}^{m\times n}\) is the coefficient matrix, \(b\in\mathbb{F}^{m}\) is the right-hand side, and \(\mathbb{F}\) is typically \(\mathbb{R}\) or \(\mathbb{C}\). The standard “monolithic” viewpoint treats all unknowns at once as components of a single vector.

1.2 Block partitioning of variables and equations

Partitioning groups components of the unknowns (and sometimes equations) into blocks. Instead of writing \(x\) as a flat vector, one writes it as \[ x=\begin{bmatrix}x_1\\ x_2\\ \vdots\end{bmatrix}, \] where each \(x_i\) collects a subset of variables. If the equations are partitioned similarly, \(Ax=b\) can be recast so that the coefficient matrix has submatrices (blocks) that reflect how variable groups interact.

1.3 Common matrix block conventions

A frequent convention is to partition both rows and columns so that the matrix takes a block form. For a \(2\times 2\) split, \[ A=\begin{bmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{bmatrix}, \quad x=\begin{bmatrix}x_1\\x_2\end{bmatrix}, \quad b=\begin{bmatrix}b_1\\b_2\end{bmatrix}. \] Here, \(A_{ij}\) connects the \(j\)-th variable block to the \(i\)-th equation block. Block dimensions are chosen so that multiplications are well-defined.

2 Block-Structured Formulation

2.1 General 2×2 partitioned systems

2.1.1 Partitioned matrix representation

Consider a system with variables split into two blocks: \[ \begin{bmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{bmatrix} \begin{bmatrix} x_1\\ x_2 \end{bmatrix} = \begin{bmatrix} b_1\\ b_2 \end{bmatrix}. \] Equivalently, this represents two coupled equations: \[ A_{11}x_1 + A_{12}x_2 = b_1,\qquad A_{21}x_1 + A_{22}x_2 = b_2. \]

2.1.2 Partitioned right-hand side vectors

The right-hand side is partitioned consistently with the row blocks: \[ b=\begin{bmatrix}b_1\\b_2\end{bmatrix}, \] so that each block equation corresponds to the relevant subset of constraints or measurements.

2.2 Extending to k×k block systems

For \(k\) variable blocks, the coefficient matrix becomes a \(k\times k\) block matrix: \[ A= \begin{bmatrix} A_{11} & A_{12} & \cdots & A_{1k}\\ A_{21} & A_{22} & \cdots & A_{2k}\\ \vdots & \vdots & \ddots & \vdots\\ A_{k1} & A_{k2} & \cdots & A_{kk} \end{bmatrix}, \quad x=\begin{bmatrix}x_1\\x_2\\ \vdots\\x_k\end{bmatrix}, \quad b=\begin{bmatrix}b_1\\b_2\\ \vdots\\b_k\end{bmatrix}. \] Block elimination and complement-based reductions generalize naturally by targeting one block (or set of blocks) for elimination.

2.3 Examples of natural partitioning

Block structure often arises when variables represent distinct physical or computational components. Typical examples include:

Multiple fields in coupled models (e.g., one block for each field).
Network-like systems where nodes are categorized.
Parameter blocks in model fitting where variables are grouped by source or type.
Time-stepping or domain decomposition settings where degrees of freedom are grouped spatially or temporally.

2.4 Assumptions (dimensions, compatibility, rank conditions)

To manipulate block systems algebraically, dimensions must satisfy:

\(A_{11}\) has size compatible with \(x_1\) and \(b_1\),
\(A_{22}\) has size compatible with \(x_2\) and \(b_2\),
and all products \(A_{ij}x_j\) align with the corresponding equation block.

Beyond dimensional compatibility, elimination steps may require invertibility (or at least solvability) of certain subblocks. When the system is singular or rank-deficient, block formulations still apply, but elimination may need generalized inverses or constrained solution concepts.

3 Solving Strategies via Block Elimination

3.1 Block Gaussian elimination overview

Block Gaussian elimination applies Gaussian elimination ideas at the level of submatrices. In a \(2\times 2\) system, the goal is often to remove one variable block (say \(x_2\)) to obtain a reduced system for the remaining variables (here \(x_1\)). This leads directly to Schur complements.

3.2 Direct elimination using submatrices

Starting from \[ A_{11}x_1 + A_{12}x_2 = b_1,\qquad A_{21}x_1 + A_{22}x_2 = b_2, \] one can solve the second equation for \(x_2\) when possible. If \(A_{22}\) is invertible, then \[ x_2 = A_{22}^{-1}(b_2 - A_{21}x_1). \] Substituting into the first equation yields a reduced equation involving only \(x_1\).

3.3 Forward/back substitution in block form

After obtaining a reduced system for \(x_1\), the eliminated block \(x_2\) is recovered by back-substitution (using the same relation as above). Conceptually:

Eliminate \(x_2\) to get a smaller system for \(x_1\).
Solve the smaller system.
Substitute to compute \(x_2\).

This mirrors ordinary elimination but respects the block structure.

3.4 When elimination is well-defined (invertibility requirements)

Simple elimination formulas require certain subblocks to be nonsingular. In the \(2\times 2\) case, invertibility of \(A_{22}\) is sufficient for eliminating \(x_2\). More generally, block elimination can be well-defined under conditions ensuring that the necessary linear subproblems have solutions and that the manipulations preserve equivalence of solution sets. When such conditions fail, one must switch to alternative strategies (e.g., rank-aware methods, regularization, or generalized inverses).

4 Schur Complements

4.1 Definition of the Schur complement (2×2 case)

For the partitioned system \[ \begin{bmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{bmatrix} \begin{bmatrix} x_1\\ x_2 \end{bmatrix} = \begin{bmatrix} b_1\\ b_2 \end{bmatrix}, \] assuming \(A_{22}\) is invertible, the Schur complement of \(A_{22}\) in \(A\) is \[ S = A_{11} - A_{12}A_{22}^{-1}A_{21}. \] Similarly, if \(A_{11}\) is invertible, one can define the Schur complement of \(A_{11}\) as \[ T = A_{22} - A_{21}A_{11}^{-1}A_{12}. \]

4.2 Eliminating one variable block

Using the earlier substitution \(x_2=A_{22}^{-1}(b_2-A_{21}x_1)\), the first block equation becomes \[ \left(A_{11} - A_{12}A_{22}^{-1}A_{21}\right)x_1 = b_1 - A_{12}A_{22}^{-1}b_2. \] Thus, elimination produces a reduced system \[ Sx_1 = b_1 - A_{12}A_{22}^{-1}b_2. \] After solving for \(x_1\), the formula for \(x_2\) recovers the eliminated block.

4.3 Equivalence of solutions

Under the stated invertibility assumption, solutions are in one-to-one correspondence between:

solutions \((x_1,x_2)\) of the full system, and
solutions \(x_1\) of the reduced system, with \(x_2\) determined uniquely by back-substitution.

Therefore, elimination via Schur complements preserves the essential solution content (not merely an approximation) when conditions hold.

4.4 Properties and interpretation

4.4.1 Invertibility relationships

Schur complements encode how the eliminated block influences solvability of the reduced problem. In particular, when appropriate inverses exist, the invertibility of the full block matrix can be related to the invertibility of \(A_{22}\) and of the Schur complement \(S\). Concretely, if \(A_{22}\) is invertible, then invertibility of the full matrix hinges on whether \(S\) is invertible as well (and vice versa in symmetric formulations).

4.5 Symmetric/Hermitian special cases

If the full matrix \(A\) is symmetric (real) or Hermitian (complex) and the blocks respect that structure (i.e., \(A_{21}=A_{12}^\ast\)), then Schur complements inherit symmetry/Hermiticity. This property is important because it often allows the reduced problem to retain favorable spectral characteristics and supports using structure-preserving numerical methods.

5 Algorithmic Considerations

5.1 Complexity and block size trade-offs

The computational cost of block methods depends on:

the size of each block,
the cost of solving subproblems involving submatrices (e.g., applying \(A_{22}^{-1}\)),
and the interaction pattern between blocks.

Large blocks can reduce the number of elimination steps but may increase the cost of subsolves. Conversely, very small blocks can increase overhead and diminish the benefit of treating coupled variables together.

5.2 Pivoting and numerical stability (high-level)

Practical elimination strategies must address numerical stability, especially when subblocks are nearly singular or poorly scaled. At a high level, pivoting determines which block or entries to eliminate first to limit growth of rounding errors. Block variants of pivoting can be more complex than scalar pivoting, but they are guided by similar goals: maintain stability while preserving efficiency.

5.3 Block preconditioning concepts

Block preconditioning improves iterative solver performance by using approximate inverses or simplified block factorizations. For instance, one may construct a preconditioner that mimics block elimination steps but uses cheaper approximations for Schur complements or the inverses of diagonal blocks. The objective is to reduce the condition number or cluster eigenvalues to accelerate convergence.

5.4 Iterative methods with partitioning

When direct elimination is costly, iterative solvers can exploit block structure in two ways:

the preconditioner is built using blocks,
the algorithm tracks residuals and updates in a manner compatible with partitioned variables.

This approach is common in large-scale settings where forming dense Schur complements is impractical.

5.4.1 Krylov methods with block structure

Krylov subspace methods (such as GMRES or conjugate-gradient variants) can benefit from block-aware preconditioning. Even if the system is treated abstractly as \(Ax=b\), block preconditioners can be designed to capture the coupling between variable groups, leading to faster convergence than purely generic preconditioners.

6 Special Cases and Variants

6.1 Diagonal block systems

If off-diagonal blocks vanish (e.g., \(A_{12}=A_{21}=0\)), the system decouples into independent subproblems for each variable block. In that setting, solving the full system is equivalent to solving each diagonal block equation separately, and Schur complements reduce to the remaining diagonal blocks.

6.2 Block triangular systems

If the block matrix is block triangular (for example, \(A_{21}=0\)), elimination becomes straightforward: one block can be solved first, and the other follows via back-substitution. This resembles forward/back substitution in triangular systems, but at block resolution.

6.3 Coupled vs decoupled partitions

A partition is “coupled” when off-diagonal blocks are nonzero, indicating interaction between variable groups. It is “nearly decoupled” when those off-diagonal blocks are small in a suitable sense, which can justify approximate elimination or iterative methods that treat coupling as a perturbation.

6.4 Singular and underdetermined partitioned systems

If the full system is singular, the reduced system may still be solvable but may not have a unique solution. Block elimination still provides structural insight: Schur complements and rank relations help determine which combinations of variables are constrained and which directions remain free. In such cases, the right solution concept might be:

finding a minimum-norm solution,
computing one solution among infinitely many,
or characterizing the nullspace.

6.5 Least-squares formulations for partitioned systems

When the system is overdetermined or inconsistent, one may solve a least-squares problem: \[

\min_x \\|Ax-b\\|_2^2.

\] Block partitioning can be carried into the normal equations or alternative least-squares formulations. Using blocks often allows reduced models that eliminate variable groups while preserving least-squares optimality under the chosen formulation.

7 Applications and Use Cases

7.1 Coupled physical models (general, non-controversial)

Many physical simulations involve multiple interacting components, producing systems where variables naturally split into groups (e.g., one block per field or component). Block elimination and Schur complement reductions help isolate the influence of one set of variables on another, enabling efficient solvers tailored to the coupling structure.

7.2 Constrained optimization via block KKT systems

Constrained optimization can produce saddle-point or KKT systems with block structure, where one block corresponds to primal variables and another to Lagrange multipliers. Eliminating multipliers via Schur complements yields reduced constrained formulations, while keeping the block structure supports preconditioning strategies for large problems.

7.3 Saddle-point problems (conceptual overview)

Saddle-point systems arise when an objective is optimized under constraints and when the discretized problem leads to indefinite matrices. Partitioning clarifies how constraints couple to variables. Although indefinite systems require careful numerical treatment, block methods provide a systematic framework for reducing dimensions and designing preconditioners.

7.4 Data and model partitioning in computation

In data-driven computation, variables may be grouped by feature sets, measurement channels, or model components. Partitioning then supports:

separate processing pipelines,
block updates in optimization,
and reduced models that eliminate nuisance variables or summarize effects through complements.

8 Worked Examples

8.1 A simple 2×2 block system (manual solve)

Consider \[ \begin{bmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{bmatrix} \begin{bmatrix} x_1\\ x_2 \end{bmatrix} = \begin{bmatrix} b_1\\ b_2 \end{bmatrix}, \] with \(A_{22}\) invertible. The second block equation is \[ A_{21}x_1 + A_{22}x_2 = b_2, \] so \[ x_2 = A_{22}^{-1}(b_2 - A_{21}x_1). \] Substitute into the first: \[ A_{11}x_1 + A_{12}A_{22}^{-1}(b_2 - A_{21}x_1)=b_1. \] Rearranging gives \[ \underbrace{\left(A_{11} - A_{12}A_{22}^{-1}A_{21}\right)}_{S}x_1 = b_1 - A_{12}A_{22}^{-1}b_2. \] Once \(x_1\) is obtained, compute \(x_2\) from the back-substitution formula.

8.2 Schur complement example

Let \[ A= \begin{bmatrix} 2 & 1 & 0\\ 1 & 3 & 1\\ 0 & 1 & 2 \end{bmatrix}, \quad x=\begin{bmatrix}x_1\\x_2\end{bmatrix}, \] where \(x_1\in\mathbb{R}^1\) and \(x_2\in\mathbb{R}^2\). Partition as \[ A_{11}=[2],\quad A_{12}=[1\ \ 0],\quad A_{21}=\begin{bmatrix}1\\0\end{bmatrix},\quad A_{22}=\begin{bmatrix}3 & 1\\1 & 2\end{bmatrix}. \] Compute the Schur complement \[ S = A_{11} - A_{12}A_{22}^{-1}A_{21}. \] After evaluating \(A_{22}^{-1}\) and the product \(A_{12}A_{22}^{-1}A_{21}\), one gets a scalar \(S\). Solving \(Sx_1=\tilde b\) (with \(\tilde b=b_1-A_{12}A_{22}^{-1}b_2\)) yields \(x_1\), and then \(x_2=A_{22}^{-1}(b_2-A_{21}x_1)\).

8.3 Multi-block example with structured elimination

For a \(k\)-block system, one may eliminate blocks sequentially. Suppose a \(3\times 3\) block system has a sparsity pattern where \(x_3\) couples only to \(x_2\) (but not directly to \(x_1\)). One can:

eliminate \(x_3\) to form an updated \(2\times 2\) block system in \((x_1,x_2)\),
then eliminate \(x_2\) to produce a final reduced system in \(x_1\).

Each elimination step uses a Schur complement computed from the currently active submatrix, reflecting how previously eliminated variables modify the remaining system.

9 Theory-Focused Results (Lightweight)

9.1 Conditions for unique solvability

Unique solvability of a partitioned linear system depends on properties of the full matrix \(A\) and, in reduced formulations, on corresponding properties of diagonal blocks and Schur complements. In the common \(2\times 2\) invertibility setting, uniqueness for the full system aligns with uniqueness for the Schur complement system together with invertibility of the eliminated block.

9.2 Rank and nullspace relationships under partitioning

Partitioning can reveal how the rank deficiency of the full matrix relates to ranks of blocks and Schur complements. While the exact relationships depend on assumptions (e.g., invertibility or consistent generalized inverses), the overarching principle is that eliminating variables transforms the problem into one whose nullspace and consistency can be described more transparently in the reduced space.

9.3 Consistency checks using block structure

Block structure enables sanity checks. For example, if a reduced system is inconsistent, then the original system cannot be consistent. Conversely, when the reduced equations satisfy compatibility requirements, one can often determine whether solutions exist and how many degrees of freedom remain. These checks are especially useful when diagnosing computational issues in large block-structured systems.

10 Terminology and Notation Reference

10.1 Common symbols for submatrices and complements

Standard notation uses \(A_{ij}\) for submatrices in a block partition. A Schur complement is commonly denoted by \(S\) (or \(T\) for the complementary block). Reduced right-hand sides are typically written using expressions derived from the elimination substitution, such as \(b_1 - A_{12}A_{22}^{-1}b_2\).

10.2 Typical naming conventions in literature

Terms frequently encountered include:

“block Gaussian elimination” for elimination performed with block algebra,
“Schur complement” for the reduced operator after eliminating a block,
“block elimination” or “block factorization” for structured decompositions,
and “block preconditioner” for iterative acceleration.

Partition: grouping variables and/or equations into blocks to expose structure.
Block elimination: removing one block of unknowns using submatrix operations.
Complement: an operator (typically the Schur complement) capturing the effect of eliminating variables.
Block preconditioning: constructing an iterative solver aid based on block structure.