Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

LU Factorization and Linear Systems for Programers

dragan.rocks

Post reply on HN
Print view View original

21–30 of 46 posts

Re: LU Factorization and Linear Systems for Programers

#21

Post by FabHK »

kxyvr wrote: post #12

By the way, if anyone is interested in good open source opportunities, computational linear algebra is nowhere near a solved problem and there's good opportunity for impactful contribution. The computational challenges of the algebra versus factorizations is one angle. Dense versus sparse is another. Shared memory parallelization vs distributed memory vs GPUs is another. Even on the GPU, there are different strategie…

> so the impact is wide

Yeah - in Shrek (2001), there's a scene where the eponymous ogre takes a mud bath in the swamp. When I studied this linear algebra stuff, one of my (more advanced) fellow students told me that their research group had "done" the mud... :-)

Re: LU Factorization and Linear Systems for Programers

#22

Post by kxyvr »

FabHK wrote: post #15
kxyvr wrote: post #12

By the way, if anyone is interested in good open source opportunities, computational linear algebra is nowhere near a solved problem and there's good opportunity for impactful contribution. The computational challenges of the algebra versus factorizations is one angle. Dense versus sparse is another. Shared memory parallelization vs distributed memory vs GPUs is another. Even on the GPU, there are different strategie…

Though, the classic dense methods have been implemented and optimised and ported to death with LAPACK/BLAS, haven't they. What you're talking about is parallelisation, moving to GPU, and modern (combinatorial) methods for sparse systems, and that's fairly cutting edge, and not trivial to implement/port. You'll need to have a pretty good understanding of the language and its paradigmatic use, and of linear algebra, an…

Yes, I believe that dense methods on single core architectures have been well ported. Of course, even there, it wasn't until I believe Eigen that we were able to moderately easily run automatic differentiation over the algebra and factorizations to get their derivatives. Though, technically, yes, we could have run ADIFOR over LAPACK and hated ourselves in the process.

It's been some time since we've seen significant speed increases for single core computers, so as new chips moved to multicore or GPU processing, the field followed. That said, even moderately basic operations such as matrix multiplication weren't fully implemented until maybe three years. I'm sure there were other groups, but that's when NVIDIA released cuBLAS-XT, which allowed multiplication of matrices that didn't fit on the GPU.

So, yes, I agree that this is nontrivial and difficult. At the academic level, numerical linear algebra tends to be in the domain of applied math departments, so I think that sometimes well suited people in CS don't get introduced to the field. That's partly why I enjoy seeing articles on HN that discuss it.

Re: LU Factorization and Linear Systems for Programers

#23

Post by R_haterade »

FabHK wrote: post #13
dagss wrote: post #5

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.

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 proba…

Excellent John D. Cook piece on the same subject: https://www.johndcook.com/blog/2010/01/19/dont-invert-that-m...

Re: LU Factorization and Linear Systems for Programers

#25

Post by santaclaus »

FabHK wrote: post #21
kxyvr wrote: post #12

By the way, if anyone is interested in good open source opportunities, computational linear algebra is nowhere near a solved problem and there's good opportunity for impactful contribution. The computational challenges of the algebra versus factorizations is one angle. Dense versus sparse is another. Shared memory parallelization vs distributed memory vs GPUs is another. Even on the GPU, there are different strategie…

> so the impact is wide Yeah - in Shrek (2001), there's a scene where the eponymous ogre takes a mud bath in the swamp. When I studied this linear algebra stuff, one of my (more advanced) fellow students told me that their research group had "done" the mud... :-)

Penn or Stanford? I think that was mostly Nick Foster’s work.

Re: LU Factorization and Linear Systems for Programers

#26

Post by compumike »

For a gentler introduction to LU factorization and how useful the decomposition is for efficiently re-solving the same system multiple times, I'd offer up the "Systems of Equations" section of the "Ultimate Electronics" book I've been working on: https://www.circuitlab.com/textbook/systems-of-equations/

I tried to go back and forth between the 5x+2y=3 style equations that most people are familiar with and the matrix forms.

