On Tue, Jan 6, 2015 at 10:57 AM, Peter Bruin <[email protected]> wrote: > Hi William, > > Op dinsdag 6 januari 2015 19:19:30 UTC+1 schreef William stein: >> >> On Tue, Jan 6, 2015 at 9:40 AM, Peter Bruin <[email protected]> wrote: >> > >> > What exactly do you mean by "factoring as a generator function"? >> > >> >> One thing people often request for Sage is the ability to do something >> like this: >> >> sage: >> add_known_prime(23368017336614295144112598516264902899420576615151) >> >> and then whenever you do anything that might involving factoring >> integer, Sage would first do trial division by known primes. To >> implement this properly, it would be by far best to do it at the level >> of PARI, so that's pari's internal factor function respects the list >> of known primes, and uses it everywhere (e.g., when computing a >> maximal order, etc.). > > > PARI has functions addprimes() and removeprimes() to manipulate the list of > known primes, but these are currently not used by Sage.
Perfect -- that's exactly what I want. So we just need to modify sage to use them (both in the library and interpreter). > >> > I am also going to the PARI workshop and am planning to try to >> > understand >> > the modular symbols functionality. I am mostly interested in this for >> > its >> > own sake, but it would also be interesting to wrap this code in Sage as >> > an >> > alternative to the existing Sage implementation of modular symbols. >> >> I wasn't aware of that. A quick Google search finds these slides from a >> talk: >> >> http://pari.math.u-bordeaux1.fr/Events/PARI2014/talks/modsym.pdf > > > It is fairly recent; Karim Belabas and Bernadette Perrin-Riou have been > working on this on and off for some time, and Karim merged this into the > development version of PARI last June. > >> The biggest challenge, IMHO, with implementing modular symbols in pari >> for anything but toy problems -- at least in the past -- was that none >> of their linear algebra algorithms were (1) asymptotically fast, or >> (2) leveraged sparse matrix algorithms. But maybe this package >> changes that. > > > The PARI implementation seems to use somewhat different techniques than > Sage; apparently it uses less linear algebra but follows ideas from a paper > of Pollack and Stevens cited in the PARI source (basemath/modsym.py): > > Pollack and Stevens, Overconvergent modular symbols and p-adic L-functions > Annales scientifiques de l'ENS 44, fascicule 1 (2011), 1-42 > http://math.bu.edu/people/rpollack/Papers/Overconvergent_modular_symbols_and_padic_Lfunctions.pdf > > and is (at least partially) adapted from a Magma package by Darmon and > Pollack: > > Darmon and Pollack, Stark-Heegner points via overconvergent modular symbols > http://www.math.mcgill.ca/darmon/programs/shp/shp.html There's two steps -- one is getting a presentation for modular symbols -- which PARI is doing differently, and the second is actually doing something with that presentation (e.g., computing a list of Galois orbits of newforms; equivalently, a list of simple submodules). The hard asymptotically fast linear algebra issues appear only in the second step, and I think there aren't any ways to do that computation in general that avoid hard dense linear algebra problems. > >> > Apart from that, I want to try to improve linear algebra (mostly over >> > finite >> > fields) in PARI. Not sure if this is immediately useful for Sage, but >> > it >> > could be. >> >> Are there any options to link FLINT to PARI yet, which would provide a >> shortcut approach to that problem? > > > Unfortunately not, and I don't think the PARI developers have such plans. > > For some computations having to do with my research (which heavily rely on > linear algebra over finite fields), I have considered various mixes of > FLINT, PARI and Sage. Using just PARI gives the right balance between > developer time and running time for me at the moment. An alternative to > speeding up linear algebra in PARI (my current plan) would be to rewrite > much of my own code to use FLINT, but I guess working on linear algebra in > PARI is more useful generally speaking. > > Peter > > -- > You received this message because you are subscribed to the Google Groups > "sage-nt" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > Visit this group at http://groups.google.com/group/sage-nt. > For more options, visit https://groups.google.com/d/optout. -- William Stein Professor of Mathematics University of Washington http://wstein.org -- You received this message because you are subscribed to the Google Groups "sage-nt" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send an email to [email protected]. Visit this group at http://groups.google.com/group/sage-nt. For more options, visit https://groups.google.com/d/optout.
