Surprises from numerical linear algebra (2010)(johndcook.com)
johndcook.com
Surprises from numerical linear algebra (2010)
http://www.johndcook.com/blog/2010/01/20/ten-surprises-from-numerical-linear-algebra/
10 comments
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.
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.
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...
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...
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...
http://www.amazon.com/Introduction-Linear-Algebra-Fourth-Gil...
Strang has another great book, Linear Algebra and its Applications: http://www.amazon.com/Linear-Algebra-Applications-Gilbert-St... Everything I know about linear algebra I learned from this book.
A slightly more advance books which I love is:
Matrix Analysis and Applied Linear Algebra by Carl Meyer.
http://www.amazon.com/gp/product/0898714540
You can find a free PDF version online.
I like it more then Strang because it's a lot more concise, covers some more advanced topics and unlike Strang everything is said very accurately. I think Strang's rather hand-wavy way of explaining things starts faltering when he talks about more advance topics.
I would read Strang and listen to his lectures to get a good feel for Linear Algebra (to build up the intuition), and if you feel like you want more then pick up Meyer's book
You can find a free PDF version online.
I like it more then Strang because it's a lot more concise, covers some more advanced topics and unlike Strang everything is said very accurately. I think Strang's rather hand-wavy way of explaining things starts faltering when he talks about more advance topics.
I would read Strang and listen to his lectures to get a good feel for Linear Algebra (to build up the intuition), and if you feel like you want more then pick up Meyer's book
Seconded. I'm an applied math PhD student (optimization) and I use linear algebra constantly. This book taught me everything.
Thirded. We used an earlier edition at my school for Linear Algebra, and in spite of having a Professor who was retiring at the end of the class (complete with "I'm getting too old for this shit" demeanor), the book was approachable enough for us to get by.
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.
Amazing writing, very succint & hacker-friendly.
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...
Link to lectures and materials: http://see.stanford.edu/see/courseinfo.aspx?coll=17005383-19...
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.
* 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.
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.
For numerical aspects of linear algebra (and other subjects), I've found Numerical Recipes to be quite helpful.
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.
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.
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.
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.
johndcook's post is about numerical linear algebra.
The recommendations given here so far are for intro/abstract linear algebra texts.
The recommendations given here so far are for intro/abstract linear algebra texts.
Correct. Though in my case I have to re-do Strang or the equivalent anyway. Been a long time.
For the numerical stuff, it's hard to beat Golub and Van Loan.
Texts that emphasize coordinate-free approaches, like Linear Algebra Done Right, don't really get at the numeric computations issue.
Texts that emphasize coordinate-free approaches, like Linear Algebra Done Right, don't really get at the numeric computations issue.
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.
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.
Khan Academy has a complete Linear Algebra section: http://www.khanacademy.org/#linear-algebra
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.
http://www.amazon.com/Computations-Hopkins-Studies-Mathemati...
This is the "how we wrote Lapack" book.
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...
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...
Ok, Daniel. Linear algebra study group. Let's make something happen.
(I just bought the Strang book mentioned downthread).
(I just bought the Strang book mentioned downthread).
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.
Edit: Let's see if this works: http://news.ycombinator.com/edit?id=2993321.
I bought _Linear Algebra and its Applications_, but as I'm fond of reminding people on HN (come work for us!) my book budget is unbounded, so I'm happy to buy a different one.
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.
Everyone I talked to then recommended the Strang textbook, and also Stanford EE263, both already pointed out by other commenters here.
Numerical Linear Algebra by Trefethen and Bao is well regarded.
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/
Start here: http://www.catonmat.net/blog/mit-linear-algebra-part-one/
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.]
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.]
Don't you still have to look out for ill-conditioned matrices?
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
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.
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
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.
Thanks. Incidentally, this is the kind of stuff that I should still remember from university.
If you use inverses then you can run into such problems, which is a good reason not to use them.
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.
A person can do a lot of damage armed with a good grasp of linear algebra and fourier analysis.
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.
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.
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.
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.
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/
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.
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.
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.
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.
>> rather than applicable to your particular field.
No, I'm saying Hefferon is not applicable to any field. He eschews application in favor of formal theorem proving in vector spaces, in isolation of any real-life examples. That is great, but that is not the typical use case of anybody out there who actually uses linear algebra in industry, whether in computer graphics or portfolio theory or multivariate statistics or what have you.
No, I'm saying Hefferon is not applicable to any field. He eschews application in favor of formal theorem proving in vector spaces, in isolation of any real-life examples. That is great, but that is not the typical use case of anybody out there who actually uses linear algebra in industry, whether in computer graphics or portfolio theory or multivariate statistics or what have you.
Just to clarify for the crowd, portfolio theory, at least as far as its connection to linear algebra, is the mathematics of a covariance matrix. You are talking about different ways to decompose such a matrix. There are many ways and the justification for any of these methods goes beyond linear algebra and is really a special area of finance theory more than linear algebra.
Long before reading the book, I spent a lot of time with financial modeling of all kinds, but your complaint doesn't resonate with me at all. I went on to study machine learning and found the ideas in Hefferon laid a good foundation. It might be fair to point out that is not a cookbook and you don't use it to learn how to wrangle LAPACK, but I think it's over the top to say what you just did.
Long before reading the book, I spent a lot of time with financial modeling of all kinds, but your complaint doesn't resonate with me at all. I went on to study machine learning and found the ideas in Hefferon laid a good foundation. It might be fair to point out that is not a cookbook and you don't use it to learn how to wrangle LAPACK, but I think it's over the top to say what you just did.
Being "not the typical use case... in industry" doesn't make it bad. It just makes it a pure mathematics book. Formal theorem proving in vector spaces is the typical use case of a pure mathematician; this book is for them.
If you're looking to do application, use an applied book. Gilbert Strang's "Linear Algebra and its Applications" is quite good.
If you're looking to do application, use an applied book. Gilbert Strang's "Linear Algebra and its Applications" is quite good.
I'll second that. Strang's book is by far my favorite introductory math book. He addresses fundamentals quite well, and gives good treatment to applications such as linear programming and game theory.
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"?
"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...
And what you apparently call linear algebra is closer to multivariate statistics...
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.
But you learn a lot.
Here I was expecting some actual surprising theorems.
Sure. No surprises. All decades old stuff.
I remember taking linear algebra some time ago. I tweeted my one main takeaway from the class. http://goo.gl/gEu4y
https://twitter.com/#!/whatgoodisaroad/status/26337970149
The link the above minimized link goes to.
The link the above minimized link goes to.