How/Why are linear systems so crucial to computer science?

Question

I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network flows, edge/vertex cover, travelling salesman etc.) I know that some of them are NP-hard, but the point being that they can be 'framed as a linear program' if not solved optimally.

That got me thinking: We've always been taught systems of linear equations, linear algebra all throughout school/college. And seeing the power of LPs for expressing various algorithms it's kinda fascinating.

Question: Although we have non-linear systems prevalent all around us how/why are linear systems so crucial to computer science? I do understand that they help simplify the understanding and are computationally tractable most of the times but is that it? How good is this 'approximation'? Are we over-simplifying and are the results still meaningful in practice? Or is it just 'nature' i.e. the problems that are the most fascinating are indeed simply linear?

Would it be safe to safe that 'linear algebra/equations/programming' are of the corner stones of CS? If not then what would be a good contradiction? How often do we deal with non-linear stuff (I don't necessarily mean theoretically but also from a 'solveability' standpoint i.e. just saying it's NP doesn't cut it; there should be a good approximation to the problem and would it land up being linear?)

Answer 1

The premise of the question is a little flawed: there are many who would argue that quadratics are the real "boundary" for tractability and modelling, since least-squares problems are almost as 'easy' as linear problems. There are others who'd argue that convexity (or even submodularity in certain cases) is the boundary for tractability.

Perhaps what is more relevant is "why do linear systems admit tractable solutions ?" which is not exactly what you asked, but is related. One perspective on this is composability. Since the defining property of a linear system is that $f(x + y) = f(x) + f(y)$, this imparts a kind of "memorylessness" to the system. To build up a solution to a problem I can focus on individual pieces and combine them with no penalty. Indeed, the premise of most algorithms for flow is precisely that.

This memorylessness imparts efficiency: I can break things into pieces, or work iteratively, and I don't lose by virtue of doing so. I can still make bad decisions (c.f. greedy algorithms) but the act of splitting things up itself doesn't hurt me.

This is one reason why linearity has such power. There are probably many others.

Answer 2

"Although we have non-linear systems prevalent all around us how/why are linear systems so crucial to computer science?"

Here is a partial answer in my mind: I think it is because nature is abound with objects/phenomena - representable by functions which albeit being nonlinear on their operands, are actually members of linear spaces. The wave functions in a Hilbert space, the components in a fourier spectrum, polynomial rings, stochastic processes - they all behave in that fashion. Even very general definitions of curved spaces are built out of composing small charts of flat spaces ( manifolds, Riemann surfaces, .. ). Moreover, nature is full of symmetries and studying symmetries invariably gets into study of linear operators (representation theory, in my mind, is creeping into many areas of computer science ever so ubiquitously).

These are in addition to the cases where the operators themselves are linear in nature.

A large fraction of problems for which we need computer programs, arise either directly as, or are abstracted from, naturally occuring phenomena. Perhaps studying/solving linear systems shouldn't be a great deal of surprise, after all?

Answer 3

I think all answers here are pretty good and linear systems admitting tractable solutions is definitely a big factor. I also like Arnab's answer about the ubiquity of linear spaces. But I also feel the need to point out that the instinct to ask this question is certainly not misplaced. Since the question employed some physical intuition, I think some physics context might be useful to illustrate why this is actually a really good question and why there's a slight caveat to the answers.

It is after all true that one of the big reasons why we think quantum mechanics is incomplete, is precisely because the Schrödinger equation, which governs quantum dynamics, is linear. Linear systems do not admit chaos, non-linear systems do. So it would seem that a purely quantum mechanical universe is one that is void of chaos, which doesn't correspond to our universe (quantum chaos is an open question in physics). This has implications for the question of whether quantum computers can be hoped to truly simulate as much as some hope them to, since quantum computers can be thought of as efficient in simulating nature because we don't have to simulate the "quantumness" (this is a bit of an oversimplification, but true to a certain extent).

Even if we look at machine learning, it seems to be the case that non-linear neural nets are needed to be particularly good at learning. Linear systems simply don't do as well here.

So while most of our universe seems perfectly well described by approximations of linearity, it may just very well be that we're missing out on some structure by not being better at computing non-linear systems.