Slug #1588
ElimMat is slow
Description
ElimMat is rather slow for larger inputs:
/**/ t0 := CpuTime(); M := ElimMat(1..50,100); TimeFrom(t0); 0.470 /**/ t0 := CpuTime(); M := ElimMat(1..100,200); TimeFrom(t0); 3.681
Complexity appears to cubic.
Related issues
History
#1
Updated by John Abbott about 3 years ago
Updated by - Related to Slug #1057: Slug: Polynomial ring contructor slow with (big) matrix ordering added
#2
Updated by John Abbott about 3 years ago
My guess is that the code repeatedly calls rank, but we should be able to be "clever" in some common cases.
Is it really worth making the effort? Don't know; hence low priority.
#3
Updated by John Abbott 2 months ago
- Target version changed from CoCoALib-0.99850 to CoCoALib-0.99900
#4
Updated by John Abbott about 1 month ago
I though we had a class for incremental gaussian reduction. That should be useful in this case!
We can also make a much faster impl for the case of normal elim orders with standard grading.