38 ms·
Surprises from numerical linear algebra (2010)
- gruseom 15y agoOk 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.
- dxbydt 15y agoHow 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/0822053314 http://www.amazon.com/Linear-Algebra-Cliffs-Quick-Review/dp/... Amazing writing, very succint & hacker-friendly.
- palebluedot 15y agoI 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-spring-2010/ 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=results_main&playnext=1&list=PLE7DDD91010BC51F8 http://www.youtube.com/watch?v=ZK3O402wf1c&feature=resul...
- achompas 15y agoThe course is taught by Gilbert Strang, who has written an excellent introductory textbook on the subject: http://www.amazon.com/Introduction-Linear-Algebra-Fourth-Gilbert/dp/0980232716/ http://www.amazon.com/Introduction-Linear-Algebra-Fourth-Gil...
- colanderman 15y agoStrang has another great book, Linear Algebra and its Applications: http://www.amazon.com/Linear-Algebra-Applications-Gilbert-Strang/dp/0030105676/ref=sr_1_2?ie=UTF8&qid=1315933580&sr=8-2 http://www.amazon.com/Linear-Algebra-Applications-Gilbert-St... Everything I know about linear algebra I learned from this book.
- seanharnett 15y agoSeconded. I'm an applied math PhD student (optimization) and I use linear algebra constantly. This book taught me everything.
- m0nastic 15y agoThirded. 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.
- cop359 15y agoA slightly more advance books which I love is: Matrix Analysis and Applied Linear Algebra by Carl Meyer. http://www.amazon.com/gp/product/0898714540 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
- lurker17 15y agojohndcook's post is about numerical linear algebra. The recommendations given here so far are for intro/abstract linear algebra texts.
- gruseom 15y agoCorrect. Though in my case I have to re-do Strang or the equivalent anyway. Been a long time.
- mturmon 15y agoFor 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.
- jparise 15y agoKhan Academy has a complete Linear Algebra section: http://www.khanacademy.org/#linear-algebra http://www.khanacademy.org/#linear-algebra
- brent 15y agoNumerical Linear Algebra by Trefethen and Bao is well regarded.
- tokenadult 15y agoAs the focus of the submitted article is on numerical methods, I'd recommend Hubbard's textbook http://matrixeditions.com/UnifiedApproach4th.html 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 15y agoI've read and would recommend Linear Algebra Done Right by Sheldon Axler. http://www.amazon.com/Linear-Algebra-Right-Sheldon-Axler/dp/0387982582/ 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 15y agoI've heard good things about this one, as well as _Linear Algebra for Everyone_. http://amzn.com/8847018382 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 15y agoWhile 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 15y agoAfter 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?p=F706B428FB7BD52C * http://www.youtube.com/view_play_list?gl=DE&hl=de&p=3A13781649466805 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 15y agoThe (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-19c6-49ed-9497-2ba8bfcfe5f6 http://see.stanford.edu/see/courseinfo.aspx?coll=17005383-19...
- tptacek 15y agoOk, Daniel. Linear algebra study group. Let's make something happen. (I just bought the Strang book mentioned downthread).
- gruseom 15y agoI'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 http://news.ycombinator.com/edit?id=2993321.
- tptacek 15y agoI 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.
- pkrumins 15y agoI 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/ http://www.catonmat.net/blog/mit-linear-algebra-part-one/
- thisrod 15y agoWow. No one has mentioned the gospel according to Golub: http://www.amazon.com/Computations-Hopkins-Studies-Mathematical-Sciences/dp/0801854148/ref=sr_1_1?ie=UTF8&qid=1315956173&sr=8-1 http://www.amazon.com/Computations-Hopkins-Studies-Mathemati... This is the "how we wrote Lapack" book.
- alxv 15y agoYes, Golub/van Loan is the bible. But Walkins's "Fundamentals of Matrix Computations" (http://www.amazon.com/o/asin/0470528338/ 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_equivalence http://en.wikipedia.org/wiki/Matrix_norm#Examples_of_norm_eq...
- brendano 15y agoI put together some free online resources for linear algebra: http://brenocon.com/blog/2011/03/poor-mans-linear-algebra-textbook/ 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_ 15y agoI 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/ http://joshua.smcvt.edu/linalg.html/
- dxbydt 15y agoOk, 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 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 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.
- trentonstrong 15y agoLinear 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 15y agoI remember taking linear algebra some time ago. I tweeted my one main takeaway from the class. http://goo.gl/gEu4y http://goo.gl/gEu4y
- chollida1 15y agohttps://twitter.com/#!/whatgoodisaroad/status/26337970149 https://twitter.com/#!/whatgoodisaroad/status/26337970149 The link the above minimized link goes to.
- zeratul 15y agoIt 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.
- mturmon 15y agolinpack and eispack are vestigial. They were folded into lapack, which is the "one true package" now (e.g., http://en.wikipedia.org/wiki/EISPACK 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 15y agoLinear 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.
- mturmon 15y agoI 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.]
- eru 15y agoDon't you still have to look out for ill-conditioned matrices?
- InclinedPlane 15y agoIf you use inverses then you can run into such problems, which is a good reason not to use them.
- mturmon 15y agoYes, 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 15y agoThe 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 15y agoSure. No surprises. All decades old stuff.
- Sniffnoy 15y agoHere I was expecting some actual surprising theorems.