#21248 closed enhancement (fixed)
Reduce Forms from Stoll and Cremona
Reported by:  Rebecca Lauren Miller  Owned by:  

Priority:  minor  Milestone:  sage7.5 
Component:  algebra  Keywords:  
Cc:  Ben Hutz, Paul Fili  Merged in:  
Authors:  Rebecca Lauren Miller, Ben Hutz  Reviewers:  Ben Hutz, Rebecca Lauren Miller 
Report Upstream:  N/A  Work issues:  
Branch:  c00aaeb (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
Implementing the reduce forms algorithm from On the reduction theory of binary forms for both polynomials and projective morphisms. Also includes Newton's method for 2 variables, could be further expanded in the future.
Change History (44)
comment:1 Changed 6 years ago by
Branch:  → u/rlmiller/binary 

comment:2 Changed 6 years ago by
Cc:  Ben Hutz Paul Fili added 

Commit:  → 0544a244e4199c6d89e1d76ceae593c71bc57c71 
Description:  modified (diff) 
Status:  new → needs_review 
comment:3 Changed 6 years ago by
Status:  needs_review → needs_work 

Well, the first step here is to move from 7.3beta4 to 7.4beta0.
Let's leave this as needswork until the issues are worked out.
comment:4 Changed 6 years ago by
Branch:  u/rlmiller/binary → u/bhutz/binary 

comment:5 Changed 6 years ago by
Commit:  0544a244e4199c6d89e1d76ceae593c71bc57c71 → f77747650f4a02a0bda698591913df7c27e6e17c 

Branch pushed to git repo; I updated commit sha1. New commits:
f777476  21248: some cleanup and minor error fixing

comment:6 Changed 6 years ago by
I did some code/formatting cleanup and made the examples work. For the most part you are just having formatting issues.
I have not tested any functionality yet.
comment:7 Changed 6 years ago by
Branch:  u/bhutz/binary → u/rlmiller/binary 

comment:8 Changed 6 years ago by
Commit:  f77747650f4a02a0bda698591913df7c27e6e17c → dcc7a4ae8d11eb006afd5cdd1b20a5edc46294cc 

Still need a few more examples, having problems with two examples in projective_morphism.py They worked in the notebook.
New commits:
dcc7a4a  21248 Reduced Binary form, added examples and documentation

comment:9 Changed 6 years ago by
I think there may be something wrong with the 2nd part of the algorithm. Using the example from the paper that illustrates why you need to use the system of equations, the numerical root finding is not getting the same z as they do.
poly = 19*x^8  262*x^7*h + 1507*x^6*h^2  4784*x^5*h^3 + 9202*x^4*h^4  10962*x^3*h^5 + 7844*x^2*h^6  3040*x*h^7 + 475*h^8
comment:10 Changed 6 years ago by
Commit:  dcc7a4ae8d11eb006afd5cdd1b20a5edc46294cc → 93e8aeaef71bdda2bac6a631f30b190e96b63059 

Branch pushed to git repo; I updated commit sha1. New commits:
93e8aea  21248 added example fixed errors

comment:11 Changed 6 years ago by
Status:  needs_work → needs_review 

comment:12 Changed 6 years ago by
Reviewers:  → Ben Hutz 

Status:  needs_review → needs_work 
 With the updated version of magma, I'm getting consistent results with most examples. Although here is one that is not working correctly:
234*x^11*h + 104832*x^10*h^2 + 21346884*x^9*h^3 + 2608021728*x^8*h^4 + 212413000410*x^7*h^5 + 12109691106162*x^6*h^6 + 493106447396862*x^5*h^7 + 14341797993350646*x^4*h^8 + 291976289803277118*x^3*h^9 + 3962625618555930456*x^2*h^10 + 32266526239647689652*x*h^11 + 119421058057217196228*h^12
It looks like the z0 part is correct, then the 2nd part is not.
 I'm not sure the inversion is correct. Take a look at part (2) on p13 of the paper. It may be causing the difference here
234*x^10  95940*x^9*h  17701164*x^8*h^2  1935379368*x^7*h^3 138869177616*x^6*h^4  6832744528662*x^5*h^5  233468654564574*x^4*h^6 5470310129096358*x^3*h^7  84114643276174446*x^2*h^8 766469114143193916*x*h^9  3142950903278916444*h^10
which has
magma: [1,41,0,1] vs sage: [1,41,0,1]
or this may be the same error as in the previous bullet point.
 Also, the code is in need of a comments describing what each piece is doing.
 I also think the try/except for the NJinv can be simplified to
if NJinv.base_ring() != KK: NJinv = matrix(KK,2,2,[KK(zw.numerator()/zw.denominator()) for zw in NJinv.list()])
Then you can remove the .numerator() on the v0's later in the code.
comment:13 Changed 6 years ago by
I though about the one that is way off and here is what is going on. There is a root on the real line of the system of equations to find z(F). Your starting z0 value converges to that solution via Newton's method. However, what you need to find is the other solution which is in the upper half plane
comment:14 Changed 6 years ago by
Commit:  93e8aeaef71bdda2bac6a631f30b190e96b63059 → 6f744f64a9d6feb4ee2d6f4ebb28d4e0944fc71c 

Branch pushed to git repo; I updated commit sha1. New commits:
6f744f6  21248 fixed error

comment:15 Changed 6 years ago by
Commit:  6f744f64a9d6feb4ee2d6f4ebb28d4e0944fc71c → f2bd1736ddc0ce63646d408c34c7120d9d84c0b6 

Branch pushed to git repo; I updated commit sha1. New commits:
f2bd173  21248 fixed errors added comments

comment:16 Changed 6 years ago by
Commit:  f2bd1736ddc0ce63646d408c34c7120d9d84c0b6 → 33e99418a4b3f233520cb9080682c05b159fa7b1 

Branch pushed to git repo; I updated commit sha1. New commits:
33e9941  21248 fixed documentaion

comment:17 Changed 6 years ago by
 docs still don't build
 here is another one that maybe doesn't work
1872*x^5*h  1375452*x^4*h^2  404242956*x^3*h^3  59402802888*x^2*h^4  4364544068352*x*h^5  128270946360960*h^6
Stoll's implementation in magma gives
12168*x^3  18252*x^2 + 9828*x  1872 [148 147] [ 1 1]
Although he may be doing some extra reducing to get the lower degree result
Here is a similar one that also maybe doesn't work:
1872*x^4  1098396*x^3*h  241680348*x^2*h^2  23634111384*x*h^3  866695583520*h^4
Stoll's implementation in magma gives
2808*x^3  4212*x^2 + 5148*x  1872 [146 1] [ 1 0]
comment:18 Changed 6 years ago by
Commit:  33e99418a4b3f233520cb9080682c05b159fa7b1 → a47a5889938f75ec474327f1ce3a54618eb25669 

Branch pushed to git repo; I updated commit sha1. New commits:
a47a588  21248 fixed errors

comment:19 Changed 6 years ago by
Status:  needs_work → needs_review 

comment:20 Changed 6 years ago by
Branch:  u/rlmiller/binary → u/bhutz/binary 

comment:21 Changed 6 years ago by
Commit:  a47a5889938f75ec474327f1ce3a54618eb25669 → 807efb0dbca2ad5700dd705a7ca255253fd0a79b 

Status:  needs_review → needs_work 
I did some general code cleanup and added some more description to the documentation. I also fixed the formatting issues in the documentation and examples. You should double check those changes.
For functionality
 I'm getting consistent results with Magma now. The only difference (besides trivial differences) is that in the case of a polynomial with a single multiple root, Magma moves that root to infinity and then minimizes the resulting poly. I assume this is to make the 'degree' as low as possible. This implementation does not, but the resulting coefficients here are actually smaller, so I don't really see this is an error, just a difference in implementation.
For projective morphism, there are a couple things
 the error_limit param needs to be passed in as well and an example where prec/error is needed.
 It is currently removing any multiple roots from the dynatomic: is this what you want to do since the algorithm is able to handle multiple roots as long as the multiplicity isn't too high?
btw, I set the default prec to 300, since that worked for nearly all my randomly generated examples.
New commits:
807efb0  21248: general code and documentation cleanup

comment:22 Changed 6 years ago by
Branch:  u/bhutz/binary → u/rlmiller/binary 

comment:23 Changed 6 years ago by
Commit:  807efb0dbca2ad5700dd705a7ca255253fd0a79b → fcc0b827221635b1a5e17f95d2f432fe5d4d2da1 

Status:  needs_work → needs_review 
New commits:
fcc0b82  21248 updated code and fixed errors

comment:24 Changed 6 years ago by
Status:  needs_review → needs_work 

A couple basic issues from the docs
in multi polynomial:
 input not formatting correctly
 check consistency in your use of the ZZ versus Z macro for integer ring
in projective:
the following do not match and does not need to be repeated twice anyway.
Still seeing issues in projective morphism See sage.rings.polynomials.reduced_form() for details. See sage.rings.polynomial.multi_polynomial.reduced_form() for the information on binary form reduction.
The following examples fail
P.<x,y>=ProjectiveSpace(QQ,1) H=End(P) f=H([x^3,y^3]) f.reduced_form()
QQbar seems to work for polys but not maps
P.<x,y>=ProjectiveSpace(QQbar,1) H=End(P) f=H([x^4,y^4]) f.reduced_form()
The behavior for RR,CC is not consistent between polynomials and morphisms
P.<x,y>=ProjectiveSpace(RR,1) H=End(P) f=H([x^4,y^4]) f.reduced_form()
vs
R.<x>=PolynomialRing(RR) F=19*x^8  262*x^7 + 1507*x^6  4784*x^5+9202*x^4  10962*x^3 + 7844*x^23040*x+475 G=F.homogenize() G.reduced_form()
comment:25 Changed 6 years ago by
Commit:  fcc0b827221635b1a5e17f95d2f432fe5d4d2da1 → 76aa6d650ab91977b5761f6b922bf8466915ab2f 

Branch pushed to git repo; I updated commit sha1. New commits:
76aa6d6  21248 fixed errors

comment:26 Changed 6 years ago by
Status:  needs_work → needs_review 

comment:27 Changed 6 years ago by
Branch:  u/rlmiller/binary → u/bhutz/binary 

comment:28 Changed 6 years ago by
Commit:  76aa6d650ab91977b5761f6b922bf8466915ab2f → 17ae0406741dc52b4c57589872fc34fe2a9a5111 

Your changes looked fine. I got this working for a few more fields by calling complex_roots directly for the roots of the polynomials. I also had to make the dividing out the gcd a little more general as well.
Go ahead and test this version and let me know what you find.
New commits:
17ae040  21248: use complex_roots for roots

comment:29 Changed 6 years ago by
typo: Implimented
typo: incresed
typo: useing covergence
typo: tolerence
comment:30 Changed 6 years ago by
Commit:  17ae0406741dc52b4c57589872fc34fe2a9a5111 → 5848b82b14a518840e52156ed10a10966d74083f 

Branch pushed to git repo; I updated commit sha1. New commits:
5848b82  21248: fixed typo, removed special casing

comment:31 Changed 6 years ago by
fixed the typo and realized since you are calling reduce on the polynomial with multiple roots, that there is no need to actually do the division. So I just count the multiple roots instead.
Just noticed the other typos. I'll push another fix for those.
comment:32 Changed 6 years ago by
Commit:  5848b82b14a518840e52156ed10a10966d74083f → 0818825cffd71e41f6e2bd4d87e562eac13cd379 

Branch pushed to git repo; I updated commit sha1. New commits:
0818825  21248: fix typos

comment:33 Changed 6 years ago by
Commit:  0818825cffd71e41f6e2bd4d87e562eac13cd379 → 1366b9e833c212418da453ec94e640c863ea5a37 

Branch pushed to git repo; I updated commit sha1. New commits:
1366b9e  21248: fixing more typos

comment:36 Changed 6 years ago by
Branch:  u/bhutz/binary → u/rlmiller/binary 

comment:37 Changed 6 years ago by
Commit:  1366b9e833c212418da453ec94e640c863ea5a37 → c00aaeb671853c4fc1c214e16dd82b1fef4be4c0 

New commits:
c00aaeb  21248 fixed spelling error

comment:38 Changed 6 years ago by
Authors:  Rebecca Lauren Miller → Rebecca Lauren Miller, Ben Hutz 

Reviewers:  Ben Hutz → Ben Hutz, Rebecca Lauren Miller 
Status:  needs_review → positive_review 
I think we're ready to go here.
comment:39 Changed 6 years ago by
Branch:  u/rlmiller/binary → c00aaeb671853c4fc1c214e16dd82b1fef4be4c0 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:40 Changed 6 years ago by
Commit:  c00aaeb671853c4fc1c214e16dd82b1fef4be4c0 

Milestone:  sage7.4 → sage7.5 
comment:41 Changed 6 years ago by
don't know what happened to the commit when I updated the milestone. I've copy/pasted the commit identifier back in.
comment:43 Changed 6 years ago by
You should rather avoid playing with the milestone once the ticket is closed.
This being said, nothing bad should happen.
Side remark: has anybody proofread this code ? there are several typos (boundry, lease, ...)
comment:44 Changed 6 years ago by
Yeah, i don't usually mess with the milestone post closing, but when it was marked positive 7.4 was still in beta, then it got released and this was closed into 7.5.
I didn't expect correcting that to interfere with other fields.
side reply: apparently not as carefully as you.
Still having some problems with the examples, and calling value errors. See notes in documentation.
New commits:
21248 Adding reduced binary form algorithm