Project

General

Profile

Support #438

Polynomial multiplication (product of RingElem)

Added by John Abbott over 10 years ago. Updated almost 10 years ago.

Status:
In Progress
Priority:
Normal
Assignee:
-
Category:
Various
Target version:
CoCoALib-1.0
Start date:
08 Feb 2014
Due date:
% Done:

10%

Estimated time:
Spent time:
0.50 h

Description

Bruns asks whether f*g and g*f take the same time or whether one way round is better than the other. He mentions the special case of one polynomial actually being a monomial; it probably is worth handling this case specially in the code.

Related issues

Related to CoCoA-5 - Support #242: CoCoA-5 Projects for students (e.g. crediti F and tesi)In Progress2012-09-28

History

#1 Updated by John Abbott over 10 years ago

[from an email sent to Bruns] I do recall that there are complications for inserting the terms in the correct order; a naive implementation has cubic complexity in some cases. One tricky case is f := (x^N-1)/(x-1) and g := subst(f,x,x^N); where N is an integer parameter. Both f and g have N terms, while the product contains N^2 terms. CoCoALib's use of geobuckets should help considerably in any case.

#2 Updated by Anna Maria Bigatti over 10 years ago

  • Status changed from New to In Progress
  • Target version set to CoCoALib-0.99534 Seoul14
  • % Done changed from 0 to 10

In SparsePolyRing.C -- myMul there is this code

    if (IamCommutative() && myNumTerms(rawf) > gLen)
    { myMul(rawlhs, rawg, rawf); return; }

Before it it checks whether one of the two is constant.
I can add the check in case one is a single summand.

#3 Updated by Winfried Bruns over 10 years ago

I think it is a question that needs careful testing before any changes should be done. As observed by John and mentioned in my last mail, the use of the geobucket presumably levels out the differences between F*G and G*F.

#4 Updated by Anna Maria Bigatti over 10 years ago

Winfried Bruns wrote:

I think it is a question that needs careful testing before any changes should be done. As observed by John and mentioned in my last mail, the use of the geobucket presumably levels out the differences between F*G and G*F.

What I meant is that all the work we've been talking about has already been done (2008):
- check if one poly is a constant (and mult is commutative)
- check if one poly is longer (and mult is commutative)
- check if one poly is a single summand (and mult is commutative)
- use geobucket

Only optimization to be done: reorganize code so that myNumTerms is computed fewer times.

#5 Updated by Winfried Bruns over 10 years ago

I am sorry for having raised a non-issue.

Regarding NumTerms: is it a data field of the polynomial or is it computed when asked for?

#6 Updated by John Abbott almost 10 years ago

  • Target version changed from CoCoALib-0.99534 Seoul14 to CoCoALib-1.0

Also available in: Atom PDF