Surprises from numerical linear algebra (2010)

http://www.johndcook.com/blog/2010/01/20/ten-surprises-from-numerical-linear-algebra/

by th0ma5 • 15 years ago

155 49 15 years ago

gruseom3• 15 years ago

Ok HN, what's the best book for learning this stuff? My criteria are: rigorous is good, but so is fun. Bonus points for anything a hacker would appreciate, such as computational applications or exercises.

dxbydt3• 15 years ago

How much time do you have ? You can easily spend several years and get multiple PhDs in linear algebra, but if you only have half an hour to devote to this, I strongly suggest Leduc's Cliff Notes. http://www.amazon.com/Linear-Algebra-Cliffs-Quick-Review/dp/...

Amazing writing, very succint & hacker-friendly.

palebluedot• 15 years ago

I highly recommend the MIT 18.06 open course on linear algebra - the lectures are first rate. I've been going through this as a refresher, in prep for the Stanford machine learning class.

Link to the course: http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-...

Link to the YouTube videos of the lectures: http://www.youtube.com/watch?v=ZK3O402wf1c&feature=resul...

achompas• 15 years ago

The course is taught by Gilbert Strang, who has written an excellent introductory textbook on the subject:

http://www.amazon.com/Introduction-Linear-Algebra-Fourth-Gil...

lurker17• 15 years ago

johndcook's post is about numerical linear algebra.

The recommendations given here so far are for intro/abstract linear algebra texts.

gruseom3• 15 years ago

Correct. Though in my case I have to re-do Strang or the equivalent anyway. Been a long time.

jparise• 15 years ago

Khan Academy has a complete Linear Algebra section: http://www.khanacademy.org/#linear-algebra

brent• 15 years ago

Numerical Linear Algebra by Trefethen and Bao is well regarded.

tokenadult• 15 years ago

As the focus of the submitted article is on numerical methods, I'd recommend Hubbard's textbook

http://matrixeditions.com/UnifiedApproach4th.html

which is theoretical and linked to other subjects of higher math, but by no means slights practical problems or numerical methods.

nokcha• 15 years ago

I've read and would recommend Linear Algebra Done Right by Sheldon Axler. http://www.amazon.com/Linear-Algebra-Right-Sheldon-Axler/dp/...

For numerical aspects of linear algebra (and other subjects), I've found Numerical Recipes to be quite helpful.

phren0logy• 15 years ago

I've heard good things about this one, as well as _Linear Algebra for Everyone_. http://amzn.com/8847018382

From the book's intro:

>But, suppose we asked a professional mathematician to step back a bit from his habitual way of speaking and write in a more linear fashion? And suppose we even asked more, for example, that he make his writing lively? ... The purpose of this book is to furnish the reader with the first mathemat- ical tools needed to understand one of the pillars of modern mathematics, i.e. linear algebra. The text has been written by a mathematician who has tried to step out of his usual character in order to speak to a larger public. He has also taken up the challenge of trying to make accessible to everyone the first ideas and the first techniques of a body of knowledge that is fundamental to all of science and technology.

Silhouette• 15 years ago

While Numerical Recipes has certainly earned its place in the history of the genre, it is only fair to point out that it is very out-dated by now, and that the example code is neither particularly well-written (from a software development point of view) nor freely usable in your own projects.

As others have suggested, something like Golub and Van Loan is a better choice. The technical notes to go with the LAPACK library, and similar documents from those developing related software, are also likely to be of interest to anyone doing this stuff seriously.

muuh-gnu• 15 years ago

After the LA intro courses, see Strangs "Computational Science and Engineering":

* http://www.youtube.com/view_play_list?p=F706B428FB7BD52C

* http://www.youtube.com/view_play_list?gl=DE&hl=de&p=...

based on the book of the same name. This is one of "name 5 books you would take with you on a desert island" kind of books, a beautiful work of art.

robobenjie• 15 years ago

The (free, open) stanford class ee263: Linear Dynamical Systems is really good. It concentrated on how to take real problems and fit them into a form where a computer can solve them in what appears to be complete magic. Plus Stephen Boyd is a very entertaining lecturer. This article reminds me a lot of his asides.

Link to lectures and materials: http://see.stanford.edu/see/courseinfo.aspx?coll=17005383-19...

tptacek2• 15 years ago

Ok, Daniel. Linear algebra study group. Let's make something happen.

