Opened 5 years ago
Closed 4 years ago
#15781 closed enhancement (fixed)
Increase Performance of possible_periods in Projective Morphism
Reported by:  drose  Owned by:  drose 

Priority:  minor  Milestone:  sage6.3 
Component:  algebraic geometry  Keywords:  possible_periods, cython 
Cc:  bhutz  Merged in:  
Authors:  Dillon Rose  Reviewers:  Ben Hutz, Joao Alberto de Faria 
Report Upstream:  N/A  Work issues:  
Branch:  3adee1c (Commits)  Commit:  3adee1ca2b37996abae28157700a5c4480fd3436 
Dependencies:  #15780  Stopgaps: 
Description
Increase Performance of possible_periods in Projective Morphism by replacing functionality with cython.
Change History (39)
comment:1 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:2 Changed 5 years ago by
 Branch set to u/drose/15781
 Cc bhutz added
 Component changed from cython to algebraic geometry
 Owner changed from (none) to drose
 Priority changed from major to minor
comment:3 Changed 5 years ago by
 Commit set to e822a8a28f0554df7dad49332d1469ed2bdb3c1e
comment:4 Changed 5 years ago by
 Commit changed from e822a8a28f0554df7dad49332d1469ed2bdb3c1e to 15c25ec46bfccc0c41779945f1d89d25b8e680f3
comment:5 Changed 5 years ago by
 Dependencies set to #15780
comment:6 Changed 5 years ago by
 Commit changed from 15c25ec46bfccc0c41779945f1d89d25b8e680f3 to 5f34987dd3f1b1a2500220e8daa9e138cacf9787
Branch pushed to git repo; I updated commit sha1. New commits:
5ca376b  trac 15780. Added documentation.

7ab8c63  Merge branch 'u/drose/15780' of git://trac.sagemath.org/sage into ticket/15781

2d9fe03  trac 15781. Added documentation.

888a2ab  trac 15780. Added documentation to projective morphism.

54136c6  Merge branch 'u/drose/15780' of git://trac.sagemath.org/sage into ticket/15781

87572ab  trac 15780. Added documentation.

ec7faaa  Merge branch 'u/drose/15780' of git://trac.sagemath.org/sage into ticket/15781

5f34987  trac 15781. Added documentation to projective_morphism_helper.pyx.

comment:7 Changed 4 years ago by
 Branch changed from u/drose/15781 to u/bhutz/ticket/15781
 Commit changed from 5f34987dd3f1b1a2500220e8daa9e138cacf9787 to e4131881531e902225804986f1c34a1d5e97385c
rebased to 6.2.beta7
Last 10 new commits:
6be7361  rebase to 6.2.beta7 and remove whitespace

65eef1c  # Tue Oct 22 20:59:00 2013 0400

18d030f  # Wed Nov 06 19:13:50 2013 0500

eb476a9  trac 15781. Added documentation.

4db0494  trac 15781. Added documentation to projective_morphism_helper.pyx.

e30ba5c  # Wed Nov 06 19:13:50 2013 0500

2f4e384  trac 15781. Added documentation.

fb89b52  trac 15780. Added documentation to projective morphism.

69cd8f4  trac 15781. Added documentation to projective_morphism_helper.pyx.

e413188  rebase to 6.2.beta7 and current 15780

comment:8 Changed 4 years ago by
 Commit changed from e4131881531e902225804986f1c34a1d5e97385c to f5ba4694b199d4aa6d0d4fc4b377f4cdb1846a04
Branch pushed to git repo; I updated commit sha1. New commits:
f5ba469  remove duplicate function from rebase

comment:9 Changed 4 years ago by
 Branch changed from u/bhutz/ticket/15781 to u/drose/ticket/15781
 Created changed from 02/03/14 15:05:59 to 02/03/14 15:05:59
 Modified changed from 04/10/14 16:00:06 to 04/10/14 16:00:06
