3 ms·

For programmers, the really interesting part of dense linear algebra is how to achieve high performance, as blocking techniques have to be used to amortize load

by dagss 9y ago

For programmers, the really interesting part of dense linear algebra is how to achieve high performance, as blocking techniques have to be used to amortize loads from memory to cache. Google for Goto's "Anatomy of high-performance matrix multiplication", one of my favorite programming texts. Also the papers underlying the development of the "Elemental" library for distributed dense linear algebra is worth a look.

gmiller123456 9y ago
To save people a few clicks: [1] https://www.cs.utexas.edu/users/pingali/CS378/2008sp/papers/gotoPaper.pdf https://www.cs.utexas.edu/users/pingali/CS378/2008sp/papers/...
FabHK 9y ago
> how to achieve high performance You really just want to use LAPACK/BLAS, no? (That's what the Neanderthal library mentioned in the article does, btw, and basically linear algebra libraries for other languages, too. If not, you probably shouldn't use it...) http://neanderthal.uncomplicate.org http://neanderthal.uncomplicate.org
- dagss 9y ago
  Of course you should but the blocking and amortization techniques have much wider usecases beyond linear algebra. Matrix multiplicaton is a useful "simple" example to study; of course you don't write your own if what you want to do is covered by BLAS/LAPACK. For instance I have written high performance spherical harmonic transforms, and these techniques apply then.
FabHK 9y ago
BTW, I think one important take-away for programmers is: Don't invert matrices. For example, the solution for the least squares (=linear regression) problem is beta^hat = (X'X)^-1 X'y and you might think that the best way to compute it is to compute X'X, invert it, do the multiplication, yada yada yada. But it's really better to just ask your library (Matlab, LAPACK, ...) to solve the problem for you, and it'll probably do a QR decomposition. For small problems, it doesn't really matter, but for big problems you'll be both faster and more accurate.
- R_haterade 9y ago
  Excellent John D. Cook piece on the same subject: https://www.johndcook.com/blog/2010/01/19/dont-invert-that-matrix/ https://www.johndcook.com/blog/2010/01/19/dont-invert-that-m...
  - conistonwater 9y ago
    That's a slightly different issue: the issue with solving normal equations directly is that the condition number of X^\top X is the square of the condition number of X, so it's much more significant than lu-vs-inv. It can matter a great deal for ill-conditioned linear regression problems where some features resemble each other.

by dagss 9y ago

gmiller123456 9y ago

To save people a few clicks: [1] https://www.cs.utexas.edu/users/pingali/CS378/2008sp/papers/gotoPaper.pdf https://www.cs.utexas.edu/users/pingali/CS378/2008sp/papers/...

FabHK 9y ago

> how to achieve high performance You really just want to use LAPACK/BLAS, no? (That's what the Neanderthal library mentioned in the article does, btw, and basically linear algebra libraries for other languages, too. If not, you probably shouldn't use it...) http://neanderthal.uncomplicate.org http://neanderthal.uncomplicate.org

dagss 9y ago
Of course you should but the blocking and amortization techniques have much wider usecases beyond linear algebra. Matrix multiplicaton is a useful "simple" example to study; of course you don't write your own if what you want to do is covered by BLAS/LAPACK. For instance I have written high performance spherical harmonic transforms, and these techniques apply then.

FabHK 9y ago

BTW, I think one important take-away for programmers is: Don't invert matrices. For example, the solution for the least squares (=linear regression) problem is beta^hat = (X'X)^-1 X'y and you might think that the best way to compute it is to compute X'X, invert it, do the multiplication, yada yada yada. But it's really better to just ask your library (Matlab, LAPACK, ...) to solve the problem for you, and it'll probably do a QR decomposition. For small problems, it doesn't really matter, but for big problems you'll be both faster and more accurate.

R_haterade 9y ago
Excellent John D. Cook piece on the same subject: https://www.johndcook.com/blog/2010/01/19/dont-invert-that-matrix/ https://www.johndcook.com/blog/2010/01/19/dont-invert-that-m...
- conistonwater 9y ago
  That's a slightly different issue: the issue with solving normal equations directly is that the condition number of X^\top X is the square of the condition number of X, so it's much more significant than lu-vs-inv. It can matter a great deal for ill-conditioned linear regression problems where some features resemble each other.