Added function ones to DomainMatrix,DDM and SDM class #21106

ks147 · 2021-03-17T09:32:44Z

References to other Issues or PRs

#20987

Brief description of what is fixed or changed

Added a function ones

Release Notes

polys
- added a function ones to DomainMatrix and DDM class

sympy-bot · 2021-03-17T09:33:17Z

✅

Hi, I am the SymPy bot (v161). I'm here to help you write a release notes entry. Please read the guide on how to write release notes.

Your release notes are in good order.

Here is what the release notes will look like:

polys
- added a function ones to DomainMatrix and DDM class (#21106 by @ks147)

This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.9.

Click here to see the pull request description that was parsed.

#### References to other Issues or PRs
#20987 


#### Brief description of what is fixed or changed
Added a function ones 

#### Release Notes

<!-- BEGIN RELEASE NOTES -->
* polys
  * added a function ones to DomainMatrix and DDM class
<!-- END RELEASE NOTES -->

Update

The release notes on the wiki have been updated.

oscarbenjamin · 2021-03-17T22:15:36Z

I guess this should also be implemented for SDM

ks147 · 2021-03-18T05:55:29Z

I guess this should also be implemented for SDM

Sure, I'll do that.

oscarbenjamin · 2021-03-18T11:56:11Z

There should be tests

ks147 · 2021-03-19T15:45:43Z

There should be tests

I'll add them

ks147 · 2021-03-20T06:20:04Z

@oscarbenjamin, could you please review

oscarbenjamin · 2021-03-20T08:58:58Z

sympy/polys/matrices/sdm.py

+        one = domain.one
+        m, n = shape
+        sdm = {i: {j: one for j in range(n)} for i in range(m)}
+        return cls(sdm, shape, domain)


You should run some timings to check this but I would imagine that for a large shape it is quicker to create a dict once and then copy it many times rather than use a dict comprehension for over j for each i:

row = dict(zip(range(n), [one]*n)) sdm = {i: row.copy() for i in range(m)}

I ran some benchmarks

from sympy.polys.matrices.sdm import SDM def ones_new(shape, domain): m, n = shape one = domain.one row = dict(zip(range(n), [one]*n)) sdm = {i: row.copy() for i in range(m)} def ones_current(shape, domain): one = domain.one m, n = shape sdm = {i: {j: one for j in range(n)} for i in range(m)}

from sympy import QQ for i in range(100,1000, 100): %time ok = ones_new((i, i), QQ) CPU times: user 0 ns, sys: 987 µs, total: 987 µs Wall time: 1 ms CPU times: user 601 µs, sys: 1.65 ms, total: 2.25 ms Wall time: 2.27 ms CPU times: user 0 ns, sys: 2.56 ms, total: 2.56 ms Wall time: 2.57 ms CPU times: user 3.04 ms, sys: 4 ms, total: 7.04 ms Wall time: 6.97 ms CPU times: user 0 ns, sys: 6.82 ms, total: 6.82 ms Wall time: 6.78 ms CPU times: user 2.64 ms, sys: 4.69 ms, total: 7.33 ms Wall time: 7.27 ms CPU times: user 0 ns, sys: 14.4 ms, total: 14.4 ms Wall time: 14 ms CPU times: user 11 ms, sys: 9.31 ms, total: 20.3 ms Wall time: 19.8 ms CPU times: user 2.5 ms, sys: 16.2 ms, total: 18.7 ms Wall time: 18.6 ms

for n in range(100, 1000, 100): %time ok = ones_current((n, n), QQ) CPU times: user 1.48 ms, sys: 178 µs, total: 1.66 ms Wall time: 1.67 ms CPU times: user 5.5 ms, sys: 0 ns, total: 5.5 ms Wall time: 5.31 ms CPU times: user 7.18 ms, sys: 0 ns, total: 7.18 ms Wall time: 7.12 ms CPU times: user 13.2 ms, sys: 49 µs, total: 13.2 ms Wall time: 13.2 ms CPU times: user 20.1 ms, sys: 0 ns, total: 20.1 ms Wall time: 19.9 ms CPU times: user 26.5 ms, sys: 0 ns, total: 26.5 ms Wall time: 26.6 ms CPU times: user 21.3 ms, sys: 15.8 ms, total: 37.1 ms Wall time: 37.1 ms CPU times: user 31.7 ms, sys: 12.1 ms, total: 43.8 ms Wall time: 43.8 ms CPU times: user 42.5 ms, sys: 12.5 ms, total: 55 ms Wall time: 55 ms

Your method is a little bit faster

oscarbenjamin · 2021-03-20T12:03:01Z

If you time DomainMatrix.ones here you'll see that it is slow due to converting between SDM and DDM and other checking:

In [12]: %time ok = DomainMatrix.ones((1000, 1000), ZZ)
CPU times: user 710 ms, sys: 50.3 ms, total: 760 ms
Wall time: 769 ms

In [13]: %prun -s cumulative ok = DomainMatrix.ones((1000, 1000), ZZ)
         1009025 function calls in 0.936 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.936    0.936 {built-in method builtins.exec}
        1    0.028    0.028    0.936    0.936 <string>:1(<module>)
        1    0.005    0.005    0.908    0.908 domainmatrix.py:232(ones)
        1    0.000    0.000    0.897    0.897 domainmatrix.py:33(from_rep)
        1    0.000    0.000    0.897    0.897 domainmatrix.py:25(__init__)
        1    0.000    0.000    0.897    0.897 sdm.py:39(from_list)
        4    0.224    0.056    0.516    0.129 {built-in method builtins.all}
        1    0.000    0.000    0.515    0.515 sdm.py:21(__init__)
        1    0.001    0.001    0.381    0.381 sdm.py:46(<dictcomp>)
     1001    0.001    0.000    0.380    0.000 sdm.py:45(<genexpr>)
     1000    0.003    0.000    0.379    0.000 sdm.py:44(<lambda>)
     1000    0.377    0.000    0.377    0.000 sdm.py:44(<dictcomp>)
  1000001    0.291    0.000    0.291    0.000 sdm.py:28(<genexpr>)
        1    0.000    0.000    0.007    0.007 ddm.py:115(ones)
        1    0.000    0.000    0.007    0.007 ddm.py:87(__init__)
     1001    0.006    0.000    0.006    0.000 ddm.py:119(<genexpr>)
     1001    0.000    0.000    0.001    0.000 ddm.py:92(<genexpr>)
     1001    0.000    0.000    0.000    0.000 sdm.py:42(<genexpr>)
     2002    0.000    0.000    0.000    0.000 {built-in method builtins.len}
     1001    0.000    0.000    0.000    0.000 sdm.py:26(<genexpr>)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}
        1    0.000    0.000    0.000    0.000 {method 'values' of 'dict' objects}

