Opened 4 years ago

Closed 3 years ago

#15781 closed enhancement (fixed)

Increase Performance of possible_periods in Projective Morphism

Reported by: drose Owned by: drose
Priority: minor Milestone: sage-6.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 4 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:2 Changed 4 years ago by drose

  • 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 4 years ago by git

  • Commit set to e822a8a28f0554df7dad49332d1469ed2bdb3c1e

Branch pushed to git repo; I updated commit sha1. New commits:

5bafb1b# Tue Oct 22 20:59:00 2013 -0400
e822a8a# Wed Nov 06 19:13:50 2013 -0500

comment:4 Changed 4 years ago by git

  • Commit changed from e822a8a28f0554df7dad49332d1469ed2bdb3c1e to 15c25ec46bfccc0c41779945f1d89d25b8e680f3

Branch pushed to git repo; I updated commit sha1. New commits:

52ec0b3trac 15780. Change to projective morphism _call_ function.
15c25ecMerge branch 'u/drose/15780' of git://trac.sagemath.org/sage into ticket/15781

comment:5 Changed 4 years ago by drose

  • Dependencies set to #15780

comment:6 Changed 4 years ago by git

  • Commit changed from 15c25ec46bfccc0c41779945f1d89d25b8e680f3 to 5f34987dd3f1b1a2500220e8daa9e138cacf9787

Branch pushed to git repo; I updated commit sha1. New commits:

5ca376btrac 15780. Added documentation.
7ab8c63Merge branch 'u/drose/15780' of git://trac.sagemath.org/sage into ticket/15781
2d9fe03trac 15781. Added documentation.
888a2abtrac 15780. Added documentation to projective morphism.
54136c6Merge branch 'u/drose/15780' of git://trac.sagemath.org/sage into ticket/15781
87572abtrac 15780. Added documentation.
ec7faaaMerge branch 'u/drose/15780' of git://trac.sagemath.org/sage into ticket/15781
5f34987trac 15781. Added documentation to projective_morphism_helper.pyx.

comment:7 Changed 3 years ago by bhutz

  • 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:

6be7361rebase 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
eb476a9trac 15781. Added documentation.
4db0494trac 15781. Added documentation to projective_morphism_helper.pyx.
e30ba5c# Wed Nov 06 19:13:50 2013 -0500
2f4e384trac 15781. Added documentation.
fb89b52trac 15780. Added documentation to projective morphism.
69cd8f4trac 15781. Added documentation to projective_morphism_helper.pyx.
e413188rebase to 6.2.beta7 and current 15780

comment:8 Changed 3 years ago by git

  • Commit changed from e4131881531e902225804986f1c34a1d5e97385c to f5ba4694b199d4aa6d0d4fc4b377f4cdb1846a04

Branch pushed to git repo; I updated commit sha1. New commits:

f5ba469remove duplicate function from rebase

comment:9 Changed 3 years ago by drose

  • 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 3 years ago by git

  • Commit changed from f5ba4694b199d4aa6d0d4fc4b377f4cdb1846a04 to 89da33337ecac6d43c7b3da4b37e8dc1a9ad16ee

Branch pushed to git repo; I updated commit sha1. New commits:

89da333Reduced memory load and fixed doctest.

comment:11 Changed 3 years ago by drose

  • Status changed from new to needs_review

comment:12 Changed 3 years ago by bhutz

  • 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 2608-2624)

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 3 years ago by bhutz

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 3 years ago by git

  • Commit changed from 89da33337ecac6d43c7b3da4b37e8dc1a9ad16ee to 52938af78886580fb736ad1604456a601af928d0

Branch pushed to git repo; I updated commit sha1. New commits:

52938afFixed issues from trac server comment 12.

comment:15 Changed 3 years ago by git

  • Commit changed from 52938af78886580fb736ad1604456a601af928d0 to 28a5a37412d5dfdbf047baf07e24283321b5a17c

Branch pushed to git repo; I updated commit sha1. New commits:

28a5a37Completed changes to fufill issues from trac server comment 12.

comment:16 Changed 3 years ago by bhutz

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 3 years ago by nbruin

... 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 3 years ago by git

  • Commit changed from 28a5a37412d5dfdbf047baf07e24283321b5a17c to 25a95995428d89a2943aee58b6fb192894866a57

Branch pushed to git repo; I updated commit sha1. New commits:

25a9599Changed documentation and reduced memory load in _enum_points.

comment:19 Changed 3 years ago by git

  • Commit changed from 25a95995428d89a2943aee58b6fb192894866a57 to b7abd7f2e8c9984143613dba07d23df4eb97eebd

Branch pushed to git repo; I updated commit sha1. New commits:

