Project

General

Profile

Slug #842

PPMonoidSparse: comparisons are VERY SLOW

Added by John Abbott about 8 years ago. Updated about 8 years ago.

Status:
New
Priority:
Normal
Assignee:
-
Category:
Improving
Target version:
CoCoALib-1.0
Start date:
15 Feb 2016
Due date:
% Done:

0%

Estimated time:
Spent time:
1.00 h

Description

I have just tried with Mario to use PPMonoidSparse rather than a normal dense repr (for a PPM with about 100 indets). The sparse impl was about 200 times slower than the dense one.

Profiling showed that PPMonoidSparse::myCmpOrdvs was the culprit.

Related issues

Related to CoCoALib - Feature #800: PPMonoidSparse: impl of sparse PPsClosed2015-11-09

History

#1 Updated by John Abbott about 8 years ago

  • Related to Feature #800: PPMonoidSparse: impl of sparse PPs added

#2 Updated by John Abbott about 8 years ago

I have created a temporary hack to the code for the special case of lex ordering. Essentially I have written a new fn myCmpLex; this largely solved the problem of low speed (not as well as I had hoped, but still good enough for Mario to proceed).

PPMonoidSparse::myCmpOrdvs is very "clean" but also understandably very slow (e.g. it always performs a matrix-vector product using BigInt arithmetic).

We should try to make the code work better for the most common cases.

Also available in: Atom PDF