11
$\begingroup$

Background

I have some background in abstract commutative algebra and basic scheme theory as covered in Atiyah/Macdonald and the notes by Ravi Vakil. What I have absolutely no background in is computer science and programming.

However, I would like to self-learn some algorithmic or computational algebra. I would appreciate to see some book recommendations concerning these topics.

Books that I know about

What seems to be quite standard but not very deep on the algebra side and not so explicit on the implementation side (which I want to learn as well) is the book Ideals, Varieties and Algorithms by Cox, Little and O'Shea.

I also know about the book A SINGULAR Introduction to commutative algebra by Greuel and Pfister. It seems to be much more in depth on the algebra side --- covering for example commutative algebra over arbitrary base rings, not just fields --- and closely connected to the CAS SINGULAR.

There is also a three volume book Computational Commutative Algebra by Kreuzer and Robbiano working with the CAS CoCoA.

Besides those computer Algebra books there are books on constructive algebra (which I am also interested in) like Commutative Algebra: Constructive Methods by Lombardi and Quitté an A Course in Constructive Algebra by Mines, Richman and Ruitenburg. These work purely constructively but do not make explicit the algorithms that can be extracted from the proofs.

My Questions

Is it important to have a book focusing on one CAS explicitly?

From this there arise two more questions:

Which CAS should I decide for?

There are so many choices here and I'm not sure if they are basically all the same or if there are major differences and which to prefer.

Where does the programming experience come from?

Suppose I just learned about Gröbner bases and the Buchberger algorithm. I might implement some version of that algorithm and compute Gröbner bases of two or three more or less complicated ideals. And then? Is this all? Move on to the next topic? Although I want to learn so computational thinking, it is not the case that every day I encounter problems that can only be solved with a computer. So where do the problems to solve and to earn experience from?

How to check if I have written good code?

This is perhaps more a computer science question. But computer scientists probably have to hand in exercises for university or so where they get feedback. If I write the worst and most inefficient code one can think of, which still somehow works - how should I know?

$\endgroup$
5
  • 1
    $\begingroup$ See also the book Modern Computer Algebra. $\endgroup$
    – lhf
    Jul 10, 2017 at 10:57
  • 2
    $\begingroup$ The real question behind the answer to your question is that what do you want to do with that? Will your research be in symbolic computations? Or do you need such computer software as a tool? $\endgroup$
    – Youngsu
    Jul 14, 2017 at 4:25
  • $\begingroup$ @Youngsu Well basically I want to deepen my understanding of algebra by learning algorithmic and computational methods and in order to learn algorithmic methods I think it is useful if not necessary to implement them. $\endgroup$
    – user158047
    Jul 15, 2017 at 16:27
  • $\begingroup$ If your primary goal is solidifying your understanding in Algebra, I do not suggest spending too much time on computer algebra systems. There are a couple of reasons. 1) not every single theorem has a constructive proof. 2) even with a constructive proof, merely implementing it may not give you a useful algorithm concerning computational efficiency. A lot of work in symbolic computations is to improve the efficiency. To do this, I believe one needs a good background in computer science which is a deviation from your primary goal in most of the time. $\endgroup$
    – Youngsu
    Jul 18, 2017 at 8:44
  • $\begingroup$ Math is necessary to provide the existence of an algorithm (Most of the time by showing termination). So, it needs to consider the worse case. In reality, most of us do not deal with the extreme cases. Hence, it is a question of how to balance the generality and efficiency. $\endgroup$
    – Youngsu
    Jul 18, 2017 at 8:44

2 Answers 2

Reset to default
8
$\begingroup$

Thank you for the interesting and carefully formulated question, and for the details on your background. Your situation is not uncommon - with the growth of computational disciplines (computational biology/chemistry/physics/etc., bioinformatics, digital humanities, etc.) many researchers have to learn programming on the job, without any formal training during their degree studies. Below I will try to give some advice applicable to computational algebra. After reading the 1st two paragraphs, I thought that the answer would go beyond merely recommending a book, and indeed you have already anticipated some further directions in your questions.

