4 ms·
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 parallel
by FabHK 9y ago
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, 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.
- dragandj 9y agoWhen I hear "you just do X", I become sceptical of that instantly :)
- kxyvr 9y agoAs a note, this feature isn't exclusive to Julia. For example, Eigen implements something similar and the requirements for doing so are specified here: https://eigen.tuxfamily.org/dox-devel/TopicCustomizing_CustomScalar.html https://eigen.tuxfamily.org/dox-devel/TopicCustomizing_Custo... The reason to do so is to use a more exotic type that gives additional information. In the simplest case, we may want to use quad precision, which BLAS and LAPACK do not support by default (but it is possible to hack in). Alternatively, it's a good way to run automatic differentiation through the solve, or use infinite precision libraries like GMP, or use interval arithmetic. So, yes, it's right to be skeptical, but it is possible, some libraries support it, and it's a useful trick to have available.
- dragandj 9y ago
- FabHK 9y agoGood point - Julia does LinAlg with BigFloats and other "exotic" numbers, if you wish. But it definitely also integrates LAPACK/BLAS, and Tim Davis' SuiteSparse.
- kxyvr 9y agoYes, 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.
- radarsat1 9y ago> 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.
- egocodedinsol 9y agoThe hard part isn’t getting it basically right. The hard part is knowing where subtle bugs are. I remember my numerical computing textbook had one major takeaway: almost always write your own matrix algorithms; almost never use them. An extraordinary amount of work has gone into linear algebra computation and much of it for mission critical stuff. It might not be “rocket science” but it’s close.
- kxyvr 9y agoThis is an important point, but I don't think it's insurmountable for a broader group of people. Though technically not required, I think it helps to know a good deal of mathematical theory as well in order to check properties that should hold, which helps in tracking down subtle bugs. In my experience, tracking these bugs is a royal pain in the ass and writing good tests for these properties is tedious. Even then, there's a lot of funny stuff that goes on. One of my favorites is that it's possible to take the Choleski factorization of an indefinite matrix in some situations. That means it's not safe to use a Choleski to check for whether or a not a matrix is positive definite for mission critical functions: https://scicomp.stackexchange.com/a/26223 https://scicomp.stackexchange.com/a/26223 But, anyway, mostly I contend that writing these algorithms is extremely tedious, so there's not that many people with the patience. I also still maintain that there's room for contribution here. Although most often these routines are written in C and Fortran, the parallel tooling for these languages is less sophisticated than that of modern languages. I've been wondering whether a language like Rust would make it easier to code and parallelize some of these algorithms.
- dnautics 9y ago+1 for Julia is an awesome language, but for most LA problems it kicks it to the BLAS libraries! I think they have now fixed the native julia LA... Next week I'm deploying it to do reed-solomon repair (using a custom numerical type).
- geezerjay 9y ago> Though, the classic dense methods have been implemented and optimised and ported to death with LAPACK/BLAS, haven't they. Those are generic algorithms that are effective but may be far from being the most efficient, particularly if the problem structure isn't taken in consideration. > 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. Those are by far not the only issues. For example, dense matrices require n^2 elements, which means that in practice 32GB pack at most a 63k*63k dense matrix. This is rather small for some engineering applications. If anyone wishes to go beyond this, they either have to throw money at the problem to continue running naive code on HPC hardware or they work on algorithms. Today's solvers are actually bundles of custom-made algorithms that apply sequences of algorithms to "massage" the problem to improve their tractability, such as applying partial factorizations or reordering schemes, to improve efficiency. Moreover, there is yet much research work to be done in the field of matrix factorization. For instance, matrix reduction schemes are starting to make their way into practical engineering applications, and among them we are seeing an increase in demand in specialized techniques such as non-negative matrix factorization. There are no "classical methods" for this sort of factorization scheme, and yet it's a very basic technique.