What is happening is that

DomainMatrix.ones calls cls.from_rep(DDM.ones(shape, domain))
DDM.ones takes 7 milliseconds but from_rep takes 897 milliseconds.
The from_rep function calls through to SDM.from_list which is slow.

I think that the problem is the currently cls.from_rep converts a DDM to SDM. Ideally it would not do that and would just use the DDM internally.

ks147 · 2021-03-21T07:11:44Z

If you time DomainMatrix.ones here you'll see that it is slow due to converting between SDM and DDM and other checking:

In [12]: %time ok = DomainMatrix.ones((1000, 1000), ZZ)
CPU times: user 710 ms, sys: 50.3 ms, total: 760 ms
Wall time: 769 ms

In [13]: %prun -s cumulative ok = DomainMatrix.ones((1000, 1000), ZZ)
         1009025 function calls in 0.936 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.936    0.936 {built-in method builtins.exec}
        1    0.028    0.028    0.936    0.936 <string>:1(<module>)
        1    0.005    0.005    0.908    0.908 domainmatrix.py:232(ones)
        1    0.000    0.000    0.897    0.897 domainmatrix.py:33(from_rep)
        1    0.000    0.000    0.897    0.897 domainmatrix.py:25(__init__)
        1    0.000    0.000    0.897    0.897 sdm.py:39(from_list)
        4    0.224    0.056    0.516    0.129 {built-in method builtins.all}
        1    0.000    0.000    0.515    0.515 sdm.py:21(__init__)
        1    0.001    0.001    0.381    0.381 sdm.py:46(<dictcomp>)
     1001    0.001    0.000    0.380    0.000 sdm.py:45(<genexpr>)
     1000    0.003    0.000    0.379    0.000 sdm.py:44(<lambda>)
     1000    0.377    0.000    0.377    0.000 sdm.py:44(<dictcomp>)
  1000001    0.291    0.000    0.291    0.000 sdm.py:28(<genexpr>)
        1    0.000    0.000    0.007    0.007 ddm.py:115(ones)
        1    0.000    0.000    0.007    0.007 ddm.py:87(__init__)
     1001    0.006    0.000    0.006    0.000 ddm.py:119(<genexpr>)
     1001    0.000    0.000    0.001    0.000 ddm.py:92(<genexpr>)
     1001    0.000    0.000    0.000    0.000 sdm.py:42(<genexpr>)
     2002    0.000    0.000    0.000    0.000 {built-in method builtins.len}
     1001    0.000    0.000    0.000    0.000 sdm.py:26(<genexpr>)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}
        1    0.000    0.000    0.000    0.000 {method 'values' of 'dict' objects}

What is happening is that

