Feature #259
Squarefree(?) GCD-free basis
Description
Hensel lifting for univariate GCDs requires a squarefree GCDfree basis.
There is an implementation in GCDfreeBasis.cpkg5
; convert this to C++.
Needs a good GCD impl to work properly -- sounds like a circular argument!
Related issues
History
#1 Updated by Anna Maria Bigatti almost 10 years ago
- Target version set to CoCoALib-1.0
#2 Updated by John Abbott over 7 years ago
- Category set to New Function
- Status changed from New to In Progress
- % Done changed from 0 to 10
I have written a first version (for RingElem
) by translating almost directly the impl in GCDFreeBasis.cpkg5
. I have not yet tested it, nor even checked it in. It does just the GCDfree part, not the squarefree part.
Note that the CoCoA-5 impl was just for integers; the new one is for any ring elem (in a true GCD domain).
#3 Updated by John Abbott over 7 years ago
- Related to Bug #154: GCD normalization (e.g. monic) added
#4 Updated by John Abbott about 7 years ago
Mostly a wake-up call. There is already an implementation in GCDFreeBasis.C
.
Decide which data-structures to use (principally vector<RingElem>
or some new type).
The "refine" function could actually be a member function.
#5 Updated by John Abbott about 6 years ago
- Status changed from In Progress to Resolved
- % Done changed from 10 to 60
I have impls of GCDFreeBasis for RingElem and for BigInt.
Not yet checked in/ No tests; one simple example.
#6 Updated by John Abbott about 6 years ago
- Assignee set to John Abbott
- % Done changed from 60 to 70
I have checked in the code. There is doc, but no tests.
I am not happy with the class names: GCDFreeBasis_BigInt
and GCDFreeBasis_RingElem
.
Since they are classes the names have to be different (or I could use templates -- awkward in this case).
Also I am slightly unhappy about the root of the name GCDFreeBasis
. In this case "GCDFree" means "coprime", so why not say "coprime"? Also I believe that there is an expression "factor base" rather than "factor basis". So a better root name might be CoprimeFactorBase
. In a sense it is nice to have the substring "Factor" in the name.
Opinions? Ideas? Suggestions?
#7 Updated by John Abbott almost 6 years ago
- Target version changed from CoCoALib-1.0 to CoCoALib-0.99650 November 2019
#8 Updated by John Abbott over 5 years ago
Should GCDFreeBasis_BigInt
and GCDFreeBasis_RingElem
be renamed to CoprimeFactorBasis_BigInt
and CoprimeFactorBasis_RingElem
?
#9 Updated by John Abbott over 5 years ago
- Related to Support #1240: John's visit Feb 2019 added
#10 Updated by John Abbott almost 5 years ago
- Status changed from Resolved to Feedback
- Target version changed from CoCoALib-0.99650 November 2019 to CoCoALib-0.99700
- % Done changed from 70 to 90
I changed the names (not sure when).
A problem with the integer version is that the "squarefree" part is potentially costly to achieve -- I believe it requires factorization.
At the moment I am tempted to skip the "squarefree" guarantee, and say that it is the caller's responsibility.
Anyway is it better to do squarefree factorization and then CoprimeFactorBasis
, or vice versa?
Probably there are situations where one approach is better, and situations where the other is better...
Moved to "feedback".
#11 Updated by John Abbott over 4 years ago
- Status changed from Feedback to Closed
- % Done changed from 90 to 100
- Estimated time set to 10.70 h
These fns were already mentioned in the previous release (0.99650).
Closing after spending 3 months in feedback.