Seven sins of numerical linear algebra

I wish there was a Missing Semester of Linear Algebra course to help people go from &quot;Okay I have a course or two in linear algebra, I know what span, vectors, basis and dimension mean, the formal definition of an inner product space, and I can do Gauss-Jordan elimination, determinants and eigenvalues for small matrices with paper and pencil&quot; to &quot;I have a 100x100 matrix of noisy data from sensors and this research paper I found tells me I can do some fantastic stuff if I compute such-and-such involving eigenvalues or inverses or whatnot. Or maybe I have a process with 1000 states where I know the probability objects move from state i to state j for each pair (i, j) and I want to find the steady state. How do I wrangle numpy into doing what I need?&quot;<p>MIT has a course called The Missing Semester of Your CS Education [1]. It tells you about practical stuff that you need to know but isn&#x27;t really taught in classes (shells, version control, build systems, package managers, VM&#x27;s).<p>There needs to be something similar for linear algebra, it seems like there&#x27;s a lot of folk knowledge and a big gap between what typical undergrad courses train you to do and what you encounter in actual practical problems.<p>(And don&#x27;t get me started on all the weird linear algebra stuff they have going on in e.g. quantum physics.)<p>[1] <a href="https:&#x2F;&#x2F;missing.csail.mit.edu&#x2F;about&#x2F;" rel="nofollow">https:&#x2F;&#x2F;missing.csail.mit.edu&#x2F;about&#x2F;</a>

Prof Higham has quite the list of papers on the finer points of numerical algorithms going back to his MSc in 1983:<p><a href="http:&#x2F;&#x2F;www.ma.man.ac.uk&#x2F;~higham&#x2F;papers&#x2F;bibbase.php" rel="nofollow">http:&#x2F;&#x2F;www.ma.man.ac.uk&#x2F;~higham&#x2F;papers&#x2F;bibbase.php</a><p>including a brief note on the comparing &quot;Top 10 Algorithms in Applied Mathematics&quot; between 2000 and 2016 that may interest some:<p><a href="https:&#x2F;&#x2F;nhigham.com&#x2F;2016&#x2F;03&#x2F;29&#x2F;the-top-10-algorithms-in-applied-mathematics&#x2F;" rel="nofollow">https:&#x2F;&#x2F;nhigham.com&#x2F;2016&#x2F;03&#x2F;29&#x2F;the-top-10-algorithms-in-appl...</a><p>It&#x27;d be nice to see some meat on the bones and a few ripping yarns about the <i>application</i> end of applied math techniques .. eg: forming an enhanced image from tens (or hundreds) of thousands of multichannel spectral samples using a sensitivity adjusted SVD, and then removing the most common expected background to highlight the anomalies.<p>It&#x27;s dry stuff in Linear Algebra, somewhat more exciting when searching for nuclear weapons in a forest or gold in a desert.

Re: the first sin, I was told to not invert matrices but never given a satisfying reason. So I wrote a blog post about it:<p><a href="http:&#x2F;&#x2F;gregorygundersen.com&#x2F;blog&#x2F;2020&#x2F;12&#x2F;09&#x2F;matrix-inversion&#x2F;" rel="nofollow">http:&#x2F;&#x2F;gregorygundersen.com&#x2F;blog&#x2F;2020&#x2F;12&#x2F;09&#x2F;matrix-inversion...</a>

Most people should pay extra attention to #7.<p>E.g. Goodfellow et al did even worse than this sin in the Deep Learning book when they claimed the condition number for a square (but not necessarily normal) matrix is defined in terms of eigenvalues. This is false, but nevertheless see 4.2 in <a href="https:&#x2F;&#x2F;www.deeplearningbook.org&#x2F;contents&#x2F;numerical.html" rel="nofollow">https:&#x2F;&#x2F;www.deeplearningbook.org&#x2F;contents&#x2F;numerical.html</a> . When I&#x27;ve raised this with people in real life, I typically get some reflexive response that it should be a useful approximation, but as this blog points out, that isn&#x27;t true either.

Also, please check other posts in Professor Nick Higham&#x27;s blog. Especially his wonderful and accessible &quot;What is ...&quot; series of articles [0]<p>[0] <a href="https:&#x2F;&#x2F;nhigham.com&#x2F;index-of-what-is-articles&#x2F;" rel="nofollow">https:&#x2F;&#x2F;nhigham.com&#x2F;index-of-what-is-articles&#x2F;</a>

Not sure I 100% agree with (2) forming A^TA. In many real-world use cases A^TA+choleksy is going to be considerably faster than QR on A, and come with few numerical consequences. Even in the numerically challenging cases, pivoted LDL^T on the saddle point system is still going to be faster than the suggested solution of doing QR on A. (Essentially no optimization solver I&#x27;ve ever seen uses QR).

Love the post. I&#x27;ll take this opportunity to link to a favorite classic linear algebra paper in a similar vein: &quot;Nineteen Dubious Ways to Compute the Exponential of a Matrix&quot; [1]<p>[1]: <a href="https:&#x2F;&#x2F;www.math.purdue.edu&#x2F;~yipn&#x2F;543&#x2F;matrixExp19-I.pdf" rel="nofollow">https:&#x2F;&#x2F;www.math.purdue.edu&#x2F;~yipn&#x2F;543&#x2F;matrixExp19-I.pdf</a>

Great list thank you. Unfortunately I commit 4 of these on a regular basis.

Numerical algorithms have always been a fascination of mine and I spent quite a bit of time studying them. Linear algebra has always seemed to provide some of the most rich content (followed by differential equations, imo). To me linear algebra was so dry when done on paper but suddenly a new world opened up when I could use computers.

I recommend Numerical Linear Algebra by Trefethen and Bau.<p>Thanks for this excellent link.

The PDFs for Higham&#x27;s &quot;What is&quot; series are available on Github: <a href="https:&#x2F;&#x2F;github.com&#x2F;higham&#x2F;what-is" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;higham&#x2F;what-is</a>

nit: in &quot;5. Not Exploiting Structure in the Matrix&quot;, the author says circulant matrices can be solved in O(n log_2 n) operations, where log_2 means &quot;base 2&quot; log. This notation is unnecessary since different bases of logs (as long as the bases are constant and independent of n) only differ in a constant factor, the _2 is insignificant in the big O notation, so it&#x27;s just O(n log n)

Learned a lot of these lessons when studying statistics as a non-coder trying to implement my own techniques and other peoples research.

Nice list. I would add<p>8. [edit: oops that&#x27;s already no 5] Not taking advantage of matrix structure (symmetric, sparse, banded, Toeplitz, ...)<p>9. Transposing a matrix (Like the inverse A^{-1}, the explicit transpose A^t is often not needed)

Per the first sin, is there any alternative for computing the view matrix from a camera matrix in 3d graphics? This is a case where inversion &quot;feels&quot; appropriate to me.

&gt; Indeed one would not solve the scalar (n = 1) system 7x = 21 by computing x = 7^-1 × 21 but rather would carry out a division x = 21 &#x2F; 7<p>I remember learning in algebra to solve this equation exactly the way he described and said we don&#x27;t use. You multiply both sides by 1 &#x2F; 7 which cancels the 7 on the left side, because 1 &#x2F; 7 is the inverse of 7.<p>Now I just implicitly divide both sides by 7, but I&#x27;m still solving the equation by using the inverse of 7...

I love this topic. Are there any industry fields or sub fields that make heavy use of this content?

What is a good resource to self-study numerical linear algebra?

fantastic post!