Hacker News Reader

> 2. Personally, though, I find the topic of numerical stability to be a little bit depressing, since it focuses on all the ways computers don't work!

Maybe a way to more positively reformulate this would be: There is no a priori reason to assume that floating point numbers are well behaved. The fact that we were able to come up with a structure so that it approximates real numbers adequately, that arithmetic operations on it are fast (which they aren't for infinite precision) and that, if we design the algorithms correctly, errors are well-behaved, is an astonishing feat of engineering.

Computers work perfectly fine. Engineering was done for a long time with slide rules to avoid the tedium of looking up values in a book and grinding out results by hand or adding machine. Using them correctly requires knowing their limitations just as knowing the limitations of a computer is important. They aren't magic oracles that always give correct answers.

> To take a more positive view, a huge fraction of the algorithms in an undergraduate CS course -- from finite automata to parsing to relational algebra to graph traversals -- can be understood as basically doing linear algebra using modules over different semirings (rather than just the reals). Eg, for all-pairs shortest paths, the Floyd-Warshall algorithm is doing an LU decomposition, and Kleene's algorithm is doing Gauss-Jordan.

The blew my mind! I loved these undergrad and grad courses but never realized they are connected. Could you please forward me to few books or resources that go over these relationships?

https://www.semanticscholar.org/paper/Fun-with-semirings%3A-...

I really agree with your comments; especially number 1. Often I can't use some black box implementation of an solver (or other algorithm for that matter) without some modifications. Numerical stability is a big one but also just performance. Sometimes the mathematically correct way of doing something is not always the best in practice. Short cuts and approximations can provide huge benefits. It is difficult to make those modifications without understanding the inner workings of the original method.

One example is that GJ stops being generally efficient in arbitrary precision settings. Many people will never have to deal with this, but if you are doing cryptography, it matters.

For example, while you can use GJ to calculate the determinant of a matrix, this can easily become exponential, and for integer matrices (or generally for matrices over division rings), there is an alternative method (the Bareiss algorithm) that is actually efficient.