DomainMatrix.ones calls cls.from_rep(DDM.ones(shape, domain))
DDM.ones takes 7 milliseconds but from_rep takes 897 milliseconds.
The from_rep function calls through to SDM.from_list which is slow.

I think that the problem is the currently cls.from_rep converts a DDM to SDM. Ideally it would not do that and would just use the DDM internally.

I'm a little lost. Do I need to change the internal representation to DDM to improve the time complexity. If yes, then how do I go about doing that.

oscarbenjamin · 2021-03-21T09:37:40Z

I'm a little lost. Do I need to change the internal representation to DDM to improve the time complexity. If yes, then how do I go about doing that.

I worked a bit on this and opened a PR #21140 which allows DomainMatrix to use either DDM or SDM.

That needs finishing though (feel free to take over and finish it). The first thing it needs is tests.

ks147 · 2021-04-24T07:36:49Z

@oscarbenjamin #21146 is now closed so I think it helps speed up DomainMatrix.ones.

I ran the benchmark again for 1000x1000 DomainMatrix.

In [3]:
from sympy import ZZ, QQ
from sympy.polys.matrices import DomainMatrix
%time ok = DomainMatrix.ones((1000, 1000), ZZ)

Out[3]:
CPU times: user 256 ms, sys: 19.9 ms, total: 276 ms
Wall time: 276 ms

In[4]: %prun -s cumulative ok = DomainMatrix.ones((1000, 1000), ZZ)

Out[4]:
  1009025 function calls in 0.341 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.341    0.341 {built-in method builtins.exec}
        1    0.006    0.006    0.341    0.341 <string>:1(<module>)
        1    0.002    0.002    0.335    0.335 domainmatrix.py:232(ones)
        1    0.000    0.000    0.327    0.327 domainmatrix.py:33(from_rep)
        1    0.000    0.000    0.327    0.327 domainmatrix.py:25(__init__)
        1    0.000    0.000    0.327    0.327 sdm.py:39(from_list)
        1    0.000    0.000    0.178    0.178 sdm.py:46(<dictcomp>)
     1001    0.000    0.000    0.178    0.000 sdm.py:45(<genexpr>)
     1000    0.001    0.000    0.177    0.000 sdm.py:44(<lambda>)
     1000    0.177    0.000    0.177    0.000 sdm.py:44(<dictcomp>)
        4    0.061    0.015    0.149    0.037 {built-in method builtins.all}
        1    0.000    0.000    0.148    0.148 sdm.py:21(__init__)
  1000001    0.087    0.000    0.087    0.000 sdm.py:28(<genexpr>)
        1    0.000    0.000    0.006    0.006 ddm.py:115(ones)
        1    0.000    0.000    0.006    0.006 ddm.py:87(__init__)
     1001    0.006    0.000    0.006    0.000 ddm.py:119(<genexpr>)
     1001    0.000    0.000    0.000    0.000 ddm.py:92(<genexpr>)
     1001    0.000    0.000    0.000    0.000 sdm.py:42(<genexpr>)
     2002    0.000    0.000    0.000    0.000 {built-in method builtins.len}
     1001    0.000    0.000    0.000    0.000 sdm.py:26(<genexpr>)
        1    0.000    0.000    0.000    0.000 {method 'values' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}

It now takes only 327ms for from_rep function call.

…trix_ones

…to DomainMatrix_ones

oscarbenjamin · 2021-04-24T09:24:12Z

It now takes only 327ms for from_rep function call.

That still seems slow to me. Why does it take so long?

oscarbenjamin · 2021-04-24T13:49:00Z

It now takes only 327ms for from_rep function call.

That still seems slow to me. Why does it take so long?

I don't think you timed that correctly. I just checked out this PR and I get:

In [1]: from sympy import ZZ, QQ
   ...: from sympy.polys.matrices import DomainMatrix

In [2]: %time ok = DomainMatrix.ones((1000, 1000), ZZ)
CPU times: user 9.43 ms, sys: 2.95 ms, total: 12.4 ms
Wall time: 12 ms

In [3]: %prun -s cumulative ok = DomainMatrix.ones((1000, 1000), ZZ)
         3013 function calls in 0.027 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.027    0.027 {built-in method builtins.exec}
        1    0.005    0.005    0.027    0.027 <string>:1(<module>)
        1    0.000    0.000    0.022    0.022 domainmatrix.py:1168(ones)
        1    0.000    0.000    0.021    0.021 ddm.py:138(ones)
        1    0.000    0.000    0.021    0.021 ddm.py:90(__init__)
     1001    0.020    0.000    0.020    0.000 ddm.py:142(<genexpr>)
        1    0.000    0.000    0.001    0.001 {built-in method builtins.all}
     1001    0.000    0.000    0.001    0.000 ddm.py:95(<genexpr>)
     1001    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.000    0.000 domainmatrix.py:116(from_rep)
        1    0.000    0.000    0.000    0.000 {built-in method __new__ of type object at 0x106b75b80}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

