Matrix computations

What Hacker News says

1. sfpotterMar 2025
   A general pitfall in numerical methods is settling on a bad old method without understanding what all your options are. It's easy to get stuck on suboptimal methods, especially if you don't look at more recent references and the literature. Not all new methods are good; lots of old methods are great. There are a dozen different ways to solve any given problem. Usually, each method will be ~equally as hard for you the implementer to understand, but they can have wildly different performance characteristics. This is the main reason to avoid looking at something like Numerical Recipes---it will get you stuck in a local minimum.

   I'll try to give books that are good starting points and provide a useful and correct orientation for each topic. For each of these topics, there are many, many other books. I don't know all the books---I'm sure I'm missing other great references.

   General numerical analysis reference: Suli & Mayers, Stoer & Bulirsch, Ridgway Scott's book. There are many others---these are the ones I like. Suli & Mayers is truly excellent. Stoer & Bulirsch is comprehensive.

   Linear algebra, etc: Trefethen & Bau, "Matrix Computations". Yousef Saad's books. Greenbaum's book. There are other key topics not covered much by these, namely sparse direct solvers. Tim Davis has a good intro book. Martinsson has a new book on fast direct solvers---unclear how useful such solvers are in general.

   Approximation theory: "Approximation Theory and Approximation Practice" by Trefethen. Extremely important book. Many numerical methods for solving 1D problems (rootfinding, approximation, optimization, solving differential equations, nonlinear boundary value problems, representing special functions, etc) are made completely obsolete by using Chebyshev approximation, at least when the function you're working with is analytic (and even when not, you can get very far by using a "Chebyshev spline"). If all you're doing is calculus on a computer, this is probably the only book you need to read.

   Optimization: Nocedal & Wright. Boyd & Vandenberghe. Bertsekas has great books.

   Interval arithmetic: Moore, Kearfott & Cloud. This topic doesn't get as much play in the academic applied math/scientific computing/numerical analysis community, which is a real shame, IMO. Gives you the basic tools to get into verified numerics, where you can write algorithms which work provably correctly, allowing you to avoid epsilon hacking to some extent. E.g., "do X if |small number| < eps, otherwise do Y". Without verified numerics it's impossible to build correct algorithms on these kinds of predicates with floating point arithmetic).

   This covers what I would consider the "basic" topics. At least, if you're doing something else that's higher level (like solving PDEs), you need stuff from this toolbox.

   Show morethread
