Solving a Linear System

We begin with a deceptively simple question that every undergraduate student encounters in their first linear algebra course: solving the linear system

If the equation above is satisfied for some $x\in {\mathbb{R}}^n$ , then for any $y\in {\mathbb{R}}^n$ the following equivalence holds, and vice versa:

This reformulation, however, does not yet yield a computationally tractable problem: we are left with $n$ equations, and when $n$ is large, direct computation becomes prohibitively expensive.

Dimension Reduction

The remedy is conceptually straightforward: restrict the space in which $x$ and $y$ live to a much lower-dimensional subspace. Replacing $n$ by a far smaller $m$ renders the computation feasible while sacrificing only a controlled amount of precision.

Recall the Quantum Dissipative System post, where orthogonal projectors $\mathcal{P}$ and $\mathcal{Q}$ were introduced to decouple the system from its bath. The equation of motion was then studied, and bath-correlation together with the Caldeira–Leggett approximation were employed to refine the model via perturbation theory.

The present strategy is analogous, with one key difference: here we have precise control over the dimensions being discarded. We change the basis by defining

The linear system then reduces to

or in compact form:

where $\tilde{A}=W^{\mathrm{T}}AW\in {\mathbb{R}}^{m\times m}$ and $\tilde{b}=W^{\mathrm{T}}b\in {\mathbb{R}}^m$ .

The number of equations drops to $m\ll n$ . In practice, one solves this reduced system iteratively until the residual $\Vert \tilde{A}\hat{x}-\tilde{b}{\Vert }_{{\ell }^2({\mathbb{R}}^m)}$ falls below a prescribed tolerance.

Choosing $W$

Opening any numerical-methods textbook reveals a wealth of algorithms for solving linear systems — gradient descent, Lanczos, Krylov subspace methods, and so on. Despite their apparent diversity, all of these methods share a common thread: they approximate the exact solution by making different choices of $W$ .

Connection with PDE Weak Solution Theory

The passage from strong to weak form in PDE theory follows precisely the same logic. Consider, for instance the Poisson equation, $-\mathrm{\Delta }u=f$ : multiplying by a test function and integrating yields the weak formulation $\mathrm{\forall }v\in H_0^1(\mathrm{\Omega }),a(u,v)=\ell (v)$ . (The converse does not hold in general, since the weak formulation imposes no twice-differentiability on $u$ .) The parallel is not merely superficial: through the lens of functional analysis, a PDE can be viewed as a linear system of infinite dimension, making the analogy between the two settings both natural and rigorous.

To obtain a numerical solution, one applies the Ritz–Galerkin projection, discretizing the problem on a finite-dimensional subspace $V_h$ via an interpolation operator ${\mathcal{I}}_h$ — playing exactly the role that $W$ plays in the algebraic setting.