4 ms·
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 opportunit
by kxyvr 9y ago
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 strategies depending on whether or not the entire matrix fits on a single GPU or if we have to use multiple GPUs. Incomplete or multilevel direct methods used as effective preconditioners for iterative methods are also important. Hell, even efficient direct techniques embedded in indirect solvers is important.
Part of the way to get started would be to look at something like a general numerical linear algebra book like Numerical Linear Algebra from Trefethen and Bau. There are better computational algorithms than what they present, but they do a good job at introducing important factorizations and why we care about them. Then, have a look at Tim Davis' book Direct Methods for Sparse Linear Systems. The codes in that book are online. Then, try to reimplement these algorithms in other languages, parallelize them, or make them better. These are good algorithms, but there are better and Tim's more recent codes are actively used by both MATLAB and Octave. Then, look for missing routines in open source libraries. For example, I just did a quick look and MAGMA currently lists missing routines between them and LAPACK.
Anyway, it's not a field for everyone, but it's one that good architecture and parallelization knowledge can have a positive impact. Nearly all engineering codes depend on good solvers, so the impact is wide.
- FabHK 9y agoThough, 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, and of modern computer architecture. However, I assume that you're right in that there might still be some low-hanging fruit. BTW, Julia is an awesome language with excellent LA support, and it's nice in that most algorithms are coded in Julia itself (unlike the two-language situation in Python, Clojure (AFAIK), etc.)
- dragandj 9y agoI think you are wrong about Julia, at least when it comes to linear algebra. Julia also relies on BLAS/LAPACK, at least those libraries that strive to be fast.
- FabHK 9y agoyou're absolutely right, I shouldn't have said "most". It basically calls BLAS/LAPACK (as every other language, and as one should), and does almost everything beyond that in Julia.
- one-more-minute 9y agoTo 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.
- dragandj 9y agoCan 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?
- newen 9y agoWell 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.
- FabHK 9y ago> 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... :-)
- santaclaus 9y agoPenn or Stanford? I think that was mostly Nick Foster’s work.
- FabHK 9y agoStanford. 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.
- santaclaus 9y agoFedkiw coauthored a paper with Foster in 2001, which is about the time of Shrek, so that must have been it!
- clairity 9y ago> "...Numerical Linear Algebra from Trefethen..." wow, what a blast from the past! i took intro CS with trefethen, and he was nice enough and obviously quite smart, but oh boy was his class ever boring. probably one of the deciding factors against my doing a CS major (besides not being terribly good at it). maybe i should take a gander at his book, since (ironically) i used computational linear algebra for my master's and ended up liking it. i took an old version of numerical recipes (https://en.wikipedia.org/wiki/Numerical_Recipes https://en.wikipedia.org/wiki/Numerical_Recipes) and translated what i needed into MATLAB.