comment:10 Changed 4 years ago by
 Commit changed from f5ba4694b199d4aa6d0d4fc4b377f4cdb1846a04 to 89da33337ecac6d43c7b3da4b37e8dc1a9ad16ee
Branch pushed to git repo; I updated commit sha1. New commits:
89da333  Reduced memory load and fixed doctest.

comment:11 Changed 4 years ago by
 Status changed from new to needs_review
comment:12 Changed 4 years ago by
 Reviewers set to Ben Hutz
 Status changed from needs_review to needs_work
No issues with the long test, but before I do more specialized testing there are number of things from looking through the code:
1) Fix preamble documentation to be for the helper and not generic projective space
2) Fix copyright date
3) in _fast_possible_periods:
 use a Reference block  see dynamtomic_polynomial (should be able to use the references from other files)
 examples should call _fast_possible_periods
 todo: typo return
 todo: add  more space efficient hash/pointtable
 use is_prime_finite_field
 move import to header of file
4) pass N+1 into into _normalize_coordinates to replace the len(point) calls
5) _mod_inv  description: Find the inverse of the number modulo the given prime.
6) Use the better version of the eigenvale computation (see 14219 lines 26082624)
7) also from 14219
use
return sorted(periods)
instead of
periods=list(periods) periods.sort() return(periods)
8)enum points documentation: Enumerate points in projective space over finite field with given prime and dimension.
comment:13 Changed 4 years ago by
err.. there was one doc test failure in helper.pyx
File "sage/schemes/projective/projective_morphism_helper.pyx", line 213, in sage.schemes.projective.projective_morphism_helper._enum_points Failed example: _enum_points(3,2) Expected: [[1, 0, 0], [0, 1, 0], [1, 1, 0], [2, 1, 0], [0, 0, 1], [1, 0, 1], [2, 0, 1], [0, 1, 1], [1, 1, 1], [2, 1, 1], [0, 2, 1], [1, 2, 1], [2, 2, 1]] Got: <generator object at 0x1161d6500>
comment:14 Changed 4 years ago by
 Commit changed from 89da33337ecac6d43c7b3da4b37e8dc1a9ad16ee to 52938af78886580fb736ad1604456a601af928d0
Branch pushed to git repo; I updated commit sha1. New commits:
52938af  Fixed issues from trac server comment 12.

comment:15 Changed 4 years ago by
 Commit changed from 52938af78886580fb736ad1604456a601af928d0 to 28a5a37412d5dfdbf047baf07e24283321b5a17c
Branch pushed to git repo; I updated commit sha1. New commits:
28a5a37  Completed changes to fufill issues from trac server comment 12.

