Hi there, Yes it would make a lot of sense to create new issues on Github for the sparse things. I will do that. I am visiting my hometown this week, so I'll get back to that once I am back from the trip. I myself have a lot of pending issues to work on for linalg ;)
Feel free to share any updates from your side in the meantime. On Thu, Jan 7, 2016 at 2:00 AM, nginn <[email protected]> wrote: > Hi Rahul, > > Thank you for such a thoughtful explanation! I think I will stick with the > suggested sequence for creating the list of functions for now and let you > know when I'll have any progress or face problems which I can't understand. > > And maybe there's a reason to create an issue on a github for this? It > would be great to collect all the code for sparse methods (EigenSparseUtil > and other suggested) and other stuff separately. > > On Mon, Jan 4, 2016 at 9:55 AM, Rahul De <[email protected]> > wrote: > >> Hi Anastasia, >> >> (CC-ing Shogun mailing list) >> >> Thanks for reaching out to me. I haven't been very active in the >> community lately. >> >> See the whole point of linalg is to support third party backends >> seamlessly. So, ideally sparse linalg would make sense when we use third >> party backends to compute sparse stuffs. For dense, we have supported >> common operations with Eigen and ViennaCL backends. Now, for sparse, things >> aren't that easy. The main issue is memory layout, which in this case isn't >> a contiguous array of data like dense vectors/matrices. As I mentioned in >> the thread, we have a LIL implementation of sparse matrices, whereas >> libraries like Eigen use CSC. So, in each sparse linalg method, we have to >> map our sparse data structure back and forth to >> Eigen/(Put-Some-Other-Lib-Name-Here) sparse data structures, since our >> linalg API will deal with SGSparse, not third party data structures. This >> would cause some overhead, like >> >> - allocating new memory for third-party object, >> - mapping the entire data one by one (can't just std::copy a chunk, but >> we gotta copy things element-wise), >> - and then after the computation, copy the result back to SGSparse data >> structures (again, element-by-element) >> - and then destroying the temporary third-party sparse object. >> >> Check this EigenSparseUtil<T>::toEigenSparse >> <https://github.com/shogun-toolbox/shogun/blob/develop/src/shogun/mathematics/eigen3.cpp#L23> >> method >> where we do the copy from SGSparseMatrix to Eigen::SparseMatrix. >> >> This extra overhead would be an overkill for small operations I think. >> So, we really need to make sure we really do get some benefit doing all the >> above things than doing a native implementation that directly deals with >> SGSparse, without using a third party library. That's the criteria. >> >> So, here's how I'd go about it. >> >> - First, add a method in the EigenSparseUtil class, that takes a >> Eigen::SparseMatrix and returns a SGSparseMatrix, make sure it works >> properly - unit tests with symmetric, asymmetric matrices. >> - Add similar methods for sparse vectors in that util class >> - start with dot product. Write a benchmark with two methods inside it: >> one, that takes two SGSparseVectors and returns the dot product using >> the native method we have, and >> two, one that first converts the vectors to Eigen types, and then >> uses Eigen to do the dot. >> Run that benchmark a couple of hundred/thousand times, see if we get >> some performance boost. If it does, add "dot" to the list (open a new issue >> on Github). >> - repeat the above for other operations (the ones that are there in >> dense), matrix-vector multiplications, etc etc. Each time we get better >> performance using Eigen, add that operation to the list. >> - explore other fast third party libraries that supports sparse linalg. >> Run the benchmarks using some of them as backend. >> >> Once we have that list, we'll design our sparse linalg accordingly. Even >> if the list is empty (that is, we didn't get much performance boost using >> third-party libraries), it would be interesting to implement some of the >> fast sparse stuffs on our own. There are a few books by Dr Yousef Saad (I >> haven't read those, just noticed it back when I did some of the sparse >> iterative solvers stuffs), we can look into it once we have that list). But >> anyway we can worry about that later. >> >> I think we can discuss more about this on IRC so that we can get >> suggestions from others as well. I'll try be online there more often. If >> you have questions, please let me know and then we can take it to IRC. >> >> Hope it helps. >> >> Best, >> Rahul >> >> On Sat, Jan 2, 2016 at 7:56 PM, Anastasia E. <[email protected]> >> wrote: >> >>> Hi lambday >>> >>> I'm nginn, we communicated about issue #2717 "Add scale and add to >>> linalg" some time ago. >>> I'm sorry if this somehow violates your privacy but your email was >>> available in the git log of shogun repo so I suppose it's not that private >>> information %) >>> >>> So, my question is: could you provide me with some information about >>> implementation of sparse methods in the shogun::linalg? Earlier you've said >>> that "we need to first come up with a list of operations for which it does >>> make sense". What are criteria for this decision? >>> >>> >>> >>> >>> >> >> >> -- >> Best, >> Rahul >> +919620408085 >> > > -- Best, Rahul +919620408085
