Opened 2 years ago

Closed 22 months ago

Last modified 22 months ago

#21248 closed enhancement (fixed)

Reduce Forms from Stoll and Cremona

Reported by: rlmiller Owned by:
Priority: minor Milestone: sage-7.5
Component: algebra Keywords:
Cc: bhutz, paulfili Merged in:
Authors: Rebecca Lauren Miller, Ben Hutz Reviewers: Ben Hutz, Rebecca Lauren Miller
Report Upstream: N/A Work issues:
Branch: c00aaeb (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by rlmiller)

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 2 years ago by rlmiller

  • Branch set to u/rlmiller/binary

comment:2 Changed 2 years ago by rlmiller

  • Cc bhutz paulfili added
  • Commit set to 0544a244e4199c6d89e1d76ceae593c71bc57c71
  • Description modified (diff)
  • Status changed from new to needs_review

Still having some problems with the examples, and calling value errors. See notes in documentation.


New commits:

0544a2421248 Adding reduced binary form algorithm

comment:3 Changed 2 years ago by bhutz

  • Status changed from needs_review to needs_work

Well, the first step here is to move from 7.3beta4 to 7.4beta0.

Let's leave this as needs-work until the issues are worked out.

comment:4 Changed 2 years ago by bhutz

  • Branch changed from u/rlmiller/binary to u/bhutz/binary

comment:5 Changed 2 years ago by git

  • Commit changed from 0544a244e4199c6d89e1d76ceae593c71bc57c71 to f77747650f4a02a0bda698591913df7c27e6e17c

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

f77747621248: some clean-up and minor error fixing

comment:6 Changed 2 years ago by bhutz

I did some code/formatting clean-up 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 2 years ago by rlmiller

  • Branch changed from u/bhutz/binary to u/rlmiller/binary

comment:8 Changed 2 years ago by rlmiller

  • Commit changed from f77747650f4a02a0bda698591913df7c27e6e17c to dcc7a4ae8d11eb006afd5cdd1b20a5edc46294cc

Still need a few more examples, having problems with two examples in projective_morphism.py They worked in the notebook.


New commits:

dcc7a4a21248 Reduced Binary form, added examples and documentation

comment:9 Changed 2 years ago by bhutz

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

  • Commit changed from dcc7a4ae8d11eb006afd5cdd1b20a5edc46294cc to 93e8aeaef71bdda2bac6a631f30b190e96b63059

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

93e8aea21248 added example fixed errors

comment:11 Changed 2 years ago by rlmiller

  • Status changed from needs_work to needs_review

comment:12 Changed 2 years ago by bhutz

  • Reviewers set to Ben Hutz
  • Status changed from needs_review to 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 2 years ago by bhutz

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

  • Commit changed from 93e8aeaef71bdda2bac6a631f30b190e96b63059 to 6f744f64a9d6feb4ee2d6f4ebb28d4e0944fc71c

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

6f744f621248 fixed error

comment:15 Changed 2 years ago by git

  • Commit changed from 6f744f64a9d6feb4ee2d6f4ebb28d4e0944fc71c to f2bd1736ddc0ce63646d408c34c7120d9d84c0b6

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

f2bd17321248 fixed errors added comments

comment:16 Changed 2 years ago by git

  • Commit changed from f2bd1736ddc0ce63646d408c34c7120d9d84c0b6 to 33e99418a4b3f233520cb9080682c05b159fa7b1

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

33e994121248 fixed documentaion

comment:17 Changed 2 years ago by bhutz

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

  • Commit changed from 33e99418a4b3f233520cb9080682c05b159fa7b1 to a47a5889938f75ec474327f1ce3a54618eb25669

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

a47a58821248 fixed errors

comment:19 Changed 2 years ago by rlmiller

  • Status changed from needs_work to needs_review

comment:20 Changed 23 months ago by bhutz

  • Branch changed from u/rlmiller/binary to u/bhutz/binary

comment:21 Changed 23 months ago by bhutz

  • Commit changed from a47a5889938f75ec474327f1ce3a54618eb25669 to 807efb0dbca2ad5700dd705a7ca255253fd0a79b
  • Status changed from needs_review to needs_work

