While reading a paper about using algebraic methods to detect some induced subgraphs, it appears that edge ideal is an important tool connecting commutative algebra and graph theory. Since I'm not familiar with computations of algebraic objects, is there any good references or books on this topic? Particularity in representing a ring R on a Turing machine, and the complexity of deciding basic properties on R (say, the height of an prime ideal in R.)
$\begingroup$
$\endgroup$
3
asked Oct 18, 2010 at 2:22
-
$\begingroup$ Sorry if the question is too elementary or broad... $\endgroup$– Hsien-Chih Chang 張顯之Oct 18, 2010 at 2:31
-
$\begingroup$ that's a nice question. $\endgroup$– Suresh VenkatOct 18, 2010 at 3:05
-
4$\begingroup$ While I don't know much about the topic myself, I'd recommend checking out On the Ring Isomorphism and Automorphism Problems by Kayal and Saxena. It's a very complexity theoretic paper, so that should help. I believe they represent finite rings by first specifying the additive group (by its generators) and then giving a list of pairwise products of all these generators. $\endgroup$– Robin KothariOct 18, 2010 at 3:48
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
Your questions are related to a field (no pun intended) called "Computer Algebra". I myself was looking for comprehensive surveys when I was working on algebraic methods to calculate various graph centrality metrics. I could not find good surveys, but this book was partially helpful. The research papers on this "topic" are scattered all over and often not explicitly categorized as "computer algebra". Reading algorithmic papers on isomorphism, factoring (integers/polynomials) and graph algorithms based on matrix multiplication might give you more insights.
-
$\begingroup$ A "field" called Computer "Algebra"... Hmm... Anyway, thank you for the book and the keyword now I can do some further searches!! $\endgroup$ Oct 19, 2010 at 1:09
$\begingroup$
$\endgroup$
1
To my best knowledge:
If you read about lower bounds in some algebraic computational model, then the usual assumption is that the ring or field operations are of constant cost, that is they are given as primitives. This is the assumption made in one of the main sources on the topic: Burgisser, Clausen, Shokrollahi-Algebraic complexity theory (Springer, 1997). (And this is what is modeled by algebraic circuits, for instance.)
When one speaks about upper bounds, for standard questions in algebraic complexity, like when studying polynomial identity testing procedures, then the standard assumption is that the ring or field operations can be computed in polytime. This means that one works over the integers, or over the rational numbers, and it is easy to find an encoding scheme that enables such efficient computations of the basic operations.
For other purposes I know of, concerning algebraic models, the way to represent the ring or field is a real question and sometimes there is no efficient way to do so, and there might even be questions of undecidability. The references I know of that cover these kind of questions are the book Shiva Kintali gave, and also: Algorithmic Algebra, Bhubaneswar Mishra, Springer 1993: Chapter 3 deals with ways to represent certain rings.
Other books of interest might be: Zur Gathen and Jurgen Gerhard, Modern Computer Algebra, Cambridge, 1999. And possibly Victor Shoup, A Computational Introduction to Number Theory and Algebra, (Available online).
answered Oct 21, 2010 at 7:30
$\begingroup$
$\endgroup$
You might also have luck with the keywords 'computational commutative algebra' and 'computational algebraic geometry.' Try CLO as a starting point, and look at J. Symbolic Computation, and systems like Macaulay2 and Singular and the papers that reference them. The big hammer is Gr\"obner bases, the computation of which will solve many algebraic problems, but is worst-case doubly exponential in general.