1ee9c63Removed src/sage/schemes/projective/projective_morphism_helper.c from being tracked.
7484355Fixed issues reported on trac server comment 28 and 29.
9be3bbaChanged doctest for fast_eval.
ff64341Merge branch 'u/drose/ticket/15780' of git://trac.sagemath.org/sage into ticket/15781
c858d54Switched parallelization to p_iter_fork.
0a1cf6dAdded documentation on new keyword ncpus.
be46079moved import to header
857d08cMerge branch 'u/bhutz/ticket/16168' of git://trac.sagemath.org/sage into ticket/15780
81fba1bFixed import statements.
b7abd7fMerge branch 'u/drose/ticket/15780' of git://trac.sagemath.org/sage into ticket/15781

comment:20 Changed 3 years ago by bhutz

  • 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 3 years ago by bhutz

  • 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:

7c85359Switched parallelization to p_iter_fork.
defcfe7Added documentation on new keyword ncpus.
d6970b4moved import to header
481ca87Fixed issues reported on trac server comment 28 and 29.
2ccf84dChanged doctest for fast_eval.
232a58dFixed issues from trac server comment 12.
3bb4284Completed changes to fufill issues from trac server comment 12.
f6df021Changed documentation and reduced memory load in _enum_points.
170205dRemoved src/sage/schemes/projective/projective_morphism_helper.c from being tracked.
5094e43rebase to 6.2.rc1

comment:22 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:23 in reply to: ↑ description Changed 3 years ago by jdefaria

  • 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 3 years ago by nbruin

  • 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 follow-up: Changed 3 years ago by 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?

comment:26 in reply to: ↑ 25 Changed 3 years ago by nbruin

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 no-one 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 3 years ago by bhutz

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 3 years ago by git

  • Commit changed from 5094e43ea32d0c6d75fe28568fc4e5bc2533cb3d to 9731957931e987ef72de9371c611cdfc455af269

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

4e0d265Reduced memory load and fixed doctest.
794da79Switched parallelization to p_iter_fork.
0ae0460Added documentation on new keyword ncpus.
2d968e6moved import to header
4edf5acFixed issues reported on trac server comment 28 and 29.
71bc3abChanged doctest for fast_eval.
02a5c64Fixed issues from trac server comment 12.
55d8129Completed changes to fufill issues from trac server comment 12.
13e35d8Changed documentation and reduced memory load in _enum_points.
9731957rebase to 6.2.rc1

comment:29 Changed 3 years ago by bhutz

I've re-written the history to remove all references to the .c file. Currently building and testing...

comment:30 Changed 3 years ago by bhutz

  • Status changed from needs_work to needs_review

comment:31 Changed 3 years ago by jdefaria

  • Status changed from needs_review to positive_review

Reviewed code, everything is still working

comment:32 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work
  • Work issues set to merge latest beta

Merge conflict, please fix

comment:33 Changed 3 years ago by git

  • Commit changed from 9731957931e987ef72de9371c611cdfc455af269 to 36e5116e6fb2be2a92f446f3a652eb66a1ef045d

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

c999a81Added lazy_attribute to fastpolys.
413224fFixed lazy attribute and merged 16168.
ccc4bc9Fixed doctest.
c0fb6fbReduced memory load and fixed doctest.
1092aafFixed issues reported on trac server comment 28 and 29.
ded07cdChanged doctest for fast_eval.
4e9dd3bFixed issues from trac server comment 12.
ebd4ccdCompleted changes to fufill issues from trac server comment 12.
6255111Changed documentation and reduced memory load in _enum_points.
36e5116rebase to 6.2.rc1

comment:34 Changed 3 years ago by bhutz

  • 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 3 years ago by bhutz

  • Work issues merge latest beta deleted

comment:36 Changed 3 years ago by vbraun

  • 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 3 years ago by git

  • Commit changed from 36e5116e6fb2be2a92f446f3a652eb66a1ef045d to 3adee1ca2b37996abae28157700a5c4480fd3436

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

d372022remove duplicate function from rebase
d8f8682Fixed parallelizaion using p_iter_fork.
8762498Fixed lazy attribute and merged 16168.
74a308aFixed doctest.
7c080abReduced memory load and fixed doctest.
916b2f0Fixed issues reported on trac server comment 28 and 29.
77c4abeFixed issues from trac server comment 12.
8704dfeCompleted changes to fufill issues from trac server comment 12.
71a35e8Changed documentation and reduced memory load in _enum_points.
3adee1crebase to 6.2.rc1

comment:38 Changed 3 years ago by bhutz

  • 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 3 years ago by vbraun

  • Branch changed from u/bhutz/ticket/15781 to 3adee1ca2b37996abae28157700a5c4480fd3436
  • Resolution set to fixed
  • Status changed from needs_review to closed
Note: See TracTickets for help on using tickets.