Optimize AdditiveMonoids sum() method #39726

user202729 · 2025-03-17T09:05:16Z

Previously the example shown takes way too long. Now it takes 0.5s.

It is probably possible to optimize further by specialize it using Singular.

Opinion: how should the iterator multiplication be implemented

as is (disadvantage: slightly misleading method name),
copy paste the code logic of iterator_prod and make a new method iterator_sum (disadvantage: code duplication),
make an internal method _iterator_combine that takes bint multiply, then make iterator_prod and iterator_sum call it (disadvantage: potential slower branching each operation, but should be negligible)

📝 Checklist

The title is concise and informative.
The description explains in detail what this PR is about.
I have linked a relevant issue or discussion.
I have created tests covering the changes.
I have updated the documentation and checked the documentation preview.

⌛ Dependencies

github-actions · 2025-03-17T11:02:30Z

Documentation preview for this PR (built with commit accd7cd; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

tscrim

LGTM modulo one doc tweak.

src/sage/misc/misc_c.pyx

tscrim · 2025-05-19T06:48:47Z

Also, perhaps as a followup, the linear_combination method of ModulesWithBasis should get a similar treatment (with perhaps somehow a cost function trying to minimize the support)?

Co-authored-by: Travis Scrimshaw <clfrngrown@aol.com>

tscrim

Thank you. LGTM.

user202729 · 2025-05-19T11:46:51Z

I think this one is already using sum which should delegate to the correct thing.

src/sage/categories/modules.py:

		def linear_combination(self, iter_of_elements_coeff, factor_on_left=True):
			r"""
			Return the linear combination `\lambda_1 v_1 + \cdots +
			\lambda_k v_k` (resp.  the linear combination `v_1 \lambda_1 +
			\cdots + v_k \lambda_k`) where ``iter_of_elements_coeff`` iterates
			through the sequence `((\lambda_1, v_1), ..., (\lambda_k, v_k))`.

			INPUT:

			- ``iter_of_elements_coeff`` -- iterator of pairs
			  ``(element, coeff)`` with ``element`` in ``self`` and
			  ``coeff`` in ``self.base_ring()``

			- ``factor_on_left`` -- (optional) if ``True``, the coefficients
			  are multiplied from the left; if ``False``, the coefficients
			  are multiplied from the right

			EXAMPLES::

				sage: m = matrix([[0,1], [1,1]])										# needs sage.modules
				sage: J.<a,b,c> = JordanAlgebra(m)										# needs sage.combinat sage.modules
				sage: J.linear_combination(((a+b, 1), (-2*b + c, -1)))					# needs sage.combinat sage.modules
				1 + (3, -1)
			"""
			if factor_on_left:
				return self.sum(coeff * element
								for element, coeff in iter_of_elements_coeff)
			else:
				return self.sum(element * coeff
								for element, coeff in iter_of_elements_coeff)

We may also want to optimize this thing though.

sage: sum
<function symbolic_sum at 0x736bc1498400>

Using weights may make it a bit faster, but I don't think it is too useful in practice and requires extra API guarantee of subclasses. (In fact the binary splitting already guarantee $O(n \log n)$ worst case performance, so we're only $O(\log n)$ factor away from the optimal in the worst case since lower bound is $Ω(n)$)

tscrim · 2025-05-19T12:20:17Z

I don’t think it will be easy to optimize the symbolic sum (the sumbolic?) since it needs to do a lot of preprocessing/delegation. (That being said, +1 if you’re able to do it.)

Ah, right. I was thinking more of the blas_dict, which is called from the CombinatorialFreeModule implementation version. This is used in a lot of linear algebra computations since a lot of algebras are based on this class/framework, and relatively little time has been spent trying to optimize that.

user202729 · 2025-05-19T12:24:39Z

Looking at the source code of that…

cpdef dict sum(dict_iter):
    r"""
    Return the pointwise addition of dictionaries with coefficients.

    INPUT:

    - ``dict_iter`` -- iterator of dictionaries whose values are in
      a common ring and all values are nonzero

    OUTPUT:

    - a dictionary containing all keys of the dictionaries in ``dict_list``
      with values being the sum of the values in the different dictionaries
      (keys with zero value are omitted)

    EXAMPLES::

        sage: import sage.data_structures.blas_dict as blas
        sage: D = {0: 1, 1: 1}; D
        {0: 1, 1: 1}
        sage: blas.sum(D for x in range(5))
        {0: 5, 1: 5}

        sage: D1 = {0: 1, 1: 1}; D2 = {0: -1, 1: 1}
        sage: blas.sum([D1, D2])
        {1: 2}

        sage: blas.sum([{}, {}, D1, D2, {}])
        {1: 2}
    """
    cdef dict result = {}
    cdef D

    for D in dict_iter:
        if result:
            iaxpy(1, D, result, remove_zeros=False)
        elif D:
            result = D.copy()

    return remove_zeros(result)

