Thanks very much, Guillaume, & Marc! Your profiler sounds like a good idea, and I'll try it. I knew adem.scm, which does the sorting, was the hotspot, and I sorta said so in my README file, e.g.
"admissify takes a term and applies a zillion Adem relations to it in order to make it admissible. ... We're only going to admissify terms (a_1 ... a_s) with say s, a_i < 100. There's a lot of this going on, so it would be nice to do it *very quickly*, but no one admissify should take that long, on our fast machines."
"As far as speed goes, I'm convinced that all the work goes into calc-d, which calls Curtis-alg a reasonable small number of times, but each Curtis-alg can involve a ton of time. Curtis-alg must construct a large simplified sorted polynomial, and keep taking d (which calls admissify), and merging the (d a)'s into the large polynomial. That's what takes the time. My advisor talked about millions of terms here."
Also, you can speed up your code quite a bit simply by adding some declarations in your code. You can read about it in the documentation: http://www.iro.umontreal.ca/~gambit/doc/gambit-c_6.html#IDX153
Now this is just the Gambit Manual, which you can read in Emacs with info files, right? There's not enough info here for me:
These declarations are compatible with the semantics of Scheme. Typically used declarations that enhance performance, at the cost of violating the Scheme semantics, are: (standard-bindings), (block), (not safe) and (fixnum).
That's the only hit in the Manual for the string "(fixnum)". Ah, but I see there's lots of hits for just "fixnum", so I'll read up.
Something like this [say, at the top of 'Curtis-algorithm.scm']:
(declare (standard-bindings) (fixnum) (not safe) (inline) (inlining-limit 1000) (block))
will give you some boost (I assume your numerals are all fixnums, but that might be wrong). Of course there are tradeoffs to doing this, so make sure you understand what those declarations means.
How about I tell you, since I have manual troubles: I have lists of integers a with -1 <= x < 100, and they're not long lists. I call them monomials, or terms. Then I have loooong lists of terms, called polynomials.