<p>To my best knowledge: </p>

<ol>
<li><p>If you read about <strong>lower bounds</strong> in some algebraic computational model, then the usual assumption is that <em>the ring or field operations are of constant cost</em>, that is they are given as primitives. This is the assumption made in one of the main sources on the topic: Burgisser, Clausen, Shokrollahi-<em>Algebraic complexity theory</em> (Springer, 1997).
(And this is what is modeled by algebraic circuits, for instance.)</p></li>
<li><p>When one speaks about <strong>upper bounds</strong>, 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.</p></li>
<li><p>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:
<em>Algorithmic Algebra</em>, Bhubaneswar Mishra, Springer 1993: Chapter 3 deals with ways to represent certain rings.</p></li>
</ol>

<p>Other books of interest might be: Zur Gathen and Jurgen Gerhard, <em>Modern Computer Algebra</em>, Cambridge, 1999. And possibly Victor Shoup, <em>A Computational Introduction to Number Theory and Algebra</em>, (Available online).</p>

CC BY-SA 2.5
2010-10-21T15:14:13.200Z
A book online really helps!!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-10-21T07:30:53.910Z
2010-10-21T07:44:44.570Z
2010-10-21T07:44:44.570Z
Iddo Tzameret
<p>You might also have luck with the keywords 'computational commutative algebra' and 'computational algebraic geometry.'  Try <a href="http://rads.stackoverflow.com/amzn/click/0387356509" rel="nofollow">CLO</a> 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.</p>

CC BY-SA 2.5
2010-10-21T03:44:36.323Z
2010-10-21T03:44:36.323Z
Jason Morton
<p>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 <a href="http://rads.stackoverflow.com/amzn/click/0521826462">book</a> 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.</p>

CC BY-SA 2.5
2010-10-19T01:09:05.703Z
A "field" called Computer "Algebra"... Hmm... Anyway, thank you for the book and the keyword now I can do some further searches!!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-10-18T04:10:52.400Z
2010-10-18T04:10:52.400Z
Shiva Kintali
<p>While reading a paper about using algebraic methods to detect some induced subgraphs, it appears that <strong>edge ideal</strong> 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.)</p>

CC BY-SA 2.5
2010-10-18T02:31:42.570Z
Sorry if the question is too elementary or broad...
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-10-18T03:05:57.870Z
that's a nice question.
Suresh Venkat
CC BY-SA 2.5
2010-10-18T03:48:54.717Z
While I don't know much about the topic myself, I'd recommend checking out [On the Ring Isomorphism and Automorphism Problems](http://portal.acm.org/citation.cfm?id=1068502.1068642) 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.
Robin Kothari
<ds.algorithms><reference-request><algebra><algebraic-complexity>
Formal representation of rings in computations
Hsien-Chih Chang 張顯之
# Formal representation of rings in computations

(Asked by: username_0 on 2010-10-18)

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.)

**Tags:** ds.algorithms, reference-request, algebra, algebraic-complexity
> **Comments:**
> **username_0**: Sorry if the question is too elementary or broad...  
> **username_1**: that's a nice question.  
> **username_2**: While I don't know much about the topic myself, I'd recommend checking out [On the Ring Isomorphism and Automorphism Problems](http://portal.acm.org/citation.cfm?id=1068502.1068642) 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.  

---

## 3 answers

### Answer by username_5 on 2010-10-18. Score: 14 | Accepted answer

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](http://rads.stackoverflow.com/amzn/click/0521826462) 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.

> **Comments:**
> **username_0**: A "field" called Computer "Algebra"... Hmm... Anyway, thank you for the book and the keyword now I can do some further searches!!  

---

### Answer by username_3 on 2010-10-21. Score: 14

To my best knowledge:

1. 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.)
2. 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.
3. 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).

> **Comments:**
> **username_0**: A book online really helps!!  

---

### Answer by username_4 on 2010-10-21. Score: 8

You might also have luck with the keywords 'computational commutative algebra' and 'computational algebraic geometry.' Try [CLO](http://rads.stackoverflow.com/amzn/click/0387356509) 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.


---