cpdef dict linear_combination(dict_factor_iter, bint factor_on_left=True):
    r"""
    Return the pointwise addition of dictionaries with coefficients.

    INPUT:

    - ``dict_factor_iter`` -- iterator of pairs ``D``, ``coeff``, where

      * the ``D``'s are dictionaries with values in a common ring
      * the ``coeff``'s are coefficients in this ring

    - ``factor_on_left`` -- boolean (default: ``True``); if ``True``,
      the coefficients are multiplied on the left, otherwise they are
      multiplied on the right

    OUTPUT:

    - a dictionary containing all keys of dictionaries in ``dict_list``
      with values being the sum of the values in the different
      dictionaries and each one first multiplied by the given factor
      (keys with zero value are omitted)

    EXAMPLES::

        sage: import sage.data_structures.blas_dict as blas
        sage: D = { 0:1, 1:1 }; D
        {0: 1, 1: 1}
        sage: blas.linear_combination( (D,i) for i in range(5) )
        {0: 10, 1: 10}
        sage: blas.linear_combination( [(D,1), (D,-1)] )
        {}
    """
    cdef dict result = {}
    cdef dict D

    for D, a in dict_factor_iter:
        if not a:  # We multiply by 0, so nothing to do
            continue
        if not result and a == 1:
            result = D.copy()
        else:
            iaxpy(a, D, result, remove_zeros=False)

    return remove_zeros(result)

So in the most common case where operations on the base ring takes constant time, this is already the best we can do. It probably won't show up too much in practice.

