Oh of course, how could I forget. There's also functional decomposition. But I've not investigated the asymptotics. I'm sure Paul Zimmermann knows since he's been studying this in relation to factoring polynomials, I think. I expect the asymptotics to be bad in comparison with using power series methods though. But as it is only dependent on computing some gcd's it might be viable at some regime.
Bill. P.S: here -> hear in my last post. On 18 Aug, 16:44, Bill Hart <[EMAIL PROTECTED]> wrote: > Assuming FLINT is in fact being used for the GCD in Z[x], the > implementation is only "fast" up to degree about 250. It depends on > your definition of fast though. :-) In a later release of FLINT, GCD > will be asymptotically faster, and certainly by degree 1000 will be > many times faster than it currently is. > > Unfortunately I see no trivial way to add a fast square root to FLINT, > or I would knock it up. However I have added it to the list of > features, as I anticipate further need for it. So FLINT will implement > it in polys over Z and Z/pZ eventually. It's now trac ticket #71 for > FLINT. I'll make sure SAGE developers here about it when it is done. > > Almost everything over Q should probably be converted to a problem > over Z. I haven't seen any polynomial problems over Q which should not > be dealt with this way so far, but I suppose they may exist. > > If I'm not mistaken, the linear algebra method is nearly cubic > complexity. The GCD method should be subquadratic (though only just). > The method using power series has the same complexity as Karatsuba > multiplication of polynomials, in terms of ring operations (see papers > of Paul Zimmermann), and the constant can be made very low by use of > the recursive middle product algorithm. > > I guess it should be possible to use the FFT to get something like > asymptotical complexity n log n log log n. Certainly this can be > achieved if one exponentiates the logarithm. The question is what the > constant would be in that case. In terms of Karatsuba multiplication > the constant is less than 1, but for FFT it's likely to be 3/2, 5/2 or > 2 or something like that, but I don't have a handy reference for this. > Dan Bernstein's famous multapps paper does give the asymptotic > complexity though I think. > > Note that if one requires the square root of an exact square of > polynomials, if one uses the power series method, one only needs to > work to a precision about half the length of the original polynomial > since that is how large the square root will be. I think so anyway, > unless I'm missing something silly here (altogether likely). > > Bill. > > On 18 Aug, 15:00, "Joel B. Mohler" <[EMAIL PROTECTED]> wrote: > > > > > On Sunday 17 August 2008 01:05:53 pm John Cremona wrote: > > > > I have needed the following. g(x) is a univariate polynomial which I > > > know to be a square, and i want its square root. g.factor() does too > > > much, as does g.squarefree_decomposition(). I can get the sqrt via > > > g.gcd(g.derivative()), which works in my case since I know that the > > > sqrt is itself square-free. > > > > Is there a better way, and would there be a demand for adding an > > > implementation? > > > I've wanted a sqrt for polynomials as well (actually I wanted it for > > multivariate polynomials). Your request caught my imagination so I whipped > > one up. I suppose the most sensible algorithm is just to solve the system > > of > > equations that you get by equating corresponding coefficients -- there's an > > obvious order in which to solve these equations so you never actually have 2 > > unknowns. > > > Some observations: > > 1) Over ZZ[x] and ZZ(p)[x], computing > > gcd(f,f.derivative()) > > is really incredibly fast. You'd have to get very agressive with cython to > > make my implementation faster than the gcd (but, my implementation is much > > more reliable -- e.g. handles a squared squares correctly). Even up to > > degree 1000, the gcd is competitive, but I think there's got to be a > > cross-over somewhere. But, note that this obvious algorithm is quadratic in > > the degree and I don't know the run-time for the gcd. > > > 2) gcd of things in QQ[x] is very slow: > > sage: f=ZZ[x].random_element(50)^2 > > sage: %time _=gcd(f,f.derivative()) > > CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s > > Wall time: 0.00 s > > sage: f=QQ[x].random_element(50)^2 > > sage: %time _=gcd(f,f.derivative()) > > CPU times: user 18.41 s, sys: 0.07 s, total: 18.48 s > > Wall time: 18.49 s > > It should be much much faster to pull out a denominator and do the gcd over > > ZZ[x] and possibly do some book-keeping. Or, is there something I'm > > missing? > > > 3) The '//' operator is not implemented for > > GF(p)http://trac.sagemath.org/sage_trac/ticket/3890 > > > 4) The 'extend=False' parameter for CyclotomicField(4) is not > > implemented.http://trac.sagemath.org/sage_trac/ticket/3889 > > > My sqrt implementation is much faster than the gcd method over number fields > > and QQ. Fixing QQ gcd will change that considerably though. > > > Here's a trac ticket:http://trac.sagemath.org/sage_trac/ticket/3891 > > and preliminary implementation (actual patch will probably come > > tomorrow):http://kiwistrawberry.us/poly-sqrt-bench.py > > > -- > > 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://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
