6

I am researching sparse adjacency matrices where most cells are zeros and some ones here-and-there, each relationship between two cells has a polynomial description that can be very long and their analysis manually time-consuming. My instructor is suggesting purely algebraic method in terms of Gröbner bases but before proceeding I would like to know from purely computer science and programming perspective about how to analyse sparse adjacency matrices? Does there exist some data mining tools to analyse them?

3
  • 1
    It depends on what you want to do with the analysis. But I think this is too much of a reference request question.
    – Teepeemm
    Nov 1, 2015 at 20:12
  • @Teepeemm Can you please clarify your comment? In which cases is the attempt too much? It would be great to understand this better. Nov 7, 2015 at 17:55
  • 1
    SO generally closes questions asking us to “recommend or find a … software library,” because there can be several valid answers. For reference, see meta.stackexchange.com/a/124489/261760. The first part of my comment is more self-explanatory: if the analysis is easy (“how many ones in each row and column”), then you may be able to create your own class. If it’s more complicated, you may want an existing library. But an existing library would need to be able to do the analysis you need, so we’d want to know what it is you need.
    – Teepeemm
    Nov 7, 2015 at 19:12

1 Answer 1

6

Multivariate polynomial computation and Gröbner basis is an active research area. In 1991, Sturmfels in Sparse elimination theory outlined the resultant methods and GR methods. In 2015 July conference, CoCoa analysis.

SE is gathering awesome material on this such as GR computational analysis in M2 where you an find step-by-step examples outlined in the books and different answers. For sparse matrices, there are sparse matrix algorithms built with GR bases such as Faugère's F4 and F5 algorithms that is based on Buchberger algorithm.

Updating this when finding more!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.