(meanwhile looking at the code I notice #40127)

tscrim · 2025-05-19T13:04:15Z

Here, since it is implement sparsely as a dict, we would want to minimize the support of the vectors, which minimizes the number of base ring operations. So it feels like it could matter, right? (Ideally, we would know ahead of time that a coefficient would be 0 or not, but that is basically impossible.)

user202729 · 2025-05-19T19:20:19Z

No? The current implementation is such that:

let $A_1,…, A_n$ be the elements in dict_factor_iter,
for each $1 ≤ i ≤ n$, let $K_i$ be the set of keys of $A_i$,
define $K = ⋃_{i=1}^n K_i$,
for $k ∈ K$, let $n(k)$ be the number of $i$ such that $k ∈ K_i$,
then the number of base ring operations is $∑_{k ∈ K} (n(k)-1)$ regardless of the ordering of the elements.

You cannot do better than this for generic values, right?

tscrim · 2025-05-20T05:21:31Z

I'm not quite convinced. I feel like the same argument could be made for this PR, where is clearly is having an effect. For dense vectors, then I agree it would likely have no discernible effect.

If we had a clairvoyant daemon that could do the sums using as few overlapping supports as possible, then it would be faster as we simply need to update the dicts. As an approximation without doing a bunch of preprocessing, we add things with small supports first.

Additionally we can also simply take the larger dict as a base to minimize the number of additions and for-loop-iterations.

For the linear combinations, we could group things with the same coefficient to minimize the number of multiplications in the base ring, which could be relatively expensive. This is likely a speedup asymptotically, but not sure if it is worthwhile to implement.

user202729 · 2025-05-20T06:56:52Z

I'm not quite convinced. I feel like the same argument could be made for this PR, where is clearly is having an effect. For dense vectors, then I agree it would likely have no discernible effect.

No, in this PR then:

the base ring is itself sparse (thus one a+b operation takes time O(len a+len b)), and
the operation a+=b also need to copy a because of immutability.

If however a+=b takes time O(len b), then summing in whichever order only take linear time. Which is the case of sparse dict, constant-time addition in base ring, and the current implementation.

user202729 · 2025-05-20T06:58:24Z

This is likely a speedup asymptotically

Assume hash/dictionary lookup etc. is slow it would backfire though.

Whether it's an asymptotic improvement… maybe, I'll need to think about it.

sagemathgh-39726: Optimize AdditiveMonoids sum() method Previously the example shown takes way too long. Now it takes 0.5s. It is probably possible to optimize further by specialize it using Singular. Opinion: how should the iterator multiplication be implemented * as is (disadvantage: slightly misleading method name), * copy paste the code logic of `iterator_prod` and make a new method `iterator_sum` (disadvantage: code duplication), * make an internal method `_iterator_combine` that takes `bint multiply`, then make `iterator_prod` and `iterator_sum` call it (disadvantage: potential slower branching each operation, but should be negligible) ### 📝 Checklist  - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [x] I have created tests covering the changes. - [x] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies    URL: sagemath#39726 Reported by: user202729 Reviewer(s): Travis Scrimshaw, user202729

sagemathgh-40126: Simplify QuiverRep_generic.linear_combination_of_basis method Shorten the code. This might become faster after sagemath#39726 (or might not, I haven't benchmarked) ### 📝 Checklist  - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies    URL: sagemath#40126 Reported by: user202729 Reviewer(s): Travis Scrimshaw

sagemathgh-39726: Optimize AdditiveMonoids sum() method Previously the example shown takes way too long. Now it takes 0.5s. It is probably possible to optimize further by specialize it using Singular. Opinion: how should the iterator multiplication be implemented * as is (disadvantage: slightly misleading method name), * copy paste the code logic of `iterator_prod` and make a new method `iterator_sum` (disadvantage: code duplication), * make an internal method `_iterator_combine` that takes `bint multiply`, then make `iterator_prod` and `iterator_sum` call it (disadvantage: potential slower branching each operation, but should be negligible) ### 📝 Checklist  - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [x] I have created tests covering the changes. - [x] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies    URL: sagemath#39726 Reported by: user202729 Reviewer(s): Travis Scrimshaw, user202729

sagemathgh-40126: Simplify QuiverRep_generic.linear_combination_of_basis method Shorten the code. This might become faster after sagemath#39726 (or might not, I haven't benchmarked) ### 📝 Checklist  - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies    URL: sagemath#40126 Reported by: user202729 Reviewer(s): Travis Scrimshaw

sagemathgh-39726: Optimize AdditiveMonoids sum() method Previously the example shown takes way too long. Now it takes 0.5s. It is probably possible to optimize further by specialize it using Singular. Opinion: how should the iterator multiplication be implemented * as is (disadvantage: slightly misleading method name), * copy paste the code logic of `iterator_prod` and make a new method `iterator_sum` (disadvantage: code duplication), * make an internal method `_iterator_combine` that takes `bint multiply`, then make `iterator_prod` and `iterator_sum` call it (disadvantage: potential slower branching each operation, but should be negligible) ### 📝 Checklist  - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [x] I have created tests covering the changes. - [x] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies    URL: sagemath#39726 Reported by: user202729 Reviewer(s): Travis Scrimshaw, user202729

sagemathgh-40126: Simplify QuiverRep_generic.linear_combination_of_basis method Shorten the code. This might become faster after sagemath#39726 (or might not, I haven't benchmarked) ### 📝 Checklist  - [x] The title is concise and informative. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies    URL: sagemath#40126 Reported by: user202729 Reviewer(s): Travis Scrimshaw

Optimize AdditiveMonoids sum() method

a6290fe

github-actions bot added the s: needs review label Mar 17, 2025

user202729 added 4 commits March 27, 2025 10:47

Merge remote-tracking branch 'upstream/develop' into optimize-monoid-sum

0fe3f5e

Merge remote-tracking branch 'upstream/develop' into optimize-monoid-sum

e826e3c

Merge remote-tracking branch 'upstream/develop' into optimize-monoid-sum

f23d081

Merge remote-tracking branch 'upstream/develop' into optimize-monoid-sum

d6cdb76

tscrim approved these changes May 19, 2025

View reviewed changes

src/sage/misc/misc_c.pyx Outdated Show resolved Hide resolved

Apply suggested changes

accd7cd

Co-authored-by: Travis Scrimshaw <clfrngrown@aol.com>

tscrim approved these changes May 19, 2025

View reviewed changes

tscrim added s: positive review and removed s: needs review labels May 19, 2025

user202729 mentioned this pull request May 19, 2025

Simplify QuiverRep_generic.linear_combination_of_basis method #40126

Merged

5 tasks

vbraun merged commit 61806aa into sagemath:develop Jun 1, 2025
19 of 25 checks passed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

Optimize AdditiveMonoids sum() method #39726

Optimize AdditiveMonoids sum() method #39726

Uh oh!

user202729 commented Mar 17, 2025 •

edited

Loading

Uh oh!

github-actions bot commented Mar 17, 2025 •

edited

Loading

Uh oh!

tscrim left a comment

Uh oh!

Uh oh!

tscrim commented May 19, 2025

Uh oh!

tscrim left a comment

Uh oh!

user202729 commented May 19, 2025

Uh oh!

tscrim commented May 19, 2025

Uh oh!

user202729 commented May 19, 2025 •

edited

Loading

Uh oh!

tscrim commented May 19, 2025

Uh oh!

user202729 commented May 19, 2025

Uh oh!

tscrim commented May 20, 2025

Uh oh!

user202729 commented May 20, 2025

Uh oh!

user202729 commented May 20, 2025

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Optimize AdditiveMonoids sum() method #39726

Optimize AdditiveMonoids sum() method #39726

Uh oh!

Conversation

user202729 commented Mar 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

📝 Checklist

⌛ Dependencies

Uh oh!

github-actions bot commented Mar 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tscrim left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

tscrim commented May 19, 2025

Uh oh!

tscrim left a comment

Choose a reason for hiding this comment

Uh oh!

user202729 commented May 19, 2025

Uh oh!

tscrim commented May 19, 2025

Uh oh!

user202729 commented May 19, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tscrim commented May 19, 2025

Uh oh!

user202729 commented May 19, 2025

Uh oh!

tscrim commented May 20, 2025

Uh oh!

user202729 commented May 20, 2025

Uh oh!

user202729 commented May 20, 2025

Uh oh!

Uh oh!

Uh oh!

user202729 commented Mar 17, 2025 •

edited

Loading

github-actions bot commented Mar 17, 2025 •

edited

Loading

user202729 commented May 19, 2025 •

edited

Loading