Project

General

Profile

Feature #1035

Improvement: how to sort QuotientBasis?

Added by Anna Maria Bigatti about 7 years ago. Updated over 6 years ago.

Status:
Closed
Priority:
Normal
Assignee:
John Abbott
Category:
Improving
Target version:
CoCoALib-0.99560
Start date:
28 Mar 2017
Due date:
% Done:

100%

Estimated time:
0.77 h
Spent time:
0.75 h

Description

QuotientBasis returns a list of power-products ordered by increasing lex (independently of the ordering in the ring).
This is slightly confusing for a human user.
However, calling sorted(QB) may tak considerably longer (100x) than computing the QB itself.

Can we make a sorted version without too much overhead? and/or make a new function SortedQuotientBasis(I) faster than sorted(QuotientBasis(I))?

History

#1 Updated by Anna Maria Bigatti about 7 years ago

  • Target version set to CoCoALib-0.99560

#2 Updated by John Abbott about 7 years ago

  • Status changed from New to In Progress
  • % Done changed from 0 to 10
First we should decide what the public interface is to be.
  • One possibility is to have 2 fns QuotientBasis and QuotientBasisSorted
  • another possibility is to have an optional 2nd arg QuotientBasis(I) and QuotientBasis(I, InIncreasingOrder)

A first impl of the "sorted" version should simply call the unsorted version, and then sort the result. It might be slow, but will surely be correct.

A probably better way to implement the "sorted" version is to replace all calls to "concat" by calls to merge (after checking that the args to merge are correctly ordered themselves). I've no idea how much faster that might be than simply sorting the result of the original impl. The main problem seems to be that there would be considerable duplication of code :-(

#3 Updated by John Abbott over 6 years ago

As far as I can tell QuotientBasisSorted is already implemented in CoCoA-5.
Should it be moved into CoCoALib?

Since C++ has a sort fn, this ought to be very easy... (famous last words?)

#4 Updated by John Abbott over 6 years ago

  • Status changed from In Progress to Feedback
  • Assignee set to John Abbott
  • % Done changed from 10 to 90
  • Estimated time set to 0.77 h

I have just moved the impl from CoCoALibSupplement.C (what was it doing there?!?) to SparsePolyRing.C

There is already CoCoA-5 doc.
I have written 1 line of doc for CoCoA-5 ; strangely this is in ideal.txt even though the source code is in SparsePolyRing.C

Should there be an example (or test) separate from that for QuotientBasis?

#5 Updated by John Abbott over 6 years ago

  • Status changed from Feedback to Closed
  • % Done changed from 90 to 100

Also available in: Atom PDF