In principle, one could be a researcher in algorithms without doing any actual programming. For example, one could study complexity of algorithms and their asymptotic behaviour which will be beyond any feasible computer implementations. On the other hand, programming skill would be an advantage. It may help in understanding how to present algorithms for their practical implementations, or to find worst case performance examples; it may allow to play with things to check facts and better understand the theory, and to find examples and counterexamples. So I support very much your intention.

Now on the specific questions.

Is it important to have a book focusing on one CAS explicitly?

No, it's not. A book dedicated to a particular CAS may not even exist in a relevant area. Books are certainly important, but not only they. Theoretical descriptions in the textbook could be quite high-level and not hinting at subtle aspects of their practical implementation. Code provided with textbooks may not run in the next version of the software. It is also important to look at manuals, teaching materials, comments in the code, or the code itself (provided the system is open source).

Which CAS should I decide for?

It depends on your area of research, on problem(s) which you'd like to work on, and on availability on the relevant functionality in appropriate CAS. An important factor is being open source. Besides CAS, I recommend to learn at least one general purpose programming language, for example Python. It has a large community and a plenty of teaching materials available. If you may need to learn several CAS, it's better to start to learn with the one which has a less steep learning curve, seems more usable, has active community, accessible teaching materials, etc. You may want to look at Singular, Macaulay2, GAP, SageMath, ...

Where does the programming experience come from?

Reading existing code, preferably short and documented functions, is useful, but it's not enough. As Brian Kernighan and Dennis Ritchie said in the first edition of The C Programming Language in 1978, "The only way to learn a new programming language is by writing programs in it.". You need to actually practice in writing your own code. Take some algorithm and try to implement it from scratch. Check that the result matches theory and/or existing implementation. Indeed, why not to try to implement the Buchberger algorithm in Singular? You will not have to re-implement everything since Singular will supply you with polynomials, so you will start with some higher level, and will learn a lot about its functionality in the process. Even if it will be not performing so well as the Singular's one, that would be a good exercise (Note that GAP also has a Groebner basis implementation, although it's not performing as good as the Singular's one).

How to check if I have written good code?

I would reformulate it as "How to learn to write a good code" at try to use some good practices from the beginning. You can find some useful tips looking for reports from various "What makes good code good" discussions on the Software Sustainability Institute website here (for example, see here and there). I recommend to attend some Software Carpentry workshop to learn more about these practices. A typical workshop for beginners does not require prior knowledge of the tools used, lasts about two days, and covers UNIX shell, version control and programming with one of the languages (see the list of lessons here). It is "programming with language", not "programming in language", since the emphasis is on general programming practices, being taught with the help of a particular language. You can check for the future workshops in your region here.

In addition, it's useful to follow mailing lists and Q&A sites for CAS of your interest, get in touch with the community of its users and developers (for example, at events like GAP days or SageMath days or at training events like such training schools). If the system has an issue tracker, perhaps some issues are labeled as newcomer-friendly (like we do in GAP here) so you may try to work on them and then get some feedback from developers.

I hope this helps - please ask if you'd like to discuss this further!

$\endgroup$
3
1
$\begingroup$

There is no book that covers all the aspects of computer algebra, not even a book that adequately covers more than one aspect. That is to say, in no particular order one has here:

  1. Commutative algebra/classical algebraic geometry
  2. Computational group theory
  3. Computational number theory
  4. Symbolic calculus, e.g. symbolic integration
  5. Computational real algebraic geometry: moment methods, numeric homotopy methods, ...
  6. ...

All these topics are interconnected and some of them are very diverse and involved by themselves, e.g. 2) consists of algorithms for permutation groups, for finitely presented groups, for representation theory, for soluble groups, for p-groups...

With your background, I'd start with Macaulay2 and the available online book, which would give you some idea about 1).

$\endgroup$
1

You must log in to answer this question.