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?
Asked
Active
Viewed 302 times
6
-
1It depends on what you want to do with the analysis. But I think this is too much of a reference request question. – Teepeemm Nov 01 '15 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. – Léo Léopold Hertz 준영 Nov 07 '15 at 17:55
-
1SO generally closes questions asking us to “recommend or find a … software library,” because there can be several valid answers. For reference, see http://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 07 '15 at 19:12
1 Answers
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!
