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