ks147 · 2021-04-24T13:57:27Z

It now takes only 327ms for from_rep function call.

That still seems slow to me. Why does it take so long?

I don't think you timed that correctly. I just checked out this PR and I get:

In [1]: from sympy import ZZ, QQ
   ...: from sympy.polys.matrices import DomainMatrix

In [2]: %time ok = DomainMatrix.ones((1000, 1000), ZZ)
CPU times: user 9.43 ms, sys: 2.95 ms, total: 12.4 ms
Wall time: 12 ms

In [3]: %prun -s cumulative ok = DomainMatrix.ones((1000, 1000), ZZ)
         3013 function calls in 0.027 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.027    0.027 {built-in method builtins.exec}
        1    0.005    0.005    0.027    0.027 <string>:1(<module>)
        1    0.000    0.000    0.022    0.022 domainmatrix.py:1168(ones)
        1    0.000    0.000    0.021    0.021 ddm.py:138(ones)
        1    0.000    0.000    0.021    0.021 ddm.py:90(__init__)
     1001    0.020    0.000    0.020    0.000 ddm.py:142(<genexpr>)
        1    0.000    0.000    0.001    0.001 {built-in method builtins.all}
     1001    0.000    0.000    0.001    0.000 ddm.py:95(<genexpr>)
     1001    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.000    0.000 domainmatrix.py:116(from_rep)
        1    0.000    0.000    0.000    0.000 {built-in method __new__ of type object at 0x106b75b80}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

My bad. Now that we know it is much faster, is there anything left to change in this PR?

oscarbenjamin · 2021-04-24T13:58:53Z

Looks good to me

Added function ones to DomainMatrix and DDM class

03177e9

Merge branch 'master' into DomainMatrix_ones

396e8ce

Added function ones to SDM class

68849f7

ks147 changed the title ~~Added function ones to DomainMatrix and DDM class~~ Added function ones to DomainMatrix,DDM and SDM class Mar 18, 2021

ks147 changed the title ~~Added function ones to DomainMatrix,DDM and SDM class~~ Added function ones to DomainMatrix,DDM and SDM class Mar 18, 2021

Abdullahjavednesar added the polys label Mar 18, 2021

Added tests

4b5f43d

oscarbenjamin reviewed Mar 20, 2021

View reviewed changes

Updated ones in SDM to make it faster

b6718ee

Merge branch 'master' into DomainMatrix_ones

4665d4c

ks147 added 3 commits April 24, 2021 13:33

Merge branch 'master' of https://github.com/sympy/sympy into DomainMa…

08bf67d

…trix_ones

Merge branch 'DomainMatrix_ones' of https://github.com/ks147/sympy in…

f70532d

…to DomainMatrix_ones

Changed internal rep of DomainMatrix ones

ee14ba2

ks147 force-pushed the DomainMatrix_ones branch from 768c0f1 to ee14ba2 Compare April 24, 2021 08:17

oscarbenjamin merged commit 6242171 into sympy:master Apr 24, 2021

Uh oh!

Added function ones to DomainMatrix,DDM and SDM class #21106

Added function ones to DomainMatrix,DDM and SDM class #21106

Uh oh!

Conversation

ks147 commented Mar 17, 2021

References to other Issues or PRs

Brief description of what is fixed or changed

Release Notes

Uh oh!

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

Uh oh!

Uh oh!

oscarbenjamin commented Mar 17, 2021

Uh oh!

ks147 commented Mar 18, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

oscarbenjamin commented Mar 18, 2021

Uh oh!

ks147 commented Mar 19, 2021

Uh oh!

ks147 commented Mar 20, 2021

Uh oh!

oscarbenjamin Mar 20, 2021

Choose a reason for hiding this comment

Uh oh!

ks147 Mar 20, 2021

Choose a reason for hiding this comment

Uh oh!

oscarbenjamin commented Mar 20, 2021

Uh oh!

ks147 commented Mar 21, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

oscarbenjamin commented Mar 21, 2021

Uh oh!

ks147 commented Apr 24, 2021

Uh oh!

oscarbenjamin commented Apr 24, 2021

Uh oh!

oscarbenjamin commented Apr 24, 2021

Uh oh!

ks147 commented Apr 24, 2021

Uh oh!

oscarbenjamin commented Apr 24, 2021

Uh oh!

Uh oh!

sympy-bot commented Mar 17, 2021 •

edited

Loading

ks147 commented Mar 18, 2021 •

edited

Loading

ks147 commented Mar 21, 2021 •

edited

Loading