2. homerowilsonJan 2023
   I'm coming from an applied math perspective. A few of my favorites (and ones I find myself regularly referring to) are:

   Matrix Analysis by Horn and Johnson (perhaps the best end-of-chapter problem sets of any math book I've encountered!)

   Matrix Computations by Golub and Van Loan

   Elements of Statistical Learning by Hastie, Friedman, Tibshirani

   Functional Analysis by Reed and Simon

   Show morethread
3. jl2718Jun 2022
   Okay but somebody please explain to me the reason for prefix operator column-major notation.

   I digress…

   >> linear algebra doesn’t exist simply because humanity managed to concoct a system that coincidentally finds usage in many seemingly unrelated subjects

   I’m not a stranger to this field, but this article doesn’t make this case at all, and I’m not sure it can be made. Linear algebra is fundamentally a set of notation rules that people built upon and found ways to represent their problems with. It’s ubiquity in many fields is no more surprising than the observation that many different genre of literature are written in English, and somehow nobody is confused enough to think that flight instruction manuals are the domain of English rather than the range of it. There is no practical limit to the number of academic papers one can write which awkwardly contort a simple intuitive computation into an indecipherable representation in linear algebra. If you want the concept of linear algebra to consume all linearity that exists in the world, then fine, whatever, but then the notation sucks. You may call a continuous Fourier transform a linear operation, but try writing down the values of that matrix.

   No; there’s nothing fundamentally tying the inner-workings of the world to the mechanics of linear algebra, but has been considerable effort to adapt some narrowly-chosen set of mechanics to represent the world, and some subset of those things work out well, so that’s what we focus on. But this is just path dependency. A different set of rules for writing linear relationships could have worked out better, or worse, but it would have to get there regardless. I expect that the current system will disappear soon as the world shifts to talking about computational tensors, and more flexible rules about how to apply operations. Who says you can’t multiply a row by a row? That’s stupid; we can and should do better. Is the determinant magical, or is is just a an arbitrary series of shift-product-sum which is far more applicable in the general sense? Do we really need a whole matrix to describe a permutation?

   Linearity may be considered well-described when there is no longer any need for a separate course to teach the notation and tricks behind it. When I was in grad school, one of my favorite books was Gene Golub’s “Matrix Computations”. It really is an impressive book from an incredible mind, like a book on chess positions written by Bobby Fisher. Regardless, it was hard for me to go through it without wondering why such a thing exists. Much like chess, the human mind can become enamored with any simple set of rules that can be extended to sufficient complexity. Faced with a real problem, sometimes it helps me to get to a solution, and sometimes it distracts me from the solution. I can never be sure which is more common.

   Show morethread
4. ameliusApr 2022
   If you're looking for a better book, I can recommend:

   Matrix computations, by Golub and van Loan.

   thread
5. vitorsrJan 2022
   In my honest view this is a bad example. Axler is a professor of mathematics and editor of multiple undergraduate and graduate mathematics texts series. His supervisor’s supervisor was Paul Halmos.

   His books are introductory in the context of mathematics courses. They are not introductory in applied mathematical sciences contexts.

   There I would suggest, e.g., Boyd and Vandenberghe’s Introduction to Applied Linear Algebra [1], Meyer’s Matrix Analysis and Applied Linear Algebra [2], Golub and Van Loan’s Matrix Computations [3] etc.

   > But the book doesn’t like determinants and isn’t focused on computing things around matrices [...].

   This is purposeful.

   [1] https://web.stanford.edu/~boyd/vmls

   [2] http://matrixanalysis.com

   [3] https://www.cs.cornell.edu/cv/cvl_home/books

   Show morethread
6. tmyklebuJul 2021
   Nocedal and Wright is an excellent overview and a good starting point. Also consider:

   - R. Schneider, Convex bodies: the Brunn-Minkowski theory. The first two chapters are an excellent introduction to convex geometry (plus a little bit extra!) if you have some undergrad-level analysis.

   - Hiriart-Urruty and Lemarechal, Fundamentals of convex analysis. This book has been highly recommended to me but I've never used it. Might be an easier go than Schneider for convex geometry.

   - Golub and van Loan, Matrix computations. Excellent book on numerical linear algebra.

   - Bonnans, Gilbert, Lemarechal, Sagastizabal, Numerical optimization: theoretical and practical aspects. This book has a detailed description of bundle methods, which are important and in my opinion underutilised.

   - I. Maros, Computational techniques of the simplex method. This is the only book I'm aware of that discusses how to build a working implementation of the simplex method for linear optimisation.

   I'm not aware of any books that cover line search algorithms in detail. These are important in implementations but, beyond discussing the Goldstein and Wolfe conditions, generally glossed over in prose. Even in the absence of stalling and numerical difficulties, you can see an order of magnitude speedup from replacing a bad line search with a good one. One line search algorithm I've had success with is described in More and Thuente, Line search algorithms with guaranteed sufficient decrease.

   Lots of tacit engineering knowledge goes into building a fast and robust optimisation code. Some of that knowledge gets forgotten when code is rewritten or ported from one language to another.

   Mercifully, a lot of that engineering knowledge has been encoded into freely-available optimisation code. Quite a bit of that code is pretty readable. Off the top of my head, I've learnt things from:

   - Liu and Nocedal's Fortran L-BFGS implementation,

   - The CUTEst problem collection,

   - Chih-Jen Lin's LIBLINEAR and LIBSVM,

   - Lin and More's TRON,

   - Csaba Meszaros's BPMPD,

   - Jacek Gondzio's HOPDM,

   - The GNU Linear Programming Kit,

   - and probably quite a few other sources!

   Show morethread