I did some general code clean-up 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:

807efb021248: general code and documentation clean-up

comment:22 Changed 23 months ago by rlmiller

  • Branch changed from u/bhutz/binary to u/rlmiller/binary

comment:23 Changed 23 months ago by rlmiller

  • Commit changed from 807efb0dbca2ad5700dd705a7ca255253fd0a79b to fcc0b827221635b1a5e17f95d2f432fe5d4d2da1
  • Status changed from needs_work to needs_review

New commits:

fcc0b8221248 updated code and fixed errors

comment:24 Changed 23 months ago by bhutz

  • Status changed from needs_review to 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^2-3040*x+475
G=F.homogenize()
G.reduced_form()

comment:25 Changed 23 months ago by git

  • Commit changed from fcc0b827221635b1a5e17f95d2f432fe5d4d2da1 to 76aa6d650ab91977b5761f6b922bf8466915ab2f

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

76aa6d621248 fixed errors

comment:26 Changed 23 months ago by rlmiller

  • Status changed from needs_work to needs_review

comment:27 Changed 23 months ago by bhutz

  • Branch changed from u/rlmiller/binary to u/bhutz/binary

comment:28 Changed 23 months ago by bhutz

  • Commit changed from 76aa6d650ab91977b5761f6b922bf8466915ab2f to 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:

17ae04021248: use complex_roots for roots

comment:29 Changed 23 months ago by chapoton

typo: Implimented

typo: incresed

typo: useing covergence

typo: tolerence

Last edited 23 months ago by chapoton (previous) (diff)

comment:30 Changed 23 months ago by git

  • Commit changed from 17ae0406741dc52b4c57589872fc34fe2a9a5111 to 5848b82b14a518840e52156ed10a10966d74083f

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

5848b8221248: fixed typo, removed special casing

comment:31 Changed 23 months ago by bhutz

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 23 months ago by git

  • Commit changed from 5848b82b14a518840e52156ed10a10966d74083f to 0818825cffd71e41f6e2bd4d87e562eac13cd379

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

081882521248: fix typos

comment:33 Changed 23 months ago by git

  • Commit changed from 0818825cffd71e41f6e2bd4d87e562eac13cd379 to 1366b9e833c212418da453ec94e640c863ea5a37

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

1366b9e21248: fixing more typos

comment:34 Changed 23 months ago by chapoton

covergence conditions is still a typo

comment:35 Changed 23 months ago by rlmiller

Typo fixed just waiting to push. Thanks

comment:36 Changed 23 months ago by rlmiller

  • Branch changed from u/bhutz/binary to u/rlmiller/binary

comment:37 Changed 23 months ago by rlmiller

  • Commit changed from 1366b9e833c212418da453ec94e640c863ea5a37 to c00aaeb671853c4fc1c214e16dd82b1fef4be4c0

New commits:

c00aaeb21248 fixed spelling error

comment:38 Changed 23 months ago by bhutz

  • Authors changed from Rebecca Lauren Miller to Rebecca Lauren Miller, Ben Hutz
  • Reviewers changed from Ben Hutz to Ben Hutz, Rebecca Lauren Miller
  • Status changed from needs_review to positive_review

I think we're ready to go here.

comment:39 Changed 22 months ago by vbraun

  • Branch changed from u/rlmiller/binary to c00aaeb671853c4fc1c214e16dd82b1fef4be4c0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:40 Changed 22 months ago by bhutz

  • Commit c00aaeb671853c4fc1c214e16dd82b1fef4be4c0 deleted
  • Milestone changed from sage-7.4 to sage-7.5

comment:41 Changed 22 months ago by bhutz

don't know what happened to the commit when I updated the milestone. I've copy/pasted the commit identifier back in.

comment:42 Changed 22 months ago by bhutz

apparently, that doesn't work. Have I messed up this ticket now?

comment:43 Changed 22 months ago by chapoton

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 22 months ago by bhutz

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.

Note: See TracTickets for help on using tickets.