accessing coefficients of a multivariate polynomial f via f[...] or f.coefficient(...) is extremely slow

[maxale]

Steps To Reproduce

In the following set up we create a polynomial f with about 100,000 random terms (with coefficients equal 1) of degree 100 in 8 variables:

sage: IV = IntegerVectors(100,8)
sage: R = PolynomialRing(QQ,8,'x')
sage: x = R.gens()
sage: f = R({IV.random_element():1 for _ in range(10^5)})

Let's sum up the coefficients of f by accessing them via f[...]:

sage: %time sum( f[t.degrees()] for _,t in f )
CPU times: user 4min 41s, sys: 25 ms, total: 4min 41s
Wall time: 4min 41s
100000

We see that these operations take 4min 41s, that is 281 seconds.

Expected Behavior

Almost 5 minutes for a cycle with just 100,000 iterations already look suspicious. Let's show that with a bit of wrapping, we get the same result in about 1 second:

sage: %time D = { t.degrees():c for c,t in f }
CPU times: user 609 ms, sys: 35 ms, total: 644 ms
Wall time: 644 ms

sage: %time sum( D[t.degrees()] for _,t in f )
CPU times: user 418 ms, sys: 999 µs, total: 419 ms
Wall time: 419 ms
100000

Here I first turned f into a dict mapping each term degrees to the corresponding coefficient, and then summed up the coefficients of f in the same way, basically replacing f[t.degrees()], extracting the coefficient from f, with D[t.degrees()] extracting the coefficient from the dictionary instead. As the timing shows, constructing the dictionary D and extracting and summing coefficients from it altogether take about 1 second.

Actual Behavior

I assumed that internally f is represented as a kind-of dictionary with a fast access to the coefficients given a term degrees. However, the above experiments disprove that by showing that accessing coefficients in the standard way is almost 300 times slower than if an actual dictionary was used. Furthermore, as illustrated, this speed-up can be easily achieved in practice.

Additional Information

No response

Environment

- **OS**: Ubuntu 24.04.1 LTS
- **Sage Version**: 10.5.beta2

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide

[mantepse]

I think you want to pass sparse=True to PolynomialRing:

sage: R = PolynomialRing(QQ,8,'x',sparse=True)

[maxale]

@mantepse: I've tested with sparse=True in PolynomialRing, and it gave just about a 2-fold speed-up, which is still unacceptably slow. Also, I believe that access to the coefficients should be fast for both sparse and non-sparse polynomials.

[user202729]

sage: c = [t for _,t in f][0]
sage: %time f[c.degrees()]
CPU times: user 38 µs, sys: 0 ns, total: 38 µs
Wall time: 40.8 µs
1
sage: c = [t for _,t in f][-1]
sage: %time f[c.degrees()]
CPU times: user 329 µs, sys: 0 ns, total: 329 µs
Wall time: 357 µs
1

It iterates through f:

        while p:
            if p_ExpVectorEqual(p, m, r) == 1:
                p_Delete(&m,r)
                return si2sa(p_GetCoeff(p, r), r, self._parent._base)
            p = pNext(p)

There are complaints in similar functions

        # Extract the monomials that match the specifications
        # this loop needs improvement

Singular stores the polynomial internally as a linked list: https://fossies.org/dox/singular-4.4.0p5/monomials_8h_source.html

Then fixing this issue would involve a tradeoff where you in parallel maintain a dictionary of coefficients and the Singular representation, which will kill performance in pretty much everything else.

Perhaps the best thing to do is to add in the documentation "Warning: this method takes linear time in the number of coefficients, unlike __getitem__ method of list, dict and pretty much anything else."