Re: LU Factorization and Linear Systems for Programers

#27

Post by FabHK »

santaclaus wrote: post #25
FabHK wrote: post #21

Earlier quoted context omitted.

> so the impact is wide Yeah - in Shrek (2001), there's a scene where the eponymous ogre takes a mud bath in the swamp. When I studied this linear algebra stuff, one of my (more advanced) fellow students told me that their research group had "done" the mud... :-)

Penn or Stanford? I think that was mostly Nick Foster’s work.

Stanford. I thought it was Ron Fedkiv’s group, but I might easily misremember, or could’ve been a visitor. I mostly remember because it was such a random thing. The graphics people had a lot of fun, one group was working on hair, fur, and fire or so. All boils down to PDEs, discretised into massive linear systems.

Re: LU Factorization and Linear Systems for Programers

#28

Post by newen »

dragandj wrote: post #19
one-more-minute wrote: post #18

Earlier quoted context omitted.

To be fair, almost all of those linalg kernels have pure-Julia implementations (mainly so they work across any numeric type). I think "most" is a reasonable description, with a few special cases that reach out to BLAS and co.

Can you give an example in popular Julia library(ies) that do that, and, very important, to speed comparisons? Are those operations close to the speed found in MKL for example?

Well if you define a new type, and * and + operations for it, you will get matrix multiplication for free in native julia. I think you can do similar things for a few other algorithms in native julia. I don't think it will be MKL speed though because MKL uses cache size information etc. and is very optimized. Of course julia uses BLAS/Lapack etc for the types it can.

GenericSVD.jl is an interesting example of how you can factorize a matrix of quaternions by just defining appropriate functions for quarternions and running using the generic SVD algorithm (it's just an example of what I talked about above, the library is not really used by anyone I think).

Knet.jl is a fairly mature deep learning library that really demonstrates the power of the language. You simply define your forward and loss functions, and then you are set. The function gets auto diferentiated and you go ahead and do SGD. There really isn't anything else you need to mess with. It also works seamlessly with GPU arrays without you having to touch the forward and loss functions.

Re: LU Factorization and Linear Systems for Programers

#29

Post by radarsat1 »

FabHK wrote: post #15
kxyvr wrote: post #12

By the way, if anyone is interested in good open source opportunities, computational linear algebra is nowhere near a solved problem and there's good opportunity for impactful contribution. The computational challenges of the algebra versus factorizations is one angle. Dense versus sparse is another. Shared memory parallelization vs distributed memory vs GPUs is another. Even on the GPU, there are different strategie…

Though, the classic dense methods have been implemented and optimised and ported to death with LAPACK/BLAS, haven't they. What you're talking about is parallelisation, moving to GPU, and modern (combinatorial) methods for sparse systems, and that's fairly cutting edge, and not trivial to implement/port. You'll need to have a pretty good understanding of the language and its paradigmatic use, and of linear algebra, an…

> What you're talking about is parallelisation, moving to GPU, and modern (combinatorial) methods for sparse systems, and that's fairly cutting edge, and not trivial to implement/port.

Honestly, it might be tricky, but implementing matrix operations is not rocket science either. I find it incredible that so many projects rely on NVidia's proprietary libraries for doing this on GPU. Maybe there is some secret juice that I just don't know about, but it seems to me there can't be that many optimisation shortcuts for matrix multiplications and the like that require intimate, secret knowledge of the hardware.

Re: LU Factorization and Linear Systems for Programers

#30

Post by santaclaus »

FabHK wrote: post #27
santaclaus wrote: post #25

Earlier quoted context omitted.

Penn or Stanford? I think that was mostly Nick Foster’s work.

Stanford. I thought it was Ron Fedkiv’s group, but I might easily misremember, or could’ve been a visitor. I mostly remember because it was such a random thing. The graphics people had a lot of fun, one group was working on hair, fur, and fire or so. All boils down to PDEs, discretised into massive linear systems.

Fedkiw coauthored a paper with Foster in 2001, which is about the time of Shrek, so that must have been it!
Post reply on HN