comment:16 Changed 4 years ago by
The long test and my other functionality tests all pass, but there are two things. One minor, one major.
Minor: I think I was wrong about the reference block. The .pyx files seem to not be part of the docbuild, so I'm a little concerned about the REFERENCE block have possible issues later on. Perhaps that should be returned to the previous method.
Major: There is still a memory issue. The following example:
P.<x,y,z,u,v>=ProjectiveSpace(QQ,4) H=Hom(P,P) f=H([38/45*x^2 + (2*y  7/45*v)*x + (1/2*y^2  1/2*v*y + v^2),67/90*x^2 + (2*y + 157/90*v)*x  v*y,(u  v)*z + (13/30*u^2 + 13/30*v*u + v^2),1/2*z^2 + (u + 3/2*v)*z + (1/3*u^2 + 4/3*v*u),v^2]) print f.possible_periods(prime_bound=[13,30])
runs just fine with 15780, but with 15781 very quickly runs out of memory (on my laptop allocated 3Gb). fyi, it take about 8min to complete the example on my laptop under 15780. The function _enum_points is what is consuming all the memory.
comment:17 Changed 4 years ago by
... and you may want to redo the branch for this ticket (hopefully nothing depends on it yet). Currently, it has the *.c
file of a *.pyx
tracked. You should probably rebase the branch so that that file is never checked in (I'm not sure whether removing it will leave it in the history).
comment:18 Changed 4 years ago by
 Commit changed from 28a5a37412d5dfdbf047baf07e24283321b5a17c to 25a95995428d89a2943aee58b6fb192894866a57
Branch pushed to git repo; I updated commit sha1. New commits:
25a9599  Changed documentation and reduced memory load in _enum_points.

comment:19 Changed 4 years ago by
 Commit changed from 25a95995428d89a2943aee58b6fb192894866a57 to b7abd7f2e8c9984143613dba07d23df4eb97eebd
Branch pushed to git repo; I updated commit sha1. New commits:
1ee9c63  Removed src/sage/schemes/projective/projective_morphism_helper.c from being tracked.

7484355  Fixed issues reported on trac server comment 28 and 29.

9be3bba  Changed doctest for fast_eval.

ff64341  Merge branch 'u/drose/ticket/15780' of git://trac.sagemath.org/sage into ticket/15781

c858d54  Switched parallelization to p_iter_fork.

0a1cf6d  Added documentation on new keyword ncpus.

be46079  moved import to header

857d08c  Merge branch 'u/bhutz/ticket/16168' of git://trac.sagemath.org/sage into ticket/15780

81fba1b  Fixed import statements.

b7abd7f  Merge branch 'u/drose/ticket/15780' of git://trac.sagemath.org/sage into ticket/15781

comment:20 Changed 4 years ago by
 Branch changed from u/drose/ticket/15781 to u/bhutz/ticket/15781
 Modified changed from 05/01/14 16:13:29 to 05/01/14 16:13:29
comment:21 Changed 4 years ago by
 Commit changed from b7abd7f2e8c9984143613dba07d23df4eb97eebd to 5094e43ea32d0c6d75fe28568fc4e5bc2533cb3d
 Status changed from needs_work to needs_review
Dillon fixed the issues and removed the .c file. I then did the rebase to be sure it doesn't have it in the history. I ran the full tests again and everything looks good.
Should someone else take a look at this since both Dillon and I have been making code changes?
Last 10 new commits:
7c85359  Switched parallelization to p_iter_fork.

defcfe7  Added documentation on new keyword ncpus.

d6970b4  moved import to header

481ca87  Fixed issues reported on trac server comment 28 and 29.

2ccf84d  Changed doctest for fast_eval.

232a58d  Fixed issues from trac server comment 12.

3bb4284  Completed changes to fufill issues from trac server comment 12.

f6df021  Changed documentation and reduced memory load in _enum_points.

170205d  Removed src/sage/schemes/projective/projective_morphism_helper.c from being tracked.

5094e43  rebase to 6.2.rc1

comment:22 Changed 4 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:23 in reply to: ↑ description Changed 4 years ago by
 Reviewers changed from Ben Hutz to Ben Hutz, Joao Alberto de Faria
 Status changed from needs_review to positive_review
Reviewed code.
comment:24 Changed 4 years ago by
 Status changed from positive_review to needs_work
Please rewrite history for this branch prior to merging. Presently, you are putting this commit in the history of sage for posterity:
http://git.sagemath.org/sage.git/commit/?id=170205d7d56fc90724c3e0d557b1d6e8ade2dcae
comment:25 followup: ↓ 26 Changed 4 years ago by
We tried to undo that by untracking the file and then rebasing. How do we rewrite the history so that .c file is not included?
comment:26 in reply to: ↑ 25 Changed 4 years ago by
Replying to bhutz:
We tried to undo that by untracking the file and then rebasing. How do we rewrite the history so that .c file is not included?
Probably something like git rebase i 6.2.rc0
(what you called rebases in history were probably merges) and then edit a lot of "pick" to be "squash" instead. If you can squash everything between the addition and the removal of the .c
file, you'll have the easiest time. If you want to preserve some of the individual commits in between, you'll have to see if you can reorder them.
You'll basically be producing a "fresh" branch that introduces the commits you want to have in there and not the ones you don't. Of course, anybody who has based work on commits you're removing, will have merge conflicts with your new branch, so hopefully noone did. That's why usually merging produces less severe conflicts and is therefore recommended, but when you really want to remove things from history, you have to rebase.
comment:27 Changed 4 years ago by
ok. I actually did git rebase and not merge. It sounds like the rebase i will give me more control over the end result. I'll give that a try and see if I can get the .c problem sorted out
comment:28 Changed 4 years ago by
 Commit changed from 5094e43ea32d0c6d75fe28568fc4e5bc2533cb3d to 9731957931e987ef72de9371c611cdfc455af269
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
4e0d265  Reduced memory load and fixed doctest.

794da79  Switched parallelization to p_iter_fork.

0ae0460  Added documentation on new keyword ncpus.

2d968e6  moved import to header

4edf5ac  Fixed issues reported on trac server comment 28 and 29.

71bc3ab  Changed doctest for fast_eval.

02a5c64  Fixed issues from trac server comment 12.

55d8129  Completed changes to fufill issues from trac server comment 12.

13e35d8  Changed documentation and reduced memory load in _enum_points.

9731957  rebase to 6.2.rc1

comment:29 Changed 4 years ago by
I've rewritten the history to remove all references to the .c file. Currently building and testing...
comment:30 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:31 Changed 4 years ago by
 Status changed from needs_review to positive_review
Reviewed code, everything is still working
comment:32 Changed 4 years ago by
 Status changed from positive_review to needs_work
 Work issues set to merge latest beta
Merge conflict, please fix
comment:33 Changed 4 years ago by
 Commit changed from 9731957931e987ef72de9371c611cdfc455af269 to 36e5116e6fb2be2a92f446f3a652eb66a1ef045d
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
c999a81  Added lazy_attribute to fastpolys.

413224f  Fixed lazy attribute and merged 16168.

ccc4bc9  Fixed doctest.

c0fb6fb  Reduced memory load and fixed doctest.

1092aaf  Fixed issues reported on trac server comment 28 and 29.

ded07cd  Changed doctest for fast_eval.

4e9dd3b  Fixed issues from trac server comment 12.

ebd4ccd  Completed changes to fufill issues from trac server comment 12.

6255111  Changed documentation and reduced memory load in _enum_points.

36e5116  rebase to 6.2.rc1

comment:34 Changed 4 years ago by
 Status changed from needs_work to needs_review
the rebase to 6.3.beta0 did not cause any changes to commit, just omitted some commits, so I had to push with force to. But, it should merge now.
comment:35 Changed 4 years ago by
 Work issues merge latest beta deleted
comment:36 Changed 4 years ago by
 Status changed from needs_review to needs_work
You should never rebase branches that are on trac, always merge.
Conflicts with 6.3.beta1
comment:37 Changed 4 years ago by
 Commit changed from 36e5116e6fb2be2a92f446f3a652eb66a1ef045d to 3adee1ca2b37996abae28157700a5c4480fd3436
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
d372022  remove duplicate function from rebase

d8f8682  Fixed parallelizaion using p_iter_fork.

8762498  Fixed lazy attribute and merged 16168.

74a308a  Fixed doctest.

7c080ab  Reduced memory load and fixed doctest.

916b2f0  Fixed issues reported on trac server comment 28 and 29.

77c4abe  Fixed issues from trac server comment 12.

8704dfe  Completed changes to fufill issues from trac server comment 12.

71a35e8  Changed documentation and reduced memory load in _enum_points.

3adee1c  rebase to 6.2.rc1

comment:38 Changed 4 years ago by
 Status changed from needs_work to needs_review
I saw the conflict and had just pushed a new rebase before I saw your comment. I'll merge in the future.
comment:39 Changed 4 years ago by
 Branch changed from u/bhutz/ticket/15781 to 3adee1ca2b37996abae28157700a5c4480fd3436
 Resolution set to fixed
 Status changed from needs_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
# Tue Oct 22 20:59:00 2013 0400
# Wed Nov 06 19:13:50 2013 0500