CoCoA » CoCoALib

I have implemented a first improvement by implementing a new fn ReadExprInSparsePolyRing which uses geobuckets to store sums. This has already made quite a big difference (e.g. that big poly now takes 15mins instead of much longer (I don't recall exactly))

I hope to check this in shortly -- the code is fairly simple, so should be safe.

Since my "stupid" MacBook cannot profile, I can only guess that reading a symbol is probably quite costly (see line 79 of RingElemInput.C which calls RingElem to convert the symbol into a RingElem value).

The conversion of a symbol into a RingElem should ideally be done using a std::map. This could be done inside the ring itself, or outside.

Currently it uses a shockingly inefficient technique: each call to RingElem(..., symbol) creates a std::vector, and checks that the symbol is there (error if not). In the case of a SparsePolyRing the actual conversion then recreates the same list of symbols, and checks again if it is there, and if so generates the answer.

The conversion table of symbol-to-ringelem should be created only once; perhaps it is best if this is inside the ring?

I did a quick test:

QQa1 ::= QQ[a];
QQa100 ::= QQ[a[0..99]];

P1 ::= QQa1[x];
P100 ::= QQa100[x];

str := "(x^10000-1)/(x-1) expanded out";
t0 := CpuTime();
j1 := ReadExpr(P1, str);
t1 := CpuTime();

j2 := ReadExpr(P100,str);
t2 := CpuTime();

println "Time to read in P1: ", FloatStr(t1-t0);
println "Time to read in P100: ", FloatStr(t2-t1);

The times recorded were about 0.28s and 1.3s. So the presence of indets which are not used has a significant cost.

For comparison I tried the test again after disabling the improvement describe in comment 1; the times reported were identical! Aha that's because adding a new terms whose PP is smaller than those in the poly is handled specially.

Anyway, for Mario's poly with 84 indets the time dropped from about 17s to 9s.

I have hacked the ReadExpr code so that it produces a table of symbols (of type std::map).
This improved the read time for Mario's poly from about 9s to less than 1s, so it is definitely worth doing.

I believe the clean way to do this is to put the std::map inside the ring; then every call to RingElem(R, sym) will be quick because it can use the symbol table :-) This should also mean that ReadExpr code already in CVS will suddenly become faster.

John Abbott wrote:

I have done a quick profile of the current version of the code (using the ad hoc impl with std::map). Now most (90+%) of the execution time is in DistrMPolyInlPP::myAddClear. I'm now sure how to improve this :-( Yet a further improvement would really be needed.

Is it a very long polynomial? I suppose we then should use in ReadExpr
geobucket f(P); instead of RingElem f(P);

I have already implemented (and checked in) a version which uses geobuckets when the ring is a sparsepolyring.

Mario says his polys are printed out using the standard term ordering (StdDegRevLex presumably).
So maybe just using PushBack will make it faster still. I hope to investigate this evening.

Some polys have more than 100000 terms, and they seem to take several minutes to read.

I reran the test to read Mario's polynomial: now it takes about 0.4s (with the "wrong" term-ordering), and about 0.25 s with the "right" term-ordering (lex in this case).

Probably the case of "wrong" term-ordering would be even faster if the terms were read into separate polynomials (one term in each) in a vector, and then sort the vector, and finally sum the terms.

Note that for larger polys the difference between "wrong" order (degrevlex when the poly was written in lex) and the "right" order is usually much more marked (typically 20-30 times slower).

Using the profiler on a linux box I noticed that DistrMPolyInlPP::myPushFront was using surprisingly much time. I had added this as issue #884.

I wrote an ad hoc reader and writer of polynomials, and observed approximately 5 times speed up (should be more if the myPushFront problem can be improved). Now I wonder whether it is worth developing a better format for communication between processes (sacrificing human-readability); this is what the OpenMath-like interface was for (but it seems implausible that the OpenMath-like XML-based format could be as fast as the simple ad hoc format).