Improve libsingular's polynomial construction

[nbruin]

This sage-support report observes that construction of libsingular polynomials from a dictionary (which is what pickle does) can be very slow, and can be beaten by constructing smaller polynomials and summing those together. Illustration of the problem:

def balanced_sum(L):
    if len(L)==0:
        raise ValueError("balanced sum takes a non-empty list")
    i=0
    while len(L)>1:
        L[i]+=L.pop()
        i+=1
        if i>=len(L)-1: i=0
    return L[i]

R.<x0,x1,x2,x3>=QQ[]
f=(x0+x1+x2+x3)^40 #has 12341 terms
D=f.dict()
L=[{k:v} for k,v in D.items()]
%timeit R(D) # 378 ms for me
%timeit balanced_sum([R(t) for t in L]) #139 ms for me

Is this just a matter of balanced summing or can we make this even more efficient? We should just be writing the polynomial in-place. We know the length of the dict, so we know for how many terms we need to reserve memory.

I also noted that in MPolynomialRing_libsingular._element_constructor_ we are dealing with the case MPolynomial_polydict twice: on line 819 and then again on line 920.

CC: @simon-king-jena

Component: algebra

Issue created by migration from https://trac.sagemath.org/ticket/27091

[nbruin]

comment:1

I'm not particularly planning to work on this. Feel free to take it up!

[embray]

comment:3

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[embray]

comment:4

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).