CoCoA » CoCoALib

d'Ali` has completed a first impl of Bernardin's algorithm.
Ported to C5 by JAA. Tests taken from Bernardin's paper all pass.

D'Ali` has almost finished refinement and testing of his impl of Bernardin's algm.
He will check the details about the assumption of primitivity -- our tests suggest that it may not be necessary for correctness (but it might be beneficial for speed of computation).

Execution times do display some unexpected variation; the source of this strange behaviour is not yet known (how does C5 compute GCDs in ZZ/(p)[x,y,z]?)

Explained peculiar variation noted last time: simply that some of the test cases were much denser modulo certain primes than modulo other primes.

D'Ali` has also implemented the case for characteristic 0. Execution speed is competitive with the built-in "factor" command for univariate polynomials; D'Ali`'s implementation is significantly faster for multivariate inputs (in QQ[x,y]). RECALL also that the built-in factor command is working with DUPZ polynomials while D'Ali`'s code was computing with multivariate polynomials and rational coefficients!!

The case of degree 0 inputs must be handled -- a simple initial check suffices.

D'Ali` has completed an initial verification that the precondition that the input be primitive is apparently unnecessary. He will write up his analysis in LaTeX (possibly to be sent to ACM Communications in Computer Algebra?)

JAA has been writing a short note where he uses a more flexible definition of sqfr factorization which allows any refinement of the standard sqfr factorization. D'Ali` commented that Bernardin's algorithm does sometimes multiply together factors which had been separated. Using the wider definition, these multiplications can be skipped. D'Ali` will check whether the algorithm can easily be modified so that it performs only those products strictly necessary.

D'Ali` will also modify the implementation so that input polynomials are split into primitive parts. We are now fairly sure this is not necessary for correctness, but expect that it will improve execution speed in some cases (without causing significant slowing in other cases).

John Abbott wrote:

D'Ali` has also implemented the case for characteristic 0. Execution speed is competitive with the built-in "factor" command for univariate polynomials; D'Ali`'s implementation is significantly faster for multivariate inputs (in QQ[x,y]).

JAA reports trouble reproducing the "comparable speed" result; the last tests indicate that the builtin "factor" command is at least 10 times faster. JAA will investigate!

Addendum: timing varies depending on the ring, just compare the following:

In a BIVARIATE ring

Use QQ[x,y];
f := (x^2+3)^11 * (x^2+2*x+3)^5 * (x^3+3*x^2+3*x+3)^3;
t0:=CpuTime(); f1024 := f^64; PrintLn "Time to compute power: ", DecimalStr(CpuTime()-t0);

t0:=CpuTime(); Squarefree(f1024); PrintLn "Time to compute sqfr: ", DecimalStr(CpuTime()-t0);
t0:=CpuTime(); factor(f1024); PrintLn "Time to compute factor: ", DecimalStr(CpuTime()-t0);

Time to compute sqfr: 7.911
...
Time to compute factor: 3.215

Same example in a UNIVARIATE ring

Time to compute sqfr: 34.927
...
Time to compute factor: 3.119

Anna thinks strange behaviour is due to the way GCDs are computed in poly rings.

• handles case f=0 --> gives error
• handles case f=const --> appears as factor with mult=1 (should be unfactored part)
• new algm Squarefree2 avoids multiplying together separated factors having the same multiplicity (algm is simpler, but seems to be slightly slower?!?)
• algm seems to be unacceptably slow over QQ -- JAA suspects that this is due to slow gcd, he will investigate.

1. investigate whether there is a "clever" way to choose the order in which the indets are to be considered
2. investigate the effect of primitivization on speed of computation (order of indets?)
3. JAA will make the C4 "fast" gcd available in CoCoALib+CoCoA5

Alessio and John have both implemented content free factorization.
The CoCoALib impl is slightly faster -- but we ran just 1 test case.
Alessio's impl of Bernardin's algm for sqfree factorization was much faster than either of the content free impls (on the same single test case).

Alessio has a second impl of content free factorization (in primitivization3.cocoa5); it was about twice as slow as his "easy" impl.

Alessio may look at the effects of considering the indets in different orders with the hope of find a simple way of choosing the best order.

He will proceed with the LaTeX report about Bernardin's algm not requiring the input to be primitive.

He will also look over his (best) impl of Bernardin's algm with the aim of making it as clean as possible.

Alessio has not found any criterion for a good order in which to "eliminate" the indets.

He did suggest offering an interface which allows the user to specify the order (otherwise the code makes some choice of order, probably increasing indet index).

Alessio did construct at least one family of polynomials which show that some simple criterions do not work in general.

He will write a report summarising his findings.

He also did some code cleaning. We did some more during the meeting.

Alessio has a first solid version of his report.
We spoke of how to generate tables of timings automatically; Alessio will try to produce a CoCoA program for generating the tables.

• continued with the report
• reorganized the tests so that they are largely automatic

He will check whether make primitive then do sqfr is the same as applying sqfr directly; ideally we want a proof or some counter-examples.

Next meeting 14:30 on wed 2012-07-11 (might possibly slip one day).

Next meeting will be in September; exact day still to be decided.

Alessio has produced two prototype implementations in CoCoA: one computes the square "in place", the other produces a new polynomial. The polynomials are actually represented as vectors of coefficients. The study is to help the revised impl of univariate polys over small finite fields (see #127).

The "in place" code is significantly more complicated, and seems to be about the same overall speed.

Testing has highlighted some curious (& undesirable) behaviour of the CoCoA interpreter, e.g. doubling the degree causes the computation time to increase by rather more than a factor of 4.

Testing has highlighted some curious (& undesirable) behaviour of the CoCoA interpreter, e.g. doubling the degree causes the computation time to increase by rather more than a factor of 4.

maybe this is related with issue "theValue makes copies"