[sage-devel] Re: sage-2.8.5 on ia64-Linux
On Sep 24, 10:53 pm, Kate Minola [EMAIL PROTECTED] wrote: William, Hello Kate, While trying to build sage-2.8.5 on ia64-Linux using gcc-4.2.1: 1. For flint-0.2.p2, I had to remove the CFLAG option -funroll-loops in order to get it to build. Interesting - which gcc are you using? 4.2.1? 2. For iml-1.0.1.p8, there is some autotools problem that I have not been able to track down. Is everything up-to-date with configure, etc. for this package? William reran autoconf after I patched in some stuff to fix some issue on OSX. The spkg with the fixes but with the old autoconf build are at http://sage.math.washington.edu/home/mabshoff/iml-1.0.1.p7.spkg You can give it a try and let us know if that fixes your problem. (My itanium machine does NOT have the latest autotools installed.) Kate Cheers, Michael -- Kate Minola University of Maryland, College Park --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: Some thought on trac and the Sage development process - feedback wanted
Hello, hopefully I incorporated all feed back: *Better Sage Project Management With The Help of Trac - rev 2* # Opening Remarks # The is more about than just the use of trac to help out with Sage development, but also about work flow in general and how we can make developing Sage more efficient now that more and more developers are joining Sage. # The Situation # * The use of trac seems to work out well. It seems that we do not lose bug reports and issues keep getting added to make sure they do not disappear. everything you work on is a ticket rule has been accepted by the vast majority of developers. * The number of open tickets keeps on rising (from about 220 to slightly under 300 at the moment), but turnover is rather high. The increased numbers of bugs found and enhancements requested is a good sign because it shows that Sage is being used by more and more people and that people care enough to report problems. Many times I have looked for software to do a specific task and encountered bugs. I ususally do neither attempt to fix the problem nor report it unless it is something I see potential in. * Bug Days have closed up to 70 ticker, the lower bounds seems to be about 40. It will be interesting to see how many tickets will be closed/opened during SD5. * The old cruft, i.e. tickets closed along the way, that were left in trac seems to have all been closed. * If you do development for Sage or consider yourself a user who wants to report issues get an account for Sage's trac installation: either email William Stein or alternatively contact him on #sage-devel on freenode. Preferably get a tray account with the same name as your google group nickname, so that one know how to contact you. # Releases, Milestones vs. Releases # * Milestones are usually goals to be met while working toward a release. In Sage's trac we use milestones instead of releases, but unless somebody volunteers to clean up all the old milestones we will stick with the current model. It doesn't make a whole lot of a difference if we use milestone instead of release. * finely grained releases are good, release early and often is the way to go, especially as more and more patches are coming in. * it is realistic to make a big release and schedule at least one bugfix release after that to sort out the inevitable doctest X is broken on distribution Y and compiler Z problem. If we ever get access to a compile farm the number of those issues will hopefully decrease, but given the number of compilers and operating systems out there one has to be realistic to expect problems. # Opening Tickets # * Before opening a ticket make sure that nobody else has opened a ticket about the same or closely related issue. * It is better to open several specific tickets than one that is very broad. * Be precise: If foo doesn't work on OSX, but is fine on Linux mention that in the title, also use the keyword option to make searches pick up the issue * be careful with the priority: blocker should be used sparingly, don't be surprised that such a ticker is reclassified. On the other hand tickets that one might consider to be of non-blocker quality might be promoted. When in doubt write an email to sage-devel or ask around on #sage-devel. # Working On Tickets # * Every bug fixed should result in a doctest: Example Zombie det() problem with LinBox, considered fixed twice, but reopened in both cases. * Cooperative debugging via IRC is faster by at least a magnitude. If you haven't learned how to use IRC please do so. If you have problems to use IRC because of firewalls, but you do have an account on sage.math you can use irssi via ssh there. If you have a flaky connection (hello malb ;) - you can use it together with screen. * This is mostly an issue with defects, there are many enhancements possible for Sage, but too few developers to implement all the good ideas. But it is useful to keep ideas in a central place because in the google groups they tend to get lost once they drop off the first page * If you are a developer be nice and try to solve a stale/old ticket every once in a while. * mhansen and I (and some other people I properly forgot to mention) regularly do triage, especially before Bug Days. Triage in this context means that we look at new bugs and classify them according to out perceived priority. # Assigning Tickets # * each ticket should have a milestone assigned * defect vs. enhancement vs. task * if you are unsure whom to assign to assign to somebody or was * certain categories have default people to assign to * if you have been assigned a ticket you should either accept it or assign it back to somebody or tbd # Closing Tickets # * if you have a solution/patch attach it to the ticket and indicate that there is a solution available by adding [with patch] to the title. It might also be a good idea to reassign the ticket to the
[sage-devel] Re: Proposed minor enhancement: elliptic curve transformations
Hi John, Group -- WierstrassIsomorphismGroup GroupElement -- WeierstrassIsomorphism OK I'll try that. On this subject, I had the idea that an Iso(X,Y) subset of Hom(X,Y) should be defined for every category. Note that the subset Aut(X) of an End(X) is a group, but in general the WeierstrassIsomorphism class are (two- sided) G-sets (over Aut(X) and Aut(Y)) but not groups. Thus I think they should have some inheritance like Morphism - EllipticCurveIsogeny - EllipticCurveIsomorphism, The middle class could be skipped for the moment. Within the category of abelian varieties, we can assume 0 goes to 0. In the future it might be of interest to have special classes of genus 1 curves which might admit more general isomorphisms, but they will no longer be given by linear transformations, which reduce to coefficients [u,r,s,t] of an (upper triangular) matrix. You could cc me in relevant messages to make sure that I response -- we have a one-week teaching break, but need to pack up my office this week. --David --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: gmp 4.2.2 LGPL V3 issues and other minor tidbits
Actually GMP is far from stale. Anyway, I put the chances of a viable GMP fork in the next year at 1% (see below). It would be very useful to figure out what the situation is with Singular's licensing plans. Do they have a mailing list or something? -- William Why I think GMP won't be fork: Torbjörn is really the organizing force behind GMP, as far as I can tell, and he seems completely OK with LGPLv3 as a license for GMP.I don't know of any serious players who have the necessary resources and who are interested in forking GMP, and the license change from LGPLv2 to LGPLv3 likely has no impact on Maple and almost none on Magma.Basically before any of this LGPLv3 stuff, various people have made noise about forking GMP for more serious reasons, and nothing happened, so I doubt it would happen now. I also have serious doubts that GMP will be successfully forked. I looked into doing this myself, and the simple, painful, truth is that the build scripts in GMP are more complicated than the mathematics. (And, several times a year, someone on the GMP mailing lists suggests forking the project, to which Torbjörn always responds, go ahead, but I can't find any successful GMP forks on the web.) Maintaining build scripts for assembly level code for hundreds of platforms has got to be a painfully tedious task that no one else wants to take on. Torbjörn may be somewhat tough to work with, but you have to give the guy credit: he's probably one of the best all around programmers on the planet. So, I think that there is only one realistic option: Sage must go v2 or later. --jason --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: number fields
Well that answered my next question, which is whether this method could be used for Qbar. Carl, what language is your code in. I would be interested in taking a look. Bill. On 23 Sep, 20:15, William Stein [EMAIL PROTECTED] wrote: On 9/23/07, cwitty [EMAIL PROTECTED] wrote: Here's one (heavily biased) example: sage: sum([sqrt(AA(i)) for i in range(1, 1000)]) [21065.833110879048 .. 21065.833110879056] I'm pretty sure that doing computations with this number algebraically requires dealing with polynomials of degree at least 2^168 (there are 168 primes less than 1000), which is obviously impossible. It is also possible to do very fast arithmetic in QQbar building on AA as illustrated below: sage: R.x = AA[] sage: Q.i = R.quotient(x^2 + 1) sage: w = i * AA(3).sqrt(); w [1.7320508075688771 .. 1.7320508075688775]*i sage: omega = (1 + w)/2; omega [0.86602540378443859 .. 0.86602540378443871]*i + 1/2 sage: omega^3 [-1.0003 .. -0.99988] sage: omega + AA(5).sqrt() [0.86602540378443859 .. 0.86602540378443871]*i + [2.7360679774997893 .. 2.7360679774997899] sage: z1 = omega = (1 + w)/2; omega [0.86602540378443859 .. 0.86602540378443871]*i + 1/2 sage: z1 = omega = (1 + w)/2 + sqrt(AA(5)) sage: z1 [0.86602540378443859 .. 0.86602540378443871]*i + [2.7360679774997893 .. 2.7360679774997899] sage: z1^10 [2882.8577427505738 .. 2882.8577427505789]*i + [-37786.733390210728 .. -37786.733390210720] sage: (z1^10)[0].minpoly() x^2 + 37851*x + 9713701/4 sage: (z1^10)[1].minpoly() x^4 - 17754903/2*x^2 + 75340716089409/16 This could probably be useful for some applications. William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: sage-2.8.5 on ia64-Linux
On Sep 24, 10:53 pm, Kate Minola [EMAIL PROTECTED] wrote: While trying to build sage-2.8.5 on ia64-Linux using gcc-4.2.1: 1. For flint-0.2.p2, I had to remove the CFLAG option -funroll-loops in order to get it to build. ?? ?? ? I tried to find information on why this might be a problem. But came up blank. Can you by any chance give a list of the errors which result. Perhaps it is not related directly to the unroll-loops option itself, but a strange interaction with something else. Bill. P.S: David Harvey set up a trac server for FLINT and I'm about to start using it now that bits and pieces of FLINT are finding themselves in SAGE. People can email me to get an account if required. All bugs which prevent SAGE from being built should be filed as major bugs. http://sage.math.washington.edu:2/flint_trac --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: number fields
On Sep 25, 8:02 am, Bill Hart [EMAIL PROTECTED] wrote: Well that answered my next question, which is whether this method could be used for Qbar. The biggest obstacle to handling Qbar directly is that I haven't found a good way of isolating the roots of a complex polynomial (that is, finding the roots with a GUARANTEED error bound) and then refining a root to arbitrary precision. (The other annoying part is that SAGE does not yet have complex interval arithmetic.) And the third obstacle is that at the moment, I only care about real numbers; so I'm not very motivated to work on the extension to Qbar. :-) (Although I'd be happy to answer questions, if anybody else wanted to work on it!) Carl, what language is your code in. I would be interested in taking a look. The part I wrote is just Python (although it makes heavy use of the rest of SAGE); it's in .../sage/rings/algebraic_real.py . Bill. Carl --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: number fields
I thought this had been solved some time ago, and was implemented in pari. Or is that only for real roots of real polynomials? John On 9/25/07, cwitty [EMAIL PROTECTED] wrote: On Sep 25, 8:02 am, Bill Hart [EMAIL PROTECTED] wrote: Well that answered my next question, which is whether this method could be used for Qbar. The biggest obstacle to handling Qbar directly is that I haven't found a good way of isolating the roots of a complex polynomial (that is, finding the roots with a GUARANTEED error bound) and then refining a root to arbitrary precision. (The other annoying part is that SAGE does not yet have complex interval arithmetic.) And the third obstacle is that at the moment, I only care about real numbers; so I'm not very motivated to work on the extension to Qbar. :-) (Although I'd be happy to answer questions, if anybody else wanted to work on it!) Carl, what language is your code in. I would be interested in taking a look. The part I wrote is just Python (although it makes heavy use of the rest of SAGE); it's in .../sage/rings/algebraic_real.py . Bill. Carl -- John Cremona --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: making new infix operators
In SAGE, '+' is used for union of sets. For example,
sage: a = Set([1,2])
sage: b = Set([2,3])
sage: a+b
{1, 2, 3}
Since currently, + is not defined for graphs, it'd be a natural choice.
--Mike
On 9/25/07, Jason Grout [EMAIL PROTECTED] wrote:
I'm thinking more about how to make the Graph class easy to use. One
thing that crops up is that the operations that combine graphs only
combine two graphs at a time (e.g., g.union(h), where g and h are graphs).
Is there a way to define an infix operator that would allow one to say:
g union h union i union j union k?
I could do it with something like:
reduce(lambda x,y: x.union(y), [g,h,i,j,k])
But that doesn't seem as clear as the infix things above.
For reference, Mathematica allows an operator in backticks to be applied
to its surrounding arguments, so the equivalent operation above would be:
g `union` h `union` i `union` j `union` k
And of course, you can set whether the operator is left-associative or
right-associative.
Of course, one solution is to use a for loop:
newgraph=Graph()
for graph in [g,h,i,j,k]:
newgraph.union(graph)
But that seems a lot clunkier than the infix expression above.
I guess another solution is to return the new graph from the union, so
that you could do:
g.union(h).union(i).union(j)
Thoughts?
-Jason
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~--~~~~--~~--~--~---
[sage-devel] Re: making new infix operators
I would appreciate any tips on how to extend the + operator in this
way, since I would like to implement Minkowski sums of polytopes and
this is natural notation for that.
Marshall
On Sep 25, 10:37 am, Mike Hansen [EMAIL PROTECTED] wrote:
In SAGE, '+' is used for union of sets. For example,
sage: a = Set([1,2])
sage: b = Set([2,3])
sage: a+b
{1, 2, 3}
Since currently, + is not defined for graphs, it'd be a natural choice.
--Mike
On 9/25/07, Jason Grout [EMAIL PROTECTED] wrote:
I'm thinking more about how to make the Graph class easy to use. One
thing that crops up is that the operations that combine graphs only
combine two graphs at a time (e.g., g.union(h), where g and h are graphs).
Is there a way to define an infix operator that would allow one to say:
g union h union i union j union k?
I could do it with something like:
reduce(lambda x,y: x.union(y), [g,h,i,j,k])
But that doesn't seem as clear as the infix things above.
For reference, Mathematica allows an operator in backticks to be applied
to its surrounding arguments, so the equivalent operation above would be:
g `union` h `union` i `union` j `union` k
And of course, you can set whether the operator is left-associative or
right-associative.
Of course, one solution is to use a for loop:
newgraph=Graph()
for graph in [g,h,i,j,k]:
newgraph.union(graph)
But that seems a lot clunkier than the infix expression above.
I guess another solution is to return the new graph from the union, so
that you could do:
g.union(h).union(i).union(j)
Thoughts?
-Jason
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~--~~~~--~~--~--~---
[sage-devel] Re: [SAGE Days 5] Re: Fwd: [sage-devel] SAGE days 6 and GPLv3
John Cremona wrote: If it has been decided not to invite someone from FSF to SD6 then that is fine with me. There seems to be some confusion between SD5 and SD6. Jaap --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: [SAGE Days 5] Re: Fwd: [sage-devel] SAGE days 6 and GPLv3
On 9/25/07, Jaap Spies [EMAIL PROTECTED] wrote: John Cremona wrote: If it has been decided not to invite someone from FSF to SD6 then that is fine with me. There seems to be some confusion between SD5 and SD6. No: you suggested this for SD6, then the SD5 organisers thought SD5 would be better being in Boston, but decided against it, and their reason for doing so is also valid, I think, for SD6. So as an SD6 organiser I vote against. By the way, SD6 is being entirely funded by the Heilbronn Institute for Mathematical Research in Bristol. John Jaap -- John Cremona --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: making new infix operators
Mike Hansen wrote: Since I don't think that graphs and polytopes fall under the SAGE coercion model, overloading operators is pretty straightforward. You just need to define the __add__ method in your class. x + y will call x.__add__(y). sage: class Foo: : def __add__(self, y): : return 42 : sage: a = Foo() sage: b = Foo() sage: a + b 42 sage: b + a 42 Note that you'll want to do some type-checking so that y is what you actually think it should be. Thanks! Knowing what to look for, google pulled up the following page from the python website, delineating the overloadable operators: http://docs.python.org/ref/numeric-types.html I put this here for future reference. Thanks, Jason --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: gmp 4.2.2 LGPL V3 issues and other minor tidbits
On 9/25/07, Bill Hart [EMAIL PROTECTED] wrote: If SAGE developers weren't so thin on the ground, I'm sure that we could fork GMP. I'd be interested in doing so, for various reasons. There's already code in the FLINT project which could go straight into a forked GMP. I'd also like to get around to providing decent assembly support for the PS3. But I alone do not have the time to maintain such an enormous package, especially given that I'm already codeveloper of FLINT. A group of us could manage it, I'm sure. But whether it would be successful, I couldn't say. I feel precisely the same way. I also hope Sage developers will become a bit more thick on the ground. That said, it might be good to think about what team would do a GMP fork, if it were to happen, just in case. Probably you, me, Jason Martin, ?? Jason Martin remarked: Maintaining build scripts for assembly level code for hundreds of platforms has got to be a painfully tedious task that no one else wants to take on. The first thing I would do if I forked GMP would be to greatly reduce the number of supported platforms, in the same way that Ubuntu supports far fewer platforms than Debian. I would chose the same platforms that Sage targets (and that Sage *wants* to target). The second thing I would do is release the forked version (i.e., all _new_ code in the forked version) under GPL (not LGPL) to prevent usage by Maple/Magma of our version. The third thing would be to integrate in all the patches to GMP that we currently distribute that aren't part of the official GMP. The fourth thing would be to choose a new name for the project.The fifth thing would be to setup a website with bug tracker, wiki, mailing lists, and all the other standard tools of an open source project. That sounds like a lot of work. I'm glad I'm not forking GMP. -- William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: gmp 4.2.2 LGPL V3 issues and other minor tidbits
At this point it looks like the only reasonable option is to (begrudgingly) move to GPLv2 or above but there is another option that I haven't seen come up in discussion yet, and that is releasing SAGE under an amended GPLv2 that explicitly allows linking against LGPLv3+ libraries (or some other compatibility clause). This would free us from being at the mercy of whatever the FSF decides is a good idea 10 years from now, or even what they decided this last year. In doing this, however, we would loose what to me is the biggest advantage of the GPL over all the other copyleft Open Source licenses out there, namely that one merely has to say this code is GPL and everyone has an idea (of varying accuracy) what you're talking about. Also, it would only cover LGPL code, not anything GPL. I am not convinced that this is the best idea, I just wanted to throw it out there. - Robert On Sep 23, 2007, at 11:34 AM, William Stein wrote: On 9/23/07, Mike Hansen [EMAIL PROTECTED] wrote: It seems odd that closed source software could use GMP under the LGPLv3, but that a GPLv2 project could not. How tightly integrated is the GMP stuff? Aren't we pretty much just using it as a library? We are just using it as a library. The problem isn't LGPLv3, but GPLv2 itself! But please see http://gplv3.fsf.org/dd3-faq where it is made crystal clear that in fact a GPLv2 project can't even use an LGPLv3 library in library-only mode. There is a discussion here: http://lwn.net/Articles/241065/ In short, Magma and Maple can use GMP under LGPLv3, but Sage can't, because Sage is GPLv2, and the GPLv2 specifically disallows linking against libraries that are more restrictive (except things like the C library). -- William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: number fields
Could the version for complex numbers use polar coordinates? Bill. On 25 Sep, 18:55, cwitty [EMAIL PROTECTED] wrote: On Sep 25, 9:28 am, John Cremona [EMAIL PROTECTED] wrote: I thought this had been solved some time ago, and was implemented in pari. Or is that only for real roots of real polynomials? John On 9/25/07, cwitty [EMAIL PROTECTED] wrote: The biggest obstacle to handling Qbar directly is that I haven't found a good way of isolating the roots of a complex polynomial (that is, finding the roots with a GUARANTEED error bound) and then refining a root to arbitrary precision. Maybe so, but the documentation doesn't give enough detail for me to be confident. The documentation for Pari's polroots function says, ... it is guaranteed to converge and to give the roots to the required accuracy. But I don't know what that means. Am I supposed to trust every bit of the returned value (that is, the error is at most a half-ULP)? I'm fairly sure I could construct examples where determining a 100-bit result to within a half-ULP would require intermediate values that were a million bits. Does Pari go ahead and use the million-bit numbers here, or does it allow errors more than a half-ULP? If it allows errors more than a half-ULP, how large are the errors it does allow? Worse, I need to work with polynomials with inexact (interval) coefficients, and polynomial root-finding is inherently unstable (small changes in the coefficients can make large changes in the locations of the roots); even if Pari gives exactly-correct (within a half-ULP) answers for the polynomials you give it, how much do you increase the size of the interval outputs to account for the uncertainty in the inputs? All of this is to support a constructor that takes a polynomial with Qbar coefficients, and a complex interval (a rectangle in the complex plane) enclosing exactly one root, and return an element of Qbar. Instead, there could be a constructor that takes a polynomial with Qbar coefficients, and a complex interval enclosing exactly one root tightly enough that it can be arbitrarily refined using Newton- Raphson; and then it would be the responsibility of the caller to find such a complex interval. But how would the caller do that? Carl --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: number fields
I don't think that would help. It would make mult/div nicer, but addition/subtraction more of a mess. I think the best analogue of an interval is a ball--addition and subtraction of open balls yield open balls, and multiplication/division of open balls are almost open balls (for inputs far enough away from the origin with respect to their radii). - Robert On Sep 25, 2007, at 11:07 AM, Bill Hart wrote: Could the version for complex numbers use polar coordinates? Bill. On 25 Sep, 18:55, cwitty [EMAIL PROTECTED] wrote: On Sep 25, 9:28 am, John Cremona [EMAIL PROTECTED] wrote: I thought this had been solved some time ago, and was implemented in pari. Or is that only for real roots of real polynomials? John On 9/25/07, cwitty [EMAIL PROTECTED] wrote: The biggest obstacle to handling Qbar directly is that I haven't found a good way of isolating the roots of a complex polynomial (that is, finding the roots with a GUARANTEED error bound) and then refining a root to arbitrary precision. Maybe so, but the documentation doesn't give enough detail for me to be confident. The documentation for Pari's polroots function says, ... it is guaranteed to converge and to give the roots to the required accuracy. But I don't know what that means. Am I supposed to trust every bit of the returned value (that is, the error is at most a half-ULP)? I'm fairly sure I could construct examples where determining a 100-bit result to within a half-ULP would require intermediate values that were a million bits. Does Pari go ahead and use the million-bit numbers here, or does it allow errors more than a half-ULP? If it allows errors more than a half-ULP, how large are the errors it does allow? Worse, I need to work with polynomials with inexact (interval) coefficients, and polynomial root-finding is inherently unstable (small changes in the coefficients can make large changes in the locations of the roots); even if Pari gives exactly-correct (within a half-ULP) answers for the polynomials you give it, how much do you increase the size of the interval outputs to account for the uncertainty in the inputs? All of this is to support a constructor that takes a polynomial with Qbar coefficients, and a complex interval (a rectangle in the complex plane) enclosing exactly one root, and return an element of Qbar. Instead, there could be a constructor that takes a polynomial with Qbar coefficients, and a complex interval enclosing exactly one root tightly enough that it can be arbitrarily refined using Newton- Raphson; and then it would be the responsibility of the caller to find such a complex interval. But how would the caller do that? Carl --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: number fields
On Sep 25, 10:10 am, Bill Hart [EMAIL PROTECTED] wrote: Actually, someone sent me some very good code for doing complex root approximation in FLINT. But I've been too damned lazy to properly incorporate it in FLINT. I will get around to it soon. Carl if you can give me a specific interface that you'd like, I can put some thought into implementing it and it will eventually get done. A lot of it depends on what people would want from an implementation of Qbar. Aside from the standard arithmetic operations (+, -, *, /, nth root), how should elements of Qbar be created? I assume there needs to be at least one constructor that takes a polynomial and indicates one particular complex root of that polynomial. Do people need polynomials with Qbar coefficients, or would construction from polynomials with rational coefficients suffice? Or maybe the constructor should take a Qbar polynomial and return a list of all its roots (as elements of Qbar)? If you want to construct an element of Qbar from a polynomial, do you already know that the polynomial is squarefree, or does the constructor need to check? Carl --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: number fields
On Sep 25, 11:24 am, Bill Hart [EMAIL PROTECTED] wrote: Actually, to make it work, it might have to switch between polar coordinates and rectangular coordinates, always ensuring the point you are talking about is inside the region, regardless of whether it is a polar rectangle or a right rectangle. Clearly I don't know anything about complex interval arithmetic if such a thing exists. Is there a reference I can read. Shame you aren't going to be at SAGE days 5 Carl. Are you going to number 6. Bill. I know very little about complex interval arithmetic myself...just what I learned from Googling for complex interval arithmetic and spending a couple of hours skimming papers I found on the Web. Some implementations use intervals represented as circles in the complex plane; others use right rectangles. I don't remember any that use polar rectangles, but they might exist. In any case, if you want the tightest possible bounds, there's some fairly tricky math. Fortunately, for implementing Qbar, I'm pretty sure we wouldn't need an implementation of complex interval arithmetic that was carefully optimized to get the tightest possible bounds. I believe (although I haven't gone through the math to check) that the extra looseness of the simple algorithms is mostly a problem if the original bounds were loose relative to the number. However, if Qbar were implemented similarly to my algebraic reals package, we start with very tight bounds, and the result of a precision error is to make the bounds much much tighter. So I think the simplest possible implementation (a complex interval is a pair of real intervals, and arithmetic operations are implemented textbook fashion using these real intervals) would probably suffice. No, I'm not planning to go to SD6. (After all, computer algebra is only a hobby for me!) Carl --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: number fields
Qbar means different things to different people (or to the same people at different times). Carl's view is to have Qbar fixed as a subfield of C so that an element of Qbar is represented as a (necessarily approximate) complex value together with its minimal polynomial. Number theorists and algebraists would like a more general viewpoint, to allow p-adics to enter the picture for example. If you have just one algebraic number a with minimal polynomial f(x) then the algebraist can be happy working with the abstract field K=Q[x]/(f(x)); this can be embedded into any larger field L (such as C) in which f has a root alpha just by mapping x to alpha; and if there are several roots then there will be that many different embeddings (into the same L). It gets more complicated if you now introduce a second algebraic number b with minimum polynomial g(x), defineing a second abstract field K'=Q[x]/(g(x)). How do add a to b, since they live in entirely different worlds? The algebraists approach is that this only makes sense if you have field L into which both K and K' embed and you do arithmetic in L. Taken to the limit (literally) one arrives at Qbar as the direct limit of all fields like K, which in abstract terms is obtained by taking the disjoint union of all the K=Q[x]/(f(x)) together with embeddings between these, and identifying two elements if they have the same image in a field containing both. Our discussion about how to make sense of symbolic expressions like sqrt(2)+sqrt(3)-sqrt(6) is relevant here. To make sense of this expression you need not only the individual fields Q(sqrt(a)) for a=2, 3, 6; you need a single field L containing sqrts of all three numbers, together with those embeddings, i.e. a labelling of *which* root of x^2-2 in this big field is the one which you want the abstract sqrt(2) to. One solution mentioned previously takes L=R (reals) and labels the positive roots. But, as we have seen that simple solution breaks down quickly for more complicated algebraic numbers. Excuse the ramblings: but I always find that computational ambiguities like this are best understood by treating the mathematics seriously! John On 9/25/07, cwitty [EMAIL PROTECTED] wrote: On Sep 25, 11:24 am, Bill Hart [EMAIL PROTECTED] wrote: Actually, to make it work, it might have to switch between polar coordinates and rectangular coordinates, always ensuring the point you are talking about is inside the region, regardless of whether it is a polar rectangle or a right rectangle. Clearly I don't know anything about complex interval arithmetic if such a thing exists. Is there a reference I can read. Shame you aren't going to be at SAGE days 5 Carl. Are you going to number 6. Bill. I know very little about complex interval arithmetic myself...just what I learned from Googling for complex interval arithmetic and spending a couple of hours skimming papers I found on the Web. Some implementations use intervals represented as circles in the complex plane; others use right rectangles. I don't remember any that use polar rectangles, but they might exist. In any case, if you want the tightest possible bounds, there's some fairly tricky math. Fortunately, for implementing Qbar, I'm pretty sure we wouldn't need an implementation of complex interval arithmetic that was carefully optimized to get the tightest possible bounds. I believe (although I haven't gone through the math to check) that the extra looseness of the simple algorithms is mostly a problem if the original bounds were loose relative to the number. However, if Qbar were implemented similarly to my algebraic reals package, we start with very tight bounds, and the result of a precision error is to make the bounds much much tighter. So I think the simplest possible implementation (a complex interval is a pair of real intervals, and arithmetic operations are implemented textbook fashion using these real intervals) would probably suffice. No, I'm not planning to go to SD6. (After all, computer algebra is only a hobby for me!) Carl -- John Cremona --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: gmp 4.2.2 LGPL V3 issues and other minor tidbits
This is not an option. From GPL2: 2. ... b) You must cause any work that you distribute or publish, that in whole or in part contains or is derived from the Program or any part thereof, to be licensed as a whole at no charge to all third parties under the terms of this License. From GPL3: These requirements apply to the modified work as a whole. If identifiable sections of that work, added by you, are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works for use not in combination with the Program. But when you distribute the same sections for use in combination with covered works, no matter in what form such combination occurs, the whole of the combination must be licensed under this License, whose permissions for other licensees extend to the entire whole, and thus to every part of the whole. Your sections may carry other terms as part of this combination in limited ways, described in section 7. Hence, if Sage cannot function without GPL3 software, it *must* be licensed under GPL3, and no other license. Therefore, GPL2 or later truly means GPL3 the instant that we include gmp4.2.2, no matter what we might tell ourselves. Similarly, if there is a library which is GPL2 only, we cannot include it once we've included gmp4.2.2. This is utterly ridiculous, but apparently a fact of life. rantWith all of RMS's talk about subjugation, and Microsoft forcing people into using their software, he seems pretty happy to force people into using the new license, and cause others to turn around and pressure their friends to do the same -- does this remind anybody else of the early days of communism in China? Oh, wait. No. I almost forgot: people aren't getting *killed* for doing or not doing these things -- what's subjugation mean again?/rant Anyway. Sorry for that. I found this link useful: http://www.groklaw.net/articlebasic.php?story=20060118155841115 and I got the above quotes from row #5. On Tue, 25 Sep 2007, Robert Bradshaw wrote: At this point it looks like the only reasonable option is to (begrudgingly) move to GPLv2 or above but there is another option that I haven't seen come up in discussion yet, and that is releasing SAGE under an amended GPLv2 that explicitly allows linking against LGPLv3+ libraries (or some other compatibility clause). This would free us from being at the mercy of whatever the FSF decides is a good idea 10 years from now, or even what they decided this last year. In doing this, however, we would loose what to me is the biggest advantage of the GPL over all the other copyleft Open Source licenses out there, namely that one merely has to say this code is GPL and everyone has an idea (of varying accuracy) what you're talking about. Also, it would only cover LGPL code, not anything GPL. I am not convinced that this is the best idea, I just wanted to throw it out there. - Robert On Sep 23, 2007, at 11:34 AM, William Stein wrote: On 9/23/07, Mike Hansen [EMAIL PROTECTED] wrote: It seems odd that closed source software could use GMP under the LGPLv3, but that a GPLv2 project could not. How tightly integrated is the GMP stuff? Aren't we pretty much just using it as a library? We are just using it as a library. The problem isn't LGPLv3, but GPLv2 itself! But please see http://gplv3.fsf.org/dd3-faq where it is made crystal clear that in fact a GPLv2 project can't even use an LGPLv3 library in library-only mode. There is a discussion here: http://lwn.net/Articles/241065/ In short, Magma and Maple can use GMP under LGPLv3, but Sage can't, because Sage is GPLv2, and the GPLv2 specifically disallows linking against libraries that are more restrictive (except things like the C library). -- William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: gmp 4.2.2 LGPL V3 issues and other minor tidbits
GMP 4.2.2 is LGPLv3, not GPLv3, so I think it would still work (though as I did mention, this is still an issue if we use anything with the (non-library) GPL). My proposal was that SAGE would be our GPL derivative but without this annoyance. My understanding is that GPLv2 can link to libraries that are less restrictive (for instance BSD/MIT/LGPLv2) as long as they are GPL- compatible, but LGPLv3 is more restrictive which is why that doesn't work. BTW, I totally agree with your rant. - Robert On Sep 25, 2007, at 12:18 PM, [EMAIL PROTECTED] wrote: This is not an option. From GPL2: 2. ... b) You must cause any work that you distribute or publish, that in whole or in part contains or is derived from the Program or any part thereof, to be licensed as a whole at no charge to all third parties under the terms of this License. From GPL3: These requirements apply to the modified work as a whole. If identifiable sections of that work, added by you, are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works for use not in combination with the Program. But when you distribute the same sections for use in combination with covered works, no matter in what form such combination occurs, the whole of the combination must be licensed under this License, whose permissions for other licensees extend to the entire whole, and thus to every part of the whole. Your sections may carry other terms as part of this combination in limited ways, described in section 7. Hence, if Sage cannot function without GPL3 software, it *must* be licensed under GPL3, and no other license. Therefore, GPL2 or later truly means GPL3 the instant that we include gmp4.2.2, no matter what we might tell ourselves. Similarly, if there is a library which is GPL2 only, we cannot include it once we've included gmp4.2.2. This is utterly ridiculous, but apparently a fact of life. rantWith all of RMS's talk about subjugation, and Microsoft forcing people into using their software, he seems pretty happy to force people into using the new license, and cause others to turn around and pressure their friends to do the same -- does this remind anybody else of the early days of communism in China? Oh, wait. No. I almost forgot: people aren't getting *killed* for doing or not doing these things -- what's subjugation mean again?/rant Anyway. Sorry for that. I found this link useful: http://www.groklaw.net/articlebasic.php?story=20060118155841115 and I got the above quotes from row #5. On Tue, 25 Sep 2007, Robert Bradshaw wrote: At this point it looks like the only reasonable option is to (begrudgingly) move to GPLv2 or above but there is another option that I haven't seen come up in discussion yet, and that is releasing SAGE under an amended GPLv2 that explicitly allows linking against LGPLv3+ libraries (or some other compatibility clause). This would free us from being at the mercy of whatever the FSF decides is a good idea 10 years from now, or even what they decided this last year. In doing this, however, we would loose what to me is the biggest advantage of the GPL over all the other copyleft Open Source licenses out there, namely that one merely has to say this code is GPL and everyone has an idea (of varying accuracy) what you're talking about. Also, it would only cover LGPL code, not anything GPL. I am not convinced that this is the best idea, I just wanted to throw it out there. - Robert On Sep 23, 2007, at 11:34 AM, William Stein wrote: On 9/23/07, Mike Hansen [EMAIL PROTECTED] wrote: It seems odd that closed source software could use GMP under the LGPLv3, but that a GPLv2 project could not. How tightly integrated is the GMP stuff? Aren't we pretty much just using it as a library? We are just using it as a library. The problem isn't LGPLv3, but GPLv2 itself! But please see http://gplv3.fsf.org/dd3-faq where it is made crystal clear that in fact a GPLv2 project can't even use an LGPLv3 library in library-only mode. There is a discussion here: http://lwn.net/Articles/241065/ In short, Magma and Maple can use GMP under LGPLv3, but Sage can't, because Sage is GPLv2, and the GPLv2 specifically disallows linking against libraries that are more restrictive (except things like the C library). -- William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: gmp 4.2.2 LGPL V3 issues and other minor tidbits
On 9/25/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: This is not an option. From GPL2: 2. ... b) You must cause any work that you distribute or publish, that in whole or in part contains or is derived from the Program or any part thereof, to be licensed as a whole at no charge to all third parties under the terms of this License. From GPL3: These requirements apply to the modified work as a whole. If identifiable sections of that work, added by you, are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works for use not in combination with the Program. But when you distribute the same sections for use in combination with covered works, no matter in what form such combination occurs, the whole of the combination must be licensed under this License, whose permissions for other licensees extend to the entire whole, and thus to every part of the whole. Your sections may carry other terms as part of this combination in limited ways, described in section 7. Hence, if Sage cannot function without GPL3 software, it *must* be licensed under GPL3, and no other license. Therefore, GPL2 or later truly means GPL3 the instant that we include gmp4.2.2, no matter what we might tell ourselves. The Sage program overall is GPL3. The Sage library (new python/cython code) itself is still GPLv2 or later, since it could be (in fact is) used with GMP-4.2.1 and GSL-1.9. Similarly, if there is a library which is GPL2 only, we cannot include it once we've included gmp4.2.2. This is utterly ridiculous, but apparently a fact of life. It is true that we cannot include any GPLv2 only libraries if we include GMP-4.2.2. Singular is a library with that property, so no matter what happens we won't be including GMP-4.2.2 (or GSL-1.10) until Singular is relicensed. If for some reason the Singular people do decide not to relicense, then we would be in quite a pickle (and would probably be forced to fork GMP). Anyway. Sorry for that. I found this link useful: http://www.groklaw.net/articlebasic.php?story=20060118155841115 and I got the above quotes from row #5. Excellent, many thanks for posting that, but I hope nobody else looks at it, since unfortunately it seems to be seriously out of date. It's from January 2006 and the GPLv3 changed a lot since then. william --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: gmp 4.2.2 LGPL V3 issues and other minor tidbits
On Sep 25, 12:18 pm, [EMAIL PROTECTED] wrote: Hence, if Sage cannot function without GPL3 software, it *must* be licensed under GPL3, and no other license. Therefore, GPL2 or later truly means GPL3 the instant that we include gmp4.2.2, no matter what we might tell ourselves. Similarly, if there is a library which is GPL2 only, we cannot include it once we've included gmp4.2.2. This is utterly ridiculous, but apparently a fact of life. What you're missing here is that gmp4.2.2 is not GPL3 licensed; it is LGPL3 licensed. I don't know of any SAGE component that is planning to switch to being GPL3(-only) licensed. Carl Witty --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: gmp 4.2.2 LGPL V3 issues and other minor tidbits
[EMAIL PROTECTED] wrote: Anyway. Sorry for that. I found this link useful: http://www.groklaw.net/articlebasic.php?story=20060118155841115 and I got the above quotes from row #5. FYI, this is a diff to an old draft of GPLv3! Mark the date. Read the real thing: http://www.gnu.org/licenses/lgpl-3.0.html Jaap --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: GPL version 2 or later permission request
On 9/25/07, Robert Miller [EMAIL PROTECTED] wrote: I have just skimmed through the sage-devel discussion about this, and I am even more confused than when I started. 1) I don't like releasing code to which a license that does not yet exist could be applied. Can't we get away with GPL V2 or (at your option) GPLv3? Technically we could get away with that. However, it is merely delaying the problem and replacing it by one that is potentially for worse. Imagine that I had instead started Sage 10 years ago when I was in grad school (I almost did start it then actually). Imagine that I had licensed everything GPLv2 only. Now, it is ten years later, and lets say over 500 people have contributed and all their code is copyright GPL v2 only. I now have to either fork GMP and GSL, etc., or get permission from those 500 people to relicense all the code GPLv3. Given how the FSF operates, it's a virtual certainty that in 10 years they will release a GPLv4 that is incompatible with GPLv3. If Sage is GPLv2 or V3 only, and there are 500 copyright owners, I will be in a terrible situation. 2) The only other issue I have is: if someone uses my code, are they required to give me credit and include the source? I'm pretty sure this is the case, but #1 makes me uncomfortable... I think that's a general GPL question.The way you phrased it is way to vague: if someone uses my code, are they required to give me credit and include the source? What does use my code mean? If Joe Spook at NSA uses your code to crack enemy encryption, do you feel they should give you credit and include the source? GPL definitely wouldn't mean they had to. -Robert M On 9/25/07, William Stein [EMAIL PROTECTED] wrote: Hello, Do I have your explicit written permission to relicense code you submit or submitted to Sage under GPL version 2 to be relicensed under the 'GPL either version 2 of the License, or (at your option) any later version' license? [ ] Yes [ ] No Note: If you answer no, unfortunately your code may have to be removed from Sage, causing much work for me. Please blame the FSF not me for causing this BS licensing nuisance. -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org -- Robert L. Miller http://www.robertlmiller.com/ -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: gmp 4.2.2 LGPL V3 issues and other minor tidbits
On 9/25/07, cwitty [EMAIL PROTECTED] wrote: What you're missing here is that gmp4.2.2 is not GPL3 licensed; it is LGPL3 licensed. I don't know of any SAGE component that is planning to switch to being GPL3(-only) licensed. GSL (http://www.gnu.org/software/gsl/), which is an extremely important component of Sage, has made a new release and it is GPL3-only licensed. William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] polynomial factorization over ZZ
Hi Bill, Did you ever benchmark polynomial factorization over ZZ, which is a key step in modular forms computations (that's why I care). I once did a few random tests 2 years ago and made the following remark (see below), namely that for small degree magma is faster than pari is faster than ntl and that for very large degree (1500) ntl is vastly faster than magma is vastly faster than pari. # PERFORMANCE NOTE: # In many tests with SMALL degree PARI is substantially # better than NTL. (And magma is better yet.) And the # timing difference has nothing to do with moving Python # data to NTL and back. # For large degree ( 1500) in the one test I tried, NTL was # *much* better than MAGMA, and far better than PARI. So probably # NTL's implementation is asymptotically better. I could use # PARI for smaller degree over other rings besides Z, and use # NTL in general. -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: gmp 4.2.2 LGPL V3 issues and other minor tidbits
On Sep 25, 12:31 pm, Robert Bradshaw [EMAIL PROTECTED] wrote: GMP 4.2.2 is LGPLv3, not GPLv3, so I think it would still work (though as I did mention, this is still an issue if we use anything with the (non-library) GPL). My proposal was that SAGE would be our GPL derivative but without this annoyance. My understanding is that GPLv2 can link to libraries that are less restrictive (for instance BSD/MIT/LGPLv2) as long as they are GPL- compatible, but LGPLv3 is more restrictive which is why that doesn't work. BTW, I totally agree with your rant. No; that's not how it works. LGPL3 is much less restrictive than GPL2; LGPL3 can link to anything, including proprietary software. It's GPL2 that's restrictive here; like you say, GPL2 software can link to anything GPL2-compatible. The problem is that LGPL3 is not GPL2-compatible. Let me go through an example to explain why LGPL3 is not GPL2- compatible. Imagine a hypothetical Ovit-brand scientific calculator. The Ovit calculator is far more powerful than any previous scientific calculator; in fact, it can do anything SAGE can do...because it includes SAGE. The Ovit comes with a CD containing the complete source code to SAGE, which makes the Ovit totally legal. The sad thing about the Ovit, though, is that there's no way to fix bugs. The Ovit software is cryptographically signed, and only Ovit themselves can produce new software that runs on this calculator. This goes totally against one of the original reasons for the free software movement, which is that users should be able to fix bugs in the software they use. Even so, Singular is released with a license (the GPL2) that says that Ovit is allowed to build their calculator using Singular and any derived work of Singular (which arguably includes SAGE). In other words, as long as SAGE is a derived work of Singular and Singular is licensed GPL2-only, William Stein is responsible for ensuring that every component of SAGE is suitable for Ovit to take and install on their non-user-modifiable calculator. Now, GMP 4.2.2 is released with a license (the LGPL3) that says (among many other things) that if Ovit wants to use GMP, they must make it possible for the user to replace GMP on their calculator (to fix bugs, or use higher-performance algorithms, or whatever). Since Ovit can't use GMP 4.2.2 (while retaining their non-user-modifiable business plan), neither can SAGE (while SAGE is a derived work of Singular and Singular is GPL2-only). Since one of the main purposes of the GPL3 and LGPL3 is to discourage Ovit-style devices (which would normally be called Tivo-style devices), by not providing code for people to use on them, and the GPL2 requires that any GPL2-compatible license allow use on Ovit-style devices, it's not surprising that they are incompatible. As far as getting people to pressure their friends into using the GPL3, it's hardly a new tactic. That's the whole point of a copyleft- style license. Please don't take this as implying that I approve of the GPL3 and LGPL3; I haven't decided yet one way or another. I dislike Tivo-style devices, and would dislike them much more if they included code that I had written and released under the GPL2. On the other hand, the GPL2 vs. GPL3 arguments, and forks, and rewritten code, and bad feelings, are pretty bad too. Maybe in a few years, with the benefit of hindsight, I'll decide whether I like the GPL3. (Even then, though, we still won't know what the world without GPL3 would have been like.) Carl Witty --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: GPL version 2 or later permission request
On 9/25/07, David Harvey [EMAIL PROTECTED] wrote: One thing is that your code will always still be licensed V2, so as long as GPL versions = 4 are *more* restrictive (which is likely to be the case, given that version 3 is more restrictive than version 2), you really don't loose anything. I.e., a person could in 10 years take the code you wrote out of sage and integrate it into a GPLv2-only project. Okay, so what if MS makes the FSF people an offer they can't refuse, buys them out, releases a new GPL v4 which says you can do anything you want with this code. I've agreed to be bound by any subsequent license version right? So now anyone can do anything with my code. I once thought the above scenario is possible, but now I don't after re-reading the GPL. The GPL license itself specifically says that Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. A license that so drastically changed from GPLv3 -- i.e., do anything you want with this code, would quite clearly not be similar in spirit to the GPLv3, and I suspect it wouldn't hold up in court on those grounds. -- William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: GPL version 2 or later permission request
On Sep 25, 2007, at 4:43 PM, William Stein wrote: Okay, so what if MS makes the FSF people an offer they can't refuse, buys them out, releases a new GPL v4 which says you can do anything you want with this code. I've agreed to be bound by any subsequent license version right? So now anyone can do anything with my code. I once thought the above scenario is possible, but now I don't after re-reading the GPL. The GPL license itself specifically says that Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. A license that so drastically changed from GPLv3 -- i.e., do anything you want with this code, would quite clearly not be similar in spirit to the GPLv3, and I suspect it wouldn't hold up in court on those grounds. Well, as long as is similar in spirit is interpreted by a court in the way we all would hope, then that's all good. I hope we can leave all this licensing stuff behind soon and get on with writing great code. david --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: polynomial factorization over ZZ
Oh, I just replied to this off list. To summarise my response: I'm not surprised at what you found. Victor Schoup is an expert on such matters, Magma has fast basic arithmetic and Pari is not asymptotically fast at anything, (though very good for many real world computations). I haven't personally timed these. Additional notes: with the FLINT profiling code written by David Harvey and added to by my student Tomasz Lechowski, it is easy to do timings of this. The question is, what is the generic case you are interested in, where there is a non-trivial factor, or where there is not? Bill. P.s: I can factor degree zero polynomials over ZZ fast. :-) On 25 Sep, 21:25, William Stein [EMAIL PROTECTED] wrote: Hi Bill, Did you ever benchmark polynomial factorization over ZZ, which is a key step in modular forms computations (that's why I care). I once did a few random tests 2 years ago and made the following remark (see below), namely that for small degree magma is faster than pari is faster than ntl and that for very large degree (1500) ntl is vastly faster than magma is vastly faster than pari. # PERFORMANCE NOTE: # In many tests with SMALL degree PARI is substantially # better than NTL. (And magma is better yet.) And the # timing difference has nothing to do with moving Python # data to NTL and back. # For large degree ( 1500) in the one test I tried, NTL was # *much* better than MAGMA, and far better than PARI. So probably # NTL's implementation is asymptotically better. I could use # PARI for smaller degree over other rings besides Z, and use # NTL in general. -- William Stein Associate Professor of Mathematics University of Washingtonhttp://wstein.org --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: polynomial factorization over ZZ
On 9/25/07, Bill Hart [EMAIL PROTECTED] wrote: Oh, I just replied to this off list. To summarise my response: I'm not surprised at what you found. Victor Schoup is an expert on such matters, Magma has fast basic arithmetic and Pari is not asymptotically fast at anything, ^ Interesting. This does some to be a general design philosophy with pari... (though very good for many real world computations). Indeed! I haven't personally timed these. Additional notes: with the FLINT profiling code written by David Harvey and added to by my student Tomasz Lechowski, it is easy to do timings of this. The question is, what is the generic case you are interested in, where there is a non-trivial factor, or where there is not? The case of interest to me personally is factoring Hecke polynomials, i.e., charpolys of Hecke operators, up to say degree about 2000. These will usually factor into about 2^n (+eps) big factors, where n is the number of prime divisors of the level, plus a bunch of small factors corresponding to old forms (lower level). The actual polynomials and their factors have fairly smallish coefficients because of the Deligne bound. This sage command outputs an example of the sort of polynomial I'm talking about: sage: X = SupersingularModule(next_prime(2000)) sage: T2 = X.T(2).matrix().dense_matrix() sage: time f = T2.charpoly() William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] gmp and mpfr
I'm the author of lcalc, the L-function Calculator, a package that is a component of Sage, and I'm trying to implement a multi-precision version to improve its capabilities. I'd like to use gmp, mpfr, and mpfrcpp but am having difficulty getting mpfr (and also mpfrcpp) to make check. I'm using a G5, and I 'sudo make install' everything so that the lib and include files end up in /usr/local/include and /usr/local/lib I tried following the README and INSTALL instructions, but have gotten various compiling errors at the make check stages of mpfr and of mpfrcpp... including path problems and problems with linking (Undefined symbols). I don't see why as I've set the configure options for mpfr: --with-gmp=/usr/local I'm wondering if anyone here has experience configuring, making, and installing gmp and then mpfr on a mac (mpfrcpp would also be nice) and, if so, can you tell me what options you used to configure, make, install, whether anything tricky was needed. --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] python configure file
I'm the author of lcalc, the L-function Calculator, a package that is a component of Sage, and I'd like to write a configure file for it to detect various system settings (example, what kind of operating system/machine, whether pari is installed, whether gmp is available, etc) and put that into a Makefile. I'm thinking of writing it in python. Does anyone have a sample configure file in python for doing similar things that they could kindly share. --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: python configure file
On 9/25/07, Michael [EMAIL PROTECTED] wrote: I'm the author of lcalc, the L-function Calculator, a package that is a component of Sage, and I'd like to write a configure file for it to detect various system settings (example, what kind of operating system/machine, whether pari is installed, whether gmp is available, etc) and put that into a Makefile. I'm thinking of writing it in python. Does anyone have a sample configure file in python for doing similar things that they could kindly share. I think this might be a job for Scons. Please check out http://www.scons.org/ and see if it is the sort of tool you want. Scons is included in Sage and is used in SAGE_ROOT/devel/sage/c_lib See the file SAGE_ROOT/devel/sage/c_lib/SConstruct Joel Mohler and Craig Citro wrote it. -- William -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: number fields
Carl and Robert, I presume that in the system you are proposing, an algebraic number would be specified as a specific root of a polynomial f with coefficients in Qbar. But f would be *represented* by a polynomial whose coefficients were complex intervals. The root alpha of f of interest would be specified by giving a complex interval containing the root alpha and no other roots of f. Is this correct? Assuming this is correct, here is my question (it always makes one look much smarter than one really is to ask a question instead of proposing an answer): if I specified two algebraic numbers alpha and beta in this way, with corresponding polynomials f and g, how would I construct the approximate polynomial of alpha + beta? Would I use the method of Dedekind, reducing the problem to writing down a determinant? Here is my second question (one looks doubly smart if one has two difficult questions and still no clue): is it true that one can easily tell if two algebraic numbers are *not* equal in this system, but to check if they are equal, one *always* has to drop back to algebraic techniques? Someone seemed to indicate that one could use root refinement to *prove* equality. Note I am not assuming anything about the construction of the polynomials of these algebraic numbers here, nor anything about how these algebraic numbers were constructed. I don't even think I can assume their polynomials have the same degree, since it is hard to give a minimum polynomial without exact coefficients being known. Even to check that two quantities are *not* equal, I may have to refine the approximation of the coefficients of their polynomials, yes? This turns it into a recursive problem; in order to refine a coefficient, I may have to refine its polynomial, etc, right down to QQ itself (assuming we were working in an extension of an extension of an extension ... of QQ). Well, my final question is, why not just define an algebraic number to be a specific root of a polynomial over QQ. One can easily then just use basic linear algebra to get a minimum polynomial over QQ of a+b, a- b, a*b, a/b and nthroot(a). If one never cares what field one is in, then this works just fine, no Galois groups required. Checking equality of algebraic numbers is also trivial. The only problem I see is if one writes QQ[a, b] where a and b have different degrees over Q (especially if those degrees are not coprime). How does interval arithmetic deal with this? I guess if one always demands polynomials over QQ (for which I cannot see any use for interval arithmetic) one can just work in QQ[x, y]/ (f(x), g(y)) where f(a) = 0 and g(b) = 0, etc. But this is precisely Allan Steel's solution! Bill. On 25 Sep, 20:04, John Cremona [EMAIL PROTECTED] wrote: Qbar means different things to different people (or to the same people at different times). Carl's view is to have Qbar fixed as a subfield of C so that an element of Qbar is represented as a (necessarily approximate) complex value together with its minimal polynomial. Number theorists and algebraists would like a more general viewpoint, to allow p-adics to enter the picture for example. If you have just one algebraic number a with minimal polynomial f(x) then the algebraist can be happy working with the abstract field K=Q[x]/(f(x)); this can be embedded into any larger field L (such as C) in which f has a root alpha just by mapping x to alpha; and if there are several roots then there will be that many different embeddings (into the same L). It gets more complicated if you now introduce a second algebraic number b with minimum polynomial g(x), defineing a second abstract field K'=Q[x]/(g(x)). How do add a to b, since they live in entirely different worlds? The algebraists approach is that this only makes sense if you have field L into which both K and K' embed and you do arithmetic in L. Taken to the limit (literally) one arrives at Qbar as the direct limit of all fields like K, which in abstract terms is obtained by taking the disjoint union of all the K=Q[x]/(f(x)) together with embeddings between these, and identifying two elements if they have the same image in a field containing both. Our discussion about how to make sense of symbolic expressions like sqrt(2)+sqrt(3)-sqrt(6) is relevant here. To make sense of this expression you need not only the individual fields Q(sqrt(a)) for a=2, 3, 6; you need a single field L containing sqrts of all three numbers, together with those embeddings, i.e. a labelling of *which* root of x^2-2 in this big field is the one which you want the abstract sqrt(2) to. One solution mentioned previously takes L=R (reals) and labels the positive roots. But, as we have seen that simple solution breaks down quickly for more complicated algebraic numbers. Excuse the ramblings: but I always find that computational ambiguities like this are best understood by treating the mathematics seriously! John On 9/25/07, cwitty
[sage-devel] Re: making new infix operators
Thanks, now I understand what to do. However, I don't understand your
comment about ...the SAGE coercion model. What is an example of
that - the sage integers?
-M. Hampton
On Sep 25, 12:10 pm, Mike Hansen [EMAIL PROTECTED] wrote:
Since I don't think that graphs and polytopes fall under the SAGE
coercion model, overloading operators is pretty straightforward. You
just need to define the __add__ method in your class. x + y will call
x.__add__(y).
sage: class Foo:
: def __add__(self, y):
: return 42
:
sage: a = Foo()
sage: b = Foo()
sage: a + b
42
sage: b + a
42
Note that you'll want to do some type-checking so that y is what you
actually think it should be.
--Mike
On 9/25/07, Hamptonio [EMAIL PROTECTED] wrote:
I would appreciate any tips on how to extend the + operator in this
way, since I would like to implement Minkowski sums of polytopes and
this is natural notation for that.
Marshall
On Sep 25, 10:37 am, Mike Hansen [EMAIL PROTECTED] wrote:
In SAGE, '+' is used for union of sets. For example,
sage: a = Set([1,2])
sage: b = Set([2,3])
sage: a+b
{1, 2, 3}
Since currently, + is not defined for graphs, it'd be a natural choice.
--Mike
On 9/25/07, Jason Grout [EMAIL PROTECTED] wrote:
I'm thinking more about how to make the Graph class easy to use. One
thing that crops up is that the operations that combine graphs only
combine two graphs at a time (e.g., g.union(h), where g and h are
graphs).
Is there a way to define an infix operator that would allow one to say:
g union h union i union j union k?
I could do it with something like:
reduce(lambda x,y: x.union(y), [g,h,i,j,k])
But that doesn't seem as clear as the infix things above.
For reference, Mathematica allows an operator in backticks to be applied
to its surrounding arguments, so the equivalent operation above would
be:
g `union` h `union` i `union` j `union` k
And of course, you can set whether the operator is left-associative or
right-associative.
Of course, one solution is to use a for loop:
newgraph=Graph()
for graph in [g,h,i,j,k]:
newgraph.union(graph)
But that seems a lot clunkier than the infix expression above.
I guess another solution is to return the new graph from the union, so
that you could do:
g.union(h).union(i).union(j)
Thoughts?
-Jason
--~--~-~--~~~---~--~~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~--~~~~--~~--~--~---
[sage-devel] Re: polynomial factorization over ZZ
NTL uses the Cantor-Zassenhaus method with van Hoeij's improvements. But so does Magma since about Jul 2001. But here's the kicker. Pari also uses this algorithm. Even Maple uses it! NTL's LLL algorithms are extremely well developed (van Hoeij uses LLL). There is also a possible speed difference in whether one uses quadratic convegence or not in the Hensel lift. But the right choice is not always what one thinks. But more than likely NTL is just better for large problems because Victor Schoup was very careful with the choice of strategies and parameters he used. Paul Zimmerman supplied him with a pile of polynomials to factor for comparison purposes and these seem to have been used to tune the algorithm for a wide range of inputs, including cases that van Hoeij's algorithm doesn't usually like. If you have a bound on the coefficients of the factors, one can surely do better than a generic implementation, but probably not much better if there are many factors. It will be interesting to code this eventually. But I'm sorry to say it is still a way off. You can see all the things we have to code before we get there, polynomials over Z/pZ including Berlekamp's algorithm, Hensel lifting, LLL, van Hoeij's algorithm, lots of tuning. Bill. On 25 Sep, 22:03, William Stein [EMAIL PROTECTED] wrote: On 9/25/07, Bill Hart [EMAIL PROTECTED] wrote: Oh, I just replied to this off list. To summarise my response: I'm not surprised at what you found. Victor Schoup is an expert on such matters, Magma has fast basic arithmetic and Pari is not asymptotically fast at anything, ^ Interesting. This does some to be a general design philosophy with pari... (though very good for many real world computations). Indeed! I haven't personally timed these. Additional notes: with the FLINT profiling code written by David Harvey and added to by my student Tomasz Lechowski, it is easy to do timings of this. The question is, what is the generic case you are interested in, where there is a non-trivial factor, or where there is not? The case of interest to me personally is factoring Hecke polynomials, i.e., charpolys of Hecke operators, up to say degree about 2000. These will usually factor into about 2^n (+eps) big factors, where n is the number of prime divisors of the level, plus a bunch of small factors corresponding to old forms (lower level). The actual polynomials and their factors have fairly smallish coefficients because of the Deligne bound. This sage command outputs an example of the sort of polynomial I'm talking about: sage: X = SupersingularModule(next_prime(2000)) sage: T2 = X.T(2).matrix().dense_matrix() sage: time f = T2.charpoly() William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: number fields
Carl, I needed to read your response above more carefully!! Now that I have the questions, I see you have already written the answers. :-) You can ignore my questions about dropping back to algebraic methods and the advantages of interval arithmetic. But I guess there are still my other questions. But maybe my question about QQ[a,b] is not relevant, since we are working in Qbar, so who cares about Q[a,b]. One only cares that one can construct numbers in terms of a and b. The only advantages of an algebraic system are that you can get an algebraic number field which is a finite extension of QQ in which everything is defined, and you can compute Galois closures and compositums. But none of these things are really specific to Qbar arithmetic. They are all just general algebraic number theory questions. I still have a question about how one computes an approximate polynomial for a + b for algebraic a and b, given approximate polynomials for a and b, using interval arithmetic. Bill. On 26 Sep, 00:37, Bill Hart [EMAIL PROTECTED] wrote: Carl and Robert, I presume that in the system you are proposing, an algebraic number would be specified as a specific root of a polynomial f with coefficients in Qbar. But f would be *represented* by a polynomial whose coefficients were complex intervals. The root alpha of f of interest would be specified by giving a complex interval containing the root alpha and no other roots of f. Is this correct? Assuming this is correct, here is my question (it always makes one look much smarter than one really is to ask a question instead of proposing an answer): if I specified two algebraic numbers alpha and beta in this way, with corresponding polynomials f and g, how would I construct the approximate polynomial of alpha + beta? Would I use the method of Dedekind, reducing the problem to writing down a determinant? Here is my second question (one looks doubly smart if one has two difficult questions and still no clue): is it true that one can easily tell if two algebraic numbers are *not* equal in this system, but to check if they are equal, one *always* has to drop back to algebraic techniques? Someone seemed to indicate that one could use root refinement to *prove* equality. Note I am not assuming anything about the construction of the polynomials of these algebraic numbers here, nor anything about how these algebraic numbers were constructed. I don't even think I can assume their polynomials have the same degree, since it is hard to give a minimum polynomial without exact coefficients being known. Even to check that two quantities are *not* equal, I may have to refine the approximation of the coefficients of their polynomials, yes? This turns it into a recursive problem; in order to refine a coefficient, I may have to refine its polynomial, etc, right down to QQ itself (assuming we were working in an extension of an extension of an extension ... of QQ). Well, my final question is, why not just define an algebraic number to be a specific root of a polynomial over QQ. One can easily then just use basic linear algebra to get a minimum polynomial over QQ of a+b, a- b, a*b, a/b and nthroot(a). If one never cares what field one is in, then this works just fine, no Galois groups required. Checking equality of algebraic numbers is also trivial. The only problem I see is if one writes QQ[a, b] where a and b have different degrees over Q (especially if those degrees are not coprime). How does interval arithmetic deal with this? I guess if one always demands polynomials over QQ (for which I cannot see any use for interval arithmetic) one can just work in QQ[x, y]/ (f(x), g(y)) where f(a) = 0 and g(b) = 0, etc. But this is precisely Allan Steel's solution! Bill. On 25 Sep, 20:04, John Cremona [EMAIL PROTECTED] wrote: Qbar means different things to different people (or to the same people at different times). Carl's view is to have Qbar fixed as a subfield of C so that an element of Qbar is represented as a (necessarily approximate) complex value together with its minimal polynomial. Number theorists and algebraists would like a more general viewpoint, to allow p-adics to enter the picture for example. If you have just one algebraic number a with minimal polynomial f(x) then the algebraist can be happy working with the abstract field K=Q[x]/(f(x)); this can be embedded into any larger field L (such as C) in which f has a root alpha just by mapping x to alpha; and if there are several roots then there will be that many different embeddings (into the same L). It gets more complicated if you now introduce a second algebraic number b with minimum polynomial g(x), defineing a second abstract field K'=Q[x]/(g(x)). How do add a to b, since they live in entirely different worlds? The algebraists approach is that this only makes sense if you have field L into which both K and K' embed and you do
[sage-devel] Re: singular gcd slow-down
2007/9/19, Joel B. Mohler [EMAIL PROTECTED]: On Wednesday 19 September 2007 16:22, William Stein wrote: I think those timings are way out of date, since Singular 3 seems to be *very* fast at mod p multivariate GCD computation, even though it sucks over QQ. Check out this paper: http://www.cecm.sfu.ca/CAG/papers/brown.ps It on exactly the problem of GCD over QQ (or equiv ZZ), and section 2 has a complete description of a gcd algorithm that reduces gcd over ZZ to doing gcd's mod p. I'll be looking into implementing that. It makes me disgruntled to be at the mercy of mathematica (or pick your favorite big commercial m). :D. FYI, I plan on implementing a multivariate gcd algorithm for Sage over RR and CC some time next year. The algorithm is by Kaltofen et al. Here's the abstract: Abstract. We consider the problem of computing minimal real or complex deformations to the coefficients in a list of relatively prime real or complex multivariate polynomials such that the deformed polynomials have a greatest common divisor (GCD) of at least a given degree k. In addition,we restrict the deformed coefficients by a given set of linear constraints, thus introducing the linearly constrained approximate GCD problem. We present an algorithm based on a version of the structured There is already an implementation of the algorithm written in maple available here if anyone is interested: http://www4.ncsu.edu/~kaltofen/software/manystln/ didier -- Joel --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
