10
$\begingroup$

So I've found some interesting linear algebraic research areas that's both pure-ish, with a numerical bent to it, too -- e.g. inverse eigenvalue problems have both interesting theoretical and computational aspects, spectral graph theory seems pretty cool (found through Yale's applied math course description ...), combinatorics, and representation theory.

This excites me much more than, say, doing linear algebraic research that aims to solve differential equations, which I've been doing a whole lot of, in our research lab (and have been enjoying).

Essentially, I don't feel competitive or motivated in the long-term, when compared to students of physics, bio, and engineering -- all of whom have way more scientific domain expertise than I do, since I'm a mathematics student by training.

How could I find a "good" linear algebraic problem for research that's pure-ish, while at the same time also having a nice computational aspect to it? Anything from geometry? Functional analysis?

By "good", I mean a problem that's tractable, yet interesting enough that many researchers are working on such a problem, and so the opportunity for collaboration and / or funding exists.

Where can I start? I could email some profs. that I know, and also read papers.

$\endgroup$
  • 1
    $\begingroup$ Could you clarify what you mean by pure-ish? Something outside applied math? AI / deep learning / machine learning is hot right now and involves linear algebra. $\endgroup$ – njuffa Dec 21 '19 at 10:33
  • $\begingroup$ @njuffa for instance, involving other mathematics, say, graph theory or geometry? But not so much the sciences / not multidisciplinary, e.g. not physics-based research (the work could land up being useful to science and engineering but I don't want that to be a primary aim in my work) ... $\endgroup$ – Samantha Dec 21 '19 at 16:54
10
$\begingroup$

Randomized linear algebra might be something you'd like. It has direct applications in data analysis and is related to several branches of Mathematics such as Geometry (see the Johnson-Lindenstrauss lemma) and, of course, Probability. A starting point would be https://cacm.acm.org/magazines/2016/6/202647-randnla/abstract and the survey https://epubs.siam.org/doi/abs/10.1137/090771806

You might also want to keep in mind that there is a strong link between Spectral Graph Theory and Differential Geometry (via Spectral Geometry). You can learn more about this via Fan Chung's work.

A natural connection between Linear Algebra and Functional Analysis would be in the discretizations involved in the Finite Element Method. More generally, you could look into applications in Computational Harmonic Analysis.

As a final suggestion, you could browse through the issues of the journal Linear algebra and its Applications.

$\endgroup$
  • 2
    $\begingroup$ Interesting thanks 👍 any linear algebraic directions with a more geometric flavor rather than algorithmic? Is there any use of nilpotent operators or the Jordan canonical form after a grad level linear algebra course? That's what I wonder a lot about, tbh ... $\endgroup$ – Samantha Dec 20 '19 at 19:34
  • $\begingroup$ The only applications I can think of right now are in ODEs/Dynamical Systems, which you said were not of interest to you. $\endgroup$ – Juan M. Bello-Rivas Dec 20 '19 at 20:33
  • $\begingroup$ Oo I'd love to hear more, actually, re: ODEs and dynamical systems - care to share? Thanks 👍 $\endgroup$ – Samantha Dec 20 '19 at 20:41
  • $\begingroup$ I think a discretization of the transient component of the phase flow of a dynamical system will fit the bill. Consider the discretization of the heat equation with Dirichlet boundary conditions $x^{n} = A^n x^0$, for $n$ sufficiently large (i.e., for long times), the solution $x^n$ will be (almost) zero regardless of the choice of the initial vector $x^0$, which implies that $A^n \approx 0$. $\endgroup$ – Juan M. Bello-Rivas Dec 20 '19 at 21:00
  • 1
    $\begingroup$ By the way, I've expanded my answer above with additional links to other areas of Mathematics. I hope you'll find some of those appealing. $\endgroup$ – Juan M. Bello-Rivas Dec 20 '19 at 21:03
6
$\begingroup$

Here's another interesting connection: There is a research area that looks into the complexity of computing matrix-matrix products from a geometric perspective. It's a totally bizarre connection, but quite fruitful. I'd start by looking at the papers by J. M. Landsberg at Texas A&M.

$\endgroup$
3
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.