(I just bought the Strang book mentioned downthread).

gruseom3• 15 years ago

I'm in. Which of the Strangen? And what's a suitable forum for working out the details and proceeding? A Google group would probably be my go-to default but I'm open to alternatives.

Edit: Let's see if this works: http://news.ycombinator.com/edit?id=2993321.

pkrumins• 15 years ago

I am reviewing all MIT Linear Algebra lectures on my blog, including lecture notes and my comments.

Start here: http://www.catonmat.net/blog/mit-linear-algebra-part-one/

thisrod• 15 years ago

Wow. No one has mentioned the gospel according to Golub:

http://www.amazon.com/Computations-Hopkins-Studies-Mathemati...

This is the "how we wrote Lapack" book.

alxv• 15 years ago

Yes, Golub/van Loan is the bible. But Walkins's "Fundamentals of Matrix Computations" (http://www.amazon.com/o/asin/0470528338/) is much more accessible to self-learners.

For those who are just starting on this subject, I highly recommend that you rework the proofs for the bounds between the various matrix norms [1]. These bounds are the building blocks for most interesting analyses in matrix computations. And understanding these analyses are essential if you want to know which algorithm will work best for your problems.

[1] http://en.wikipedia.org/wiki/Matrix_norm#Examples_of_norm_eq...

brendano• 15 years ago

I put together some free online resources for linear algebra: http://brenocon.com/blog/2011/03/poor-mans-linear-algebra-te...

Everyone I talked to then recommended the Strang textbook, and also Stanford EE263, both already pointed out by other commenters here.

T_S_2• 15 years ago

I used Jim Hefferon's Linear Algebra to get back into the subject a few years ago. Great balance of rigorous and intuitive. Free book available here http://joshua.smcvt.edu/linalg.html/

dxbydt3• 15 years ago

Ok, so Hefferon was my textbook for 2 full semesters. Lots of problems with this book. Hefferon is an algebraist, so the computational aspect of linear algebra ie. the stuff you are most likely to use linalg for at your workplace, has been given short shrift. Instead, the author gives fullblown treatment to theorem proving in vector spaces. So you are spending a lot of time constructing isomorphisms between subspaces....that shit is neat for a math major, which I was, but now that I'm in the workplace, I find what the world calls "linear algebra" isn't what Hefferon cares about.

eg. One of the basics you must absolutely know, or so I've been told, is how to do a PCA, and why a PCA is not the same as regression. So if you've got multidimensional data, say data in 7 dimensions ( risk ratio, fico score, salary, age etc etc ), you want to know if you can reduce that whole set to say 1 dimension. ie. can you transform the original set of 7 variable vectors into a much smaller set of 1 variable vectors that captures 90% of the information in the original ? If so, how ? Turns out you construct a linear combination of correlated variables. Ok, but there's infinitely many combinations. So how ? Well, construct it in such a fashion that the variance of the combination is maximized. That component is called the Principal Component, and its the single most used technique to reduce dimensionality in the industry. So you've taken a 7-dimension space and nicely reduced it to a 1-dimension subspace with maximum variance that explains 90% of the original 7 dimension space. Its quite amazing actually. http://en.wikipedia.org/wiki/Principal_component_analysis

Similarly, there are a whole bunch of very common stuff you'd actually use linear algebra for in CG - translation, rotation in 3D, shear matrices and the like. Hefferon doesn't do those either.

