I have a bit of an odd background. I have a fair bit of mathematics (four year MA equivalent course in mathematics at Cambridge) and at least a reasonable background in software engineering and programming (about three years working as a software engineer now, plus a lot of random stuff on my spare time during that period and a little bit before hand), but I don’t have a lot of knowldge of the overlap between the two. This is increasingly causing me trouble, and I’d like to fix it. It seems like the sort of subject my blog audience should know about, so I’m asking for help here. :-)
The immediate subject I want to learn more about is numerical linear algebra. It’s come up a couple times recently and I’ve had to go “Bwrgh. Um. Halp!”. I usually muddle through, but it’s really not something I should be struggling on and I’ve probably done stupid things as a result of lack of knowledge.
So, my goal here is to become reasonably well versed in at least the basics of the subject. At the moment nothing terribly specific – I want to get a good grasp of the theory and practice of working with matrices, vectors, etc. computationally. Linear optimisation and eigenvector problems especially. I’m looking for recommendations for books, libraries, software packages and anything else you think would be useful. I’m willing to spend a reasonable amount of money (more so on the books than the software packages, as long term I’ll really be looking for stuff I can freely bundle with my personal projects) in doing so, ‘though obviously free is a plus. Libraries I can use from a variety of languages are definitely a good thing, though I’m willing to look at language specific things like NumPy, etc. too if they come highly recommended (at least as a starting point).
Relevant background:
Mathematics: Quite a lot of real and complex analysis, though mostly pure. Enough linear algebra that I at least know where to start with it, though I’m going to be rusty.
Programming/computer science: Some amount of general algorithms and datastructures work. Generally comfortable with Java, Haskell and Scala. Comfortable enough with C that I can write it if I have to. A little bit of Python and Lua (plus a few others which are probably not relevant). Fairly willing to pick up a new language if it would help (though if you tell me to write fortran I’ll cry).
So, suggestions?
Edit: I’ll keep a list of recommendations updated here. If you have any comments for or against these, please pipe up.
- Applied numerical linear algebra by Demmel
- Matrix computations by Golub and Loan
- Numerical Linear Algebra by Trefethen and Bau
- An Introduction to numerical methods and analysis by Epperson
- Numerical recipes in C by William H. Press, Saul A. Teukolsky, William T. Vetterling
- Matrix Algorithms by G.W. Stewart.
I found a copy of Epperson going very cheaply and for no particular reason it looked interesting, so I’ve ordered a copy. I’ll almost certainly order a copy of Golub and Loan. I’m also going to be playing around with Octave. Thanks guys!
MIT offers a complete set of linear algebra lecture videos via OpenCourseWare. MATLAB and Octave are great interactive environments for experimenting.
Can’t beat the Fortran libs. You can call them from whatever language you like, but most languages don’t really support arrays as well as Fortran.
For general numerical linear algebra, You could do worse that Golub and Van Loan, I find that it is extremely well written and quite comprehensive. It is not strong on optimization, as that is a related, but somewhat different field. There, I would suggest Nocedal and Wright, which covers more than just linear programming, but nowadays interior point methods are used for both linear and non linear programs.
(There are worse things in life than modern fortran)
Indeed. I’m assuming that whatever I end up doing long term will involve a wrapper around the Fortran libs. But I really don’t want to learn this material off something quite that painfully low level.
The MIT linear algebra lectures look like they’re more on the purse side of things. Is that not the case? It’s almost certainly worth my brushing up on that, so I’ll give them a look, but not the direct priority.
Thanks for the response.
Deinst:
I’m happy to cover optimisation separately. A good general knowledge of the subject is more important to me than strong knowledge of the specific bits I need right now, although obviously I’m hoping to pick those up too. :-)
The Golub and Van Loan book does look good. I think I’ll probably end up getting it, but would like to wait a little bit to hear other recommendations.
Pingback: History of Mathematics Blog » Blog Archive » Request for help: Numerical linear algebra
Pingback: EquMath: Math Lessons » Blog Archive » Request for help: Numerical linear algebra
I would suggest Numerical Linear Algebra by Trefethen and Bau. It’s not quite as comprehensive as Golub or Demmel, but I used it for my first-year graduate course in numerical linear algebra and found it very readable and clear.
For programming, we did everything in Matlab for all of my numerical analysis courses, but I would think that Octave or NumPy or even R would work well too, and they all have the advantage of being free. If you want to solve large-scale problems, you probably don’t want to implement things yourself but rather write a wrapper around the fortran (or sometimes C) libs–it might take you (or anyone) years to write an equally good implementation.
For optimization, Boyd and Vandenberghe is very good, though it focuses more on theory than implemetation. I’ve heard that the book is available in draft form online, perhaps from Boyd’s webpage at Stanford.
Indeed. I want this to be perfectly clear: I don’t intend to write my own linear algebra library (at least, I don’t intend to write and *use* my own linear algebra library. I’m sure I’ll implement some things as a learning exercise)! I probably won’t even write my own wrappers for the fortran libraries if I can find a good existing one. But I do want to understand how they work.
It definitely sounds like I should have a play around with Octave (I suppose I could buy matlab, but I’d rather not unless there’s a a good reason for it). Thanks for the book recommendations, I’ll add them to the list.
I just wrapped up a numerical methods class, and our textbook has everything you could possibly want.
“An Introduction to Numerical Methods and Analysis” by Epperson. It’s very rigorous and mathy, but they do give pseudocode. I’ve already written a few programs based on the linear algebra of the book (mostly having to do with row reduction), and the book was extraordinarily helpful, as it is based around the ideas of computation. If you get it, be sure to read the parts in the beginning about computational errors. This book will give you a lot of answers to important questions, such as convergence and rate of convergence. There is also a whole chapter dedicated to finding the solution to eigenvalue problems.
You’ll find that this stuff is fairly easy, though. If you just want to know how computational linear algebra works, look up the power method for eigenvalues, the inverse power method for eigenvalues, and LU factorization of matrices on Wikipedia to get yourself a head start.
Any decent linear algebra textbook should have a section on linear optimization. All you may be looking for is the Wikipedia treatment on all of these subjects.
I’ll second that recommendation for Numerical Linear Algebra. It’s great for self-learners. I just used it to prepare for the UIUC numerical analysis qual.
We used Biswa Nath Datta’s book.
It was pretty easy to follow, for a restricted subset of “easies.” :-)
Uses Matlab.
It was easier than Demmel’s.
You might also want to lok at Quarteoni’s books – all pretty good. Some are aimed at a first-look undergraduate level.
Sorry, that should have been Quarteroni.
Scientific Computing with MATLAB and Octave
is pretty entry-level, but also check out his other books.
Cheers.
You should not shun Fortran. It is very good for these sorts of computations, almost like pseudo-code for the numerical algorithms. Fortran 90 is not bad at all (which is what you should probably use).
Also, there is a huge number of scientific computing routines written in Fortran by experts in numerical computing.
But if you want to be on the cutting edge check out Fortress from SUN Microsystems.
I don’t think NumPy is adequate. Last I looked at it, it had an insufficent number of routines. For a free software alternative look at Scilab – it is developed by a consortium industry+academia (mostly in France, me thinks).
Fortress is so cutting edge you’ll bleed if you try to use it. :-) (It’s also totally unsuitable for high performance computing at the moment).
In terms of writing Fortran: I am not averse to at some point having to do so. I am deeply set against simultaneously attempting to come to terms with Fortran and another subject.
Thanks for the recommendations.
In terms of NumPy, it was just there as an example. I have no idea if it’s any good or not. I’ll check out scilab, thanks.
There are quite a few free resources you can start with. A good example is Numerical Methods in C (which is a free download) (you probably already know of this book). Chapter 11 deals especially with the calculations of Eigenvectors. You probably know of Gilbert Strangs introduction to linear algebra course on ocw.mit.edu.
Now to the bad part (at least in my experience). There is only one good linear algebra library – LAPACK. It is in the public domain. Most mathematical software uses LAPACK (MATLAB started out as a wrapper for LAPACK). The problem with LAPACK is that is in FORTRAN :(. I have found no good public domain mathematical software – especially for calculation of eigenvalues/vectors.
But it would be a good idea if you check what algorithms LAPACK implements when you write your own software or library (since they are the best). I am sure that if you write an open source linear algebra library in plain ANSI C, using excellent algorithms, quote a few people would be grateful (including me). I fear for the future when all the people that knows FORTRAN died of old age and the world goes back to the dark ages because no one understands LAPACK.
I read some of the above comments and would like to add some more:
If you are poor (like most of us), use Octave. Octave’s language is basically the same as that of Matlab and it can run most Matlab scripts without a problem. You can use for example both # and % for its comments, but Matlab only understands % – so write your Octave scripts so that it can run in Matlab too (it is just good practice).
In my experience though Matlab’s plotting is waay better than Octaves plotting (but that may be just me).
If you want your algorithms to execute fast (i.e. native), it is fairly easy to write it in C and just write an interface for Octave or Matlab (although in this case you will have to duplicate the plug-in interface for both octave and Matlab). You can then call your scripts from Octave/Matlab – it helps with plotting and provides a nice environment to use or test your algorithms in.
The text that someone mentioned from Boyd and Vandenberghe is mostly for convex optimization (e.g. quadratic constrained etc…). I am incidentally currently using it. I do not think this is the particular material that you are looking for – more numerical algebra…
Oh yeah – the book I mentioned is Numerical Recipes in C (William H. Press
, Saul A. Teukolsky, William T. Vetterling). The second edition was an online download – but I can not find it now. Use google and maybe check a P2P network/campus network. Somebody is bound to have downloaded it – check it and buy the new version if you like it.
Good Luck!
Numerical recipes !!!
http://en.wikipedia.org/wiki/Numerical_Recipes
Ok, as a LAPACK developer and finishing grad student in numerical linear algebra… You’ll want to skim some of these in a library (or possibly Google Books) first. Each has its own style of presentation and focus. You’ll need to decide which matches your needs (stylistic and technical).
Also, there’s a lot of ongoing work on eigenvalue problems. All these are references are a bit out of date, but only because the field has been moving forward… Probably the same can be said for interior point methods, but that’s not in my immediate sphere.
Golub & Van Loan: Very complete list of algorithms with sample code. Think of it as what “Numerical Recipes” could have been (on the linear algebra side) if it had bothered with being correct.
Demmel: (my advisor) Very comprehensive, probably the only single book that covers direct and iterative methods for linear systems and eigenvalue problems. Much practical advice.
Higham’s Accuracy and Stability of Numerical Algorithms: Very, very in-depth for linear systems. Gives excellent intuitions as well as the formalisms. Also has good practical advice and makes algorithms explicit.
Trefethen & Bau: Excellent intuitions about the linear algebra side. Scares many engineers because it emphasizes mathematical intuition from the beginning rather than presenting results and working backward.
Stewart’s Matrix Algorithms series: Imagine a point somewhere between Golub & Van Loan, Demmel, and Higham. Stewart’s Afternotes Goes to Graduate School contains many practical gems.
Numerical Recipes: If you don’t actually care about your results, use this book.
I know there are more, but I’m blanking on them and I’m not at home / near my bookcase. Other references:
Michael Overton’s Numerical Computing with IEEE Floating Point Arithmetic: Helps dispel many widely held myths about floating-point arithmetic. Higham’s text also covers the topic, but Overton’s book goes into far more depth.
Stephen Boyd and Lieven Vandenberghe’s Convex Optimization is at http://www.stanford.edu/~boyd/cvxbook/ and is really good. IIRC, Vanderbei’s Linear Programming: Foundations and Extensions is good as well. Note that the optimization community leans more towards proprietary gadgets than does the linear algebra community, at least in my observation.
And don’t knock Fortran without trying a modern flavor. If they had someone working on the language with the right background and enough time to specify and implement parameterized types, it would completely rock for numerical work…
I frequently come across numerical linear algebra for my job. I’ve got a semi-similar background (Math degrees and working as a scientific programmer for a Physicist at the moment). The best two references I’ve come across are Matrix Computations by Golub and Van Loan and Accuracy and Stability of Numerical Algorithms by Higham. The first is the theory, the second is a bit more practical (it details the algorithms used by LAPACK etc, but is still pretty theoretical and has been slightly more useful to me).
Get friendly with LAPACK/BLAS and the like. They really are the best libraries around and they are public domain. They are written in primarily FORTRAN77 but there are good interfaces for Fortran90/95 (which while still a PITA, is much better than 77) and other languages. As mentioned by others, many/most mathematical software just uses LAPACK instead of trying to do something better themselves.
Finally you’ve received a couple responses about the Numerical Recipes books. Just a word of warning with these. They are useful in certain circumstances, but these books will bite you if you don’t know exactly what you are doing. They are not written by mathematicians and as such suffer from the rigor and preciseness that you sometimes need. I own and use them, but I always attempt to verify the information contained. This has minimized the pain they can bring for me.
Thanks. It’s sounding like it’s definitely worth my while to pick up Golub and Van Loan.
And yeah, I’ve heard warnings about the numerical recipes books before. I’m planning to steer clear of them until I know what I’m doing a bit more.
I suggest you pick up a copy of “Mathematics for 3D Game Programming & Computer Graphics”. Here: http://www.amazon.com/Mathematics-Programming-Computer-Graphics-Development/dp/1584500379
It will give you a great foundation to work off of.
Scilab, Octave, R, and LAPACK are well worth a look, as other comments
mention. For linear programming there’s also lpsolve, and for dealing with
sparse matrices, you might consider ufsparse. You can try out lots of
free and proprietary optimization packages on the NEOS server, which
allows you to submit batch jobs by email. Some free non-linear optimization
packages are the sundials libraries (especially kinsol) and the minpack
fortran library. There are some tools on my web site to help at getting
some of these resources to work together.
For a good overview of many topics, including numerical linear algebra, I highly recommend Numerical Recipes
I found Scipy to be an extremely productive environment for me when I was working on a Latent Semantic Indexing problem in college.
A good paper to read and play with would be this one: http://lsi.research.telcordia.com/lsi/papers/JASIS90.pdf .
I used “Fundamentals of Matrix Computations” by David Watkins. It was OK – have no idea how it compares to other books. It’s quite theoretical.
I have to warn you – the maths and theory is fairly ugly. If you just want an overview to get an idea about the efficiency of various techniques, without the mathematical justifications, then this book is probably not for you.
http://www.nrbook.com/a/bookcpdf.php
Numerical Recipes in C
chapters 2 & 11 — good treatments
I suggest the following:
numpy + scipy + matplotlib + ipython + pil (python imaging library).
Then use interactive python via ipython -pylab. It’s really quite an amazing environment. There are also many addon libraries, depending on what you want to do. It would be nice if these packages were all bundled together.
If you want more symbolic stuff (sounds like you don’t) then check out sage (www.sagemath.org). It’s a bundling of many of the components above, but also has many other things.
I am not sure what components jj was referring to. I found numpy quite comprehensive.
Another book to get is Numerical Methods for Scientists and Engineers by Hamming. It’s rather old, but it’s available in a Dover edition for cheap.
Where good numerical linear algebra code like LAPACK comes from:
http://netlib.org/
Also take a look at TNT:
http://math.nist.gov/tnt/
I can second the recommendation for both Trefethen & Bau and Golub & van Loan. T&B is highly readable, and I would suggest it as a better introductory book, but G&vL is more comprehensive. If you have the money and interest, get both; they’re both available in paperback, which will help bring the price down, and I’ve found both to be useful.
Oh, Fundamental of Matrix Computations by David Watkins that Bettle B. mention I also used and it’s very good and friendly.
Golub and van Loan is a classic. Get it.
Another good idea is really to get a course on the topic.
As for getting your hands on some piece of software: write your own implementations of algorithms in octave. Check them against standard octave functions. R is definitly worth looking at, but it goes into statistics, that’s what R was actually made for. Oh, and LAPACK is still the for the brave of us.
If you’re more comfortable with Java than Python then you might want to check out Colt
http://acs.lbl.gov/~hoschek/colt/
They claim 90% of the performance of the Fortran libraries. It’s worth checking out.
I’ve actually used colt. It’s kinda painful and has some weird gaps but works rather well when you can bend it to your whims.
Pingback: Recent Links Tagged With "datastructures" - JabberTags