Project

General

Profile

Slug #1057

Slug: Polynomial ring contructor slow with (big) matrix ordering

Added by Anna Maria Bigatti almost 7 years ago. Updated about 1 month ago.

Status:
In Progress
Priority:
High
Assignee:
Anna Maria Bigatti
Category:
Improving
Target version:
CoCoALib-0.99880
Start date:
04 May 2017
Due date:
% Done:

50%

Estimated time:
8.00 h
Spent time:
5.70 h

Description

I have an example which shows that creating a SparsePolyRing with matrix ordering is slower than default ordering.

Related issues

Related to CoCoA-5 - Slug #1047: NewPolyRing with user defined ordering is slower than CoCoALibClosed2017-04-18

Related to CoCoALib - Slug #1049: GroebnerFan: slow examplesIn Progress2017-04-19

Related to CoCoA-5 - Slug #1068: PolyRing constructor: NewOrdvArith computed twiceIn Progress2017-05-17

Related to CoCoALib - Design #841: NewPolyRing: tidy up the many different versionsIn Progress2016-01-21

Related to CoCoALib - Feature #1197: IsZeroDet: new fnIn Progress2018-06-26

Related to CoCoALib - Slug #1588: ElimMat is slowNew2021-04-15

Related to CoCoALib - Bug #1641: gcd does not recognize univariate input Closed2021-12-20

Related to CoCoALib - Design #1798: Computing in sub polyringNew2024-03-22

History

#1 Updated by Anna Maria Bigatti almost 7 years ago

  • % Done changed from 0 to 10

(The example is cvs-ed in the dir IdealsModp)
I had added a ludicrous number of (unused) indeterminates: the computation speed seems good,
I believe the cost is in checking the matrix ordering, so I should investigate that part.

If the check is intrinsically slow, I could design a way to pass the matrix from a ring to a new ring (for GB operations) without further checks.

#2 Updated by Anna Maria Bigatti almost 7 years ago

  • Description updated (diff)

#3 Updated by Anna Maria Bigatti almost 7 years ago

  • Related to Slug #1047: NewPolyRing with user defined ordering is slower than CoCoALib added

#4 Updated by Anna Maria Bigatti almost 7 years ago

  • Related to Slug #1049: GroebnerFan: slow examples added

#5 Updated by Anna Maria Bigatti almost 7 years ago

  • Related to Slug #1068: PolyRing constructor: NewOrdvArith computed twice added

#6 Updated by Anna Maria Bigatti almost 7 years ago

  • Subject changed from Slug: Polynomial ring with matrix ordering to Slug: Polynomial ring contructor slow with (big) matrix ordering
  • Status changed from New to In Progress
  • % Done changed from 10 to 30

First problem found: NewOrdvArith(ord) ic computed twice.
If ord is defined by M, then many checks are done on M.

#7 Updated by Anna Maria Bigatti almost 7 years ago 

  SparsePolyRing NewPolyRing(const ring& CoeffRing, const PPMonoid& PPM)
  {
    return NewPolyRing_DMP(CoeffRing, PPM);// the only one for DMP
    // !!! ANNA: but if PPM is PPMonoidOv we could be clever!!!
  }

#8 Updated by Anna Maria Bigatti over 6 years ago

  • Related to Design #841: NewPolyRing: tidy up the many different versions added

#9 Updated by John Abbott over 6 years ago

  • Target version changed from CoCoALib-0.99560 to CoCoALib-0.99600

#10 Updated by Anna Maria Bigatti over 5 years ago

  • Target version changed from CoCoALib-0.99600 to CoCoALib-0.99650 November 2019

#11 Updated by John Abbott about 5 years ago

#12 Updated by John Abbott over 4 years ago

  • Target version changed from CoCoALib-0.99650 November 2019 to CoCoALib-0.99800

#13 Updated by John Abbott about 3 years ago

#14 Updated by John Abbott about 3 years ago

Here is a benchmark (since there was none given earlier:

/**/ t0 := CpuTime(); M := ElimMat(1..250,500); TimeFrom(t0);
58.731   --->  see issue 1588
/**/ t0 := CpuTime(); P := NewPolyRing(QQ, SymbolRange("x",1,500), M, 0); TimeFrom(t0);
6.403

Since we know that M is already a good matrix, it is surprising that NewPolyRing takes more than 6s (on my linux box).
Surely it suffices to check that M is square with integer entries, has non-zero det, and that the first non-zero in each col is positive?

#15 Updated by John Abbott about 2 years ago

  • Target version changed from CoCoALib-0.99800 to CoCoALib-0.99850

The first line in commenrt 10 above is still about 50s... too slow!
How long does it take to compute the det of a 500x500 matrix?
We need that IsZeroDet function!

#16 Updated by John Abbott about 2 months ago

We now have a first impl of IsZeroDet. Hopefully this will help!

#17 Updated by Anna Maria Bigatti about 2 months ago

  • % Done changed from 30 to 50

John Abbott wrote:

Here is a benchmark (since there was none given earlier:

Much better now with IsZeroDet. On my computer it is

/**/ t0 := CpuTime(); M := ElimMat(1..250,500); TimeFrom(t0);
48.822
/**/ t0 := CpuTime(); P := NewPolyRing(QQ, SymbolRange("x",1,500), M, 0); TimeFrom(t0);
1.160

But I still want to investigate why it calls twice NewOrdvArith(ord) and IsTermOrdering 3 times.

#18 Updated by Anna Maria Bigatti about 1 month ago

  • Related to Bug #1641: gcd does not recognize univariate input added

#19 Updated by John Abbott about 1 month ago

  • Target version changed from CoCoALib-0.99850 to CoCoALib-0.99880

#20 Updated by John Abbott about 1 month ago

  • Priority changed from Normal to High
  • Target version changed from CoCoALib-0.99880 to CoCoALib-0.99850

#21 Updated by Anna Maria Bigatti about 1 month ago

#22 Updated by John Abbott about 1 month ago

  • Target version changed from CoCoALib-0.99850 to CoCoALib-0.99880

Also available in: Atom PDF