For me, a classic problem in linear algebra that got me climbing down a rabbit hole of complex analysis, conformal mappings, and polynomials, was in trying to prove converge rate bounds and iteration bounds for Krylov subspace methods. At a high level, it asks one of the following questions:
- What is the fastest way of computing $A^{-1}b$, under the assumption that matrix-vector products $x\mapsto Ax$ are cheap to compute?
- What is the fastest way to minimize $f(x) = (x-z)^T A (x-z)$, under the assumption that the gradient $\nabla f(x) = A (x-z)$ is cheap to evaluate?
As such, it has sweeping applications from PDEs, to physics, to optimization, to data science, to machine learning, etc.
To explain, let us focus our attention on optimal $\ell_2$ Krylov methods like MINRES and GMRES. (The theory for CG is similar.) These methods can be shown to generate the solution to the following least-squares problem at their $k$-th iteration
$$\underset{x_k\in\mathbb{R}^n}{\text{minimize }} \|Ax_k-b\|$$
where the $k$-th iterate $x_k$ is constrained to the $k$-th Krylov subspace
$$\text{subject to } x_k \in \mathrm{span}\{b,Ab,A^2b,\ldots,A^{k-1}b\}.$$
Observe that $x_k=(c_0 + c_1 A + \cdots + c_{k-1}A^{k-1})b=p(A)b$, where $p(\cdot)$ is a polynomial of order $k-1$. Similarly, $\|Ax_k-b\|=\|q(A)b\|$, where $q(\cdot)$ is a polynomial of order $k$ satisfying $q(0)=-1$. So the least-squares problem from above for each fixed $k$ can be equivalently posed as a polynomial optimization problem with the same optimal objective
$$\text{minimize } \|q_k(A)b\|
\text{ subject to } q_k(0)=-1,\; q_k(\cdot) \text{ is an order-} k \text{ polynomial.}$$
In essence, I'm trying to approximate, in some optimal sense, the inverse map $z\mapsto z^{-1}$ by a finite-degree polynomial $p(z)$. I'm trying to approximate the linear solve written $A^{-1}x$ by a sequence of matrix-vector products $p(A)b$. In turn, how good I can approximate the inverse map for a particular matrix exactly describes how fast MINRES / GMRES will converge.
If $A=I$, then $A^{-1}=A$, so we just need a degree-1 polynomial. In this case, GMRES / MINRES will converge to the exact solution in a single iteration.
If $A=\mathrm{diag}(aI,bI)$, then we need at most a degree-2 polynomial (proof is an exercise). In this case, GMRES / MINRES will converge to the exact solution in two iterations.
For a general $A$, I can prove that I need at most a degree-$n$ polynomial, therefore MINRES / GMRES is guaranteed to converge to the exact solution in $n$ iterations. The trick is to pick $p(z)=\det(zI-A)$ as the characteristic polynomial of the matrix $A$, and use the Cayley-Hamilton theorem (a fundamental result in linear algebra and also abstract algebra) to say that $p(A)=0$.
The most interesting research directions in this area is actually to bound the number of iterations to an $\epsilon$-approximate solution, rather than the exact solution. In analyzing the convergence rates, you will end up trying to approximate regions on the complex plane using polynomials. There's a connection to conformal maps and Christoffel-Schwarz transforms. Also, there is the functional analysis aspect once you allow $A$ to be a linear operator (sort of like an infinite-dimensional matrix).
To learn more on this area, I would highly recommend starting with Greenbaum's book (which is easier to read) and moving on to Saad's book (which is more comprehensive).
@book{greenbaum1997iterative,
title={Iterative methods for solving linear systems},
author={Greenbaum, Anne},
volume={17},
year={1997},
publisher={Siam}
}
@book{saad2003iterative,
title={Iterative methods for sparse linear systems},
author={Saad, Yousef},
volume={82},
year={2003},
publisher={siam}
}
I would also recommend Lecture 32 onwards from Trefethen's book.
@book{trefethen1997numerical,
title={Numerical linear algebra},
author={Trefethen, Lloyd N and Bau III, David},
volume={50},
year={1997},
publisher={Siam}
}
(This answer was partially adapted from an old answer on MO)