In portfolio theory which is my bread and butter (http://en.wikipedia.org/wiki/Portfolio_theory ) almost everything I do is very properly linear algebra. But again, Hefferon doesn't offer any insight into how/why finding a vector with minimum variance can yield better returns in a vector space of portfolios.

starwed• 15 years ago

Your problem with the book seems to be that it is general, rather than applicable to your particular field.

Why on earth would expect that it would be? I took and enjoyed linear algebra using that text-- it didn't specifically address the QM I deal with as a physicist, but since the author can't predict each student's future, I'd hardly characterise that as a problem with the text!

If it was used as a course on portfolios, ok, bad choice -- but directed against a general linear algebra text, your criticism doesn't seem very valid.

pixcavator• 15 years ago

Did it ever occur to you that maybe you were able to handle PCA, CG, portfolio theory, etc because "Hefferon was my textbook for 2 full semesters"?

ginzasparrow• 15 years ago

"I find what the world calls "linear algebra" isn't what Hefferon cares about."?

And what you apparently call linear algebra is closer to multivariate statistics...

trentonstrong• 15 years ago

Linear algebra is one of my favorite subjects. Of all the math I used while still in physics, linear algebra ended up being the most practical for solving everyday problems in other fields.

A person can do a lot of damage armed with a good grasp of linear algebra and fourier analysis.

whatgoodisaroad• 15 years ago

I remember taking linear algebra some time ago. I tweeted my one main takeaway from the class. http://goo.gl/gEu4y

chollida1• 15 years ago

https://twitter.com/#!/whatgoodisaroad/status/26337970149

The link the above minimized link goes to.

zeratul• 15 years ago

It all depends how often you solve linear problems. If you are occasional user any package for any language will do.

If, however, you process tons of sparse, dense, categorical, or continuous data BE WARY: "lapack", "eispack", "linpack", "scalapack", and "lis" will give you different solutions. Occasionally, crash on some machines. Compilers, linkers, precision, and missing values matter here, too.

mturmon4• 15 years ago

linpack and eispack are vestigial. They were folded into lapack, which is the "one true package" now (e.g., http://en.wikipedia.org/wiki/EISPACK). The situation here is really not complicated.

scalapack is a different animal entirely. It's a parallel version of lapack (via MPI) so should not be expected to duplicate lapack results because partitioned algorithms will be used. But if you're using scalapack, you know that already.

gamble• 15 years ago

Linear algebra is the foundation of modern engineering. Before computers, the only mathematically tractable problems were those that could be reduced to linear problems. With computers, we can take on those formerly intractable problems by reducing them to massive systems of linear equations. Literally everything around you in daily life is the product of linear algebra.

mturmon4• 15 years ago

I thought the OP would reference the fact that errors in solving a linear system don't combine and magnify to produce unusable results beyond say a 10x10 system.

At the outset of numerical linear algebra, say in the 1940s [until 1948], it was not known whether errors would blow up or not. [best bound was 4^n where n is matrix order]

Turned out they did not (if you do things remotely right) but even von Neumann [in a 1947 paper, with others] was surprised that large (say 20x20, at that time) linear systems could be solved accurately.

[edits in braces: This history, and more, is in www.maths.manchester.ac.uk/~higham/talks/twge96.ps.gz ; Higham wrote probably the best and most comprehensive up-to-date book on the accuracy of numerical linear algebra.]

eru2• 15 years ago

Don't you still have to look out for ill-conditioned matrices?

InclinedPlane• 15 years ago

If you use inverses then you can run into such problems, which is a good reason not to use them.

mturmon4• 15 years ago

Yes, in some sense (see below) you do care about A.

But back then, everyone was worried even about well-conditioned systems. As of the mid 1940s the best error bound on cumulative roundoff error was 4^n where n is matrix order. That 4^n would be a multiplier on top of condition number (which at the time had not been formalized, it was Turing who did that).

Anyway, the dependence on matrix size turned out to be order n^2, and in practice more like O(n).

* * *

Also, the bounds on solving

  A x = b

for x, knowing b and A, work differently than solving for the inverse of A.

Sometimes for a given A and b, you can compute x above quite accurately, but you can't compute inv(A) accurately and multiply by b to get x. It depends on the how the "difficult directions" in A interact with b. This is one reason numerical analysts always ask, "Do you really need to invert A?"

Because of this, the actual condition number of A (i.e., the norm of A times that of inv(A)) does not enter into the bounds on solving A x = b. The bounds depend on a different norm.

In fact, there are several forms of the error bound -- known as backward and forward errors -- depending on what you need.

* * *

Incidentally, this is the kind of stuff that's covered in Golub and Van Loan, or in Trefethen and Bao, but not in a standard Abstract Linear Algebra book. For instance, Strang's book spends only one chapter on numerical linear algebra.

cheez• 15 years ago

The biggest surprise for me was never having to compute the inverse. I never saw such gymnastics to avoid computing things like I saw people avoiding computing the inverse of a matrix (for obvious reasons.) It's really amazing to work in the numerical computing field for a while. You leave it though because you can't stand the code.

But you learn a lot.

NY_Entrepreneur• 15 years ago

Sure. No surprises. All decades old stuff.

Sniffnoy• 15 years ago

Here I was expecting some actual surprising theorems.

Surprises from numerical linear algebra (2010)

Related Stories