antispam@math.uni.wroc.pl schrieb:   
   >   
   > clicliclic@freenet.de wrote:   
   > >   
   > > antispam@math.uni.wroc.pl schrieb:   
   > > >   
   > > > clicliclic@freenet.de wrote:   
   > > > >   
   > > > > Consequently, the numerical approach should be taken; this will now be   
   > > > > easy to implement in FriCAS as you have added LLL reduction in version   
   > > > > 1.3.3. A general algorithm is obtained if symbolic numbers (including   
   > > > > the integration variable) are replaced by multi-precision random   
   > > > > numbers.   
   > > > >   
   > > > > A triangular build-up of checks (starting with one pair and then   
   > > > > checking each new root against those already done) combined with the   
   > > > > removal of roots already found to be dependent will keep the number of   
   > > > > integer coefficients down. An ordering by degree is important here; our   
   > > > > initial pair [SQRT(2), SQRT(SQRT(2) + 1)] is not really independent,   
   > > > > since the first root is expressible in terms of the second, though not   
   > > > > vice versa:   
   > > > >   
   > > > > [PrecisionDigits := 30, NotationDigits := 30, Notation := Scientific]   
   > > > >   
   > > > > pslq(APPEND([SQRT(SQRT(2) + 1)], VECTOR(SQRT(2)^n, n, 0, 1)))   
   > > > >   
   > > > > [[- 4.9919403*10^8, - 3.432391509*10^9, 2.975523862*10^9],   
   > > > > 0.0613806316930851818115657368417,   
   > > > > 8.60189464433061998367873564557*10^8]   
   > > > >   
   > > > > pslq(APPEND([SQRT(2)], VECTOR(SQRT(SQRT(2) + 1)^n, n, 0, 3)))   
   > > > >   
   > > > > [[-1, -1, 0, 1, 0], 1.49327557032630840460698894130*10^(-29),   
   > > > > 1.21006737170355383082315636508]   
   > > > >   
   > > > > When roots already found to be dependent are removed, the remaining   
   > > > > checks reduce to pair checks:   
   > > > >   
   > > > > pslq(APPEND([SQRT(58*SQRT(2) + 82)], VECTOR(SQRT(SQRT(2) + 1)^n, n, 0,   
   > > > > 3)))   
   > > > >   
   > > > > [[1, 0, -1, 0, -3], 4.06232927766911843010005263680*10^(-29),   
   > > > > 1.50826829417552156902865739881]   
   > > > >   
   > > > > pslq(APPEND([SQRT(17*SQRT(2) + 23)], VECTOR(SQRT(SQRT(2) + 1)^n, n, 0,   
   > > > > 3)))   
   > > > >   
   > > > > [[1, 0, -2, 0, -1], 0, 1.73717211380057814091826419549]   
   > > > >   
   > > > > For the typical use case where many root combinations resulted from a   
   > > > > small number (two or three) of basic roots of moderate degree, the   
   > > > > triangular scheme will be fast - the above checks using 30 decimals   
   > > > > take a few ten milliseconds on a modern computer. However, the   
   > > > > precision needed depends on the number of digits contained in the   
   > > > > integer coefficients, which is not known beforehand. Can a bound be   
   > > > > derived from the coefficients of the polynomials defining the   
   > > > > algebraics?   
   > > >   
   > > > AFAICS what you describe is equvalent to Lenstra factorization   
   > > > method (and yes, there is known bound on precision).  It was   
   > > > the first factorization method with polynomial running time.   
   > > > Unfortunately, in practice it is significantly slower then   
   > > > other methods.  Let me stress that the problem in not a "typical"   
   > > > case: typical case has independent roots so there is nothing   
   > > > to do.  When there is small number of roots of small degree   
   > > > (as above) FriCAS factorization works well.  Various special   
   > > > cases can be handled efficiently, for example sqrt(2), sqrt(3),   
   > > > sqrt(5), sqrt(7), sqrt(11), sqrt(13), sqrt(17), sqrt(19),   
   > > > sqrt(23), sqrt(29), sqrt(31) are easily shown independent due   
   > > > to Kummer theory (or see theorem in R. Fateman thesis).  For   
   > > > this numerical approach needs matrices of dimension of order   
   > > > 1000 and probably thousends of digits.  The problem is when   
   > > > there are several roots so that dimension of field generated   
   > > > by roots is high -- one can easily get milions from   
   > > > relatively small examples while already 30-100 leads   
   > > > to noticable slowdown (when carefuly implemented best   
   > > > known methods should work to 1000 or maybe a bit more).   
   > > >   
   > >   
   > > The LLL algorithm was originally (Math. Ann. 1982) proposed as a method   
   > > of factoring polynomials with rational coefficients. But there may be   
   > > something on precision bounds in:   
   > >   
   > > R. Kannan, A.K. Lenstra, and L. Lov?sz, Polynomial factorization and   
   > > non-randomness of bits of algebraic and some transcendental numbers,   
   > > Math. Comp. 50 (1988) 235?250.   
   > >   
   > > Even in the "typical case" of independent roots, that independence   
   > > would have to be to confirmed computationally for integration to   
   > > proceed. In order to see if a numerical approach can also deal with   
   > > those "innocent-looking" examples where the computation based on the   
   > > factorization algorithms currently implemented in FriCAS "takes hours"   
   > > you should provide one of them for other people to try. That set of   
   > > roots should not be entirely unlikely to appear in an integrand, of   
   > > course.   
   >   
   > Well, what appears in integrand depends on users.  Concerning   
   > likeness or unlikeness: Rubi testsuite contains several examples   
   > of multiparameter integrals in attempt to test "generic" answer.   
   > In similar spirit a user may try plugging in several algebraics   
   > instead of symbolic parameters into integral.  Does it make   
   > sense: probably no.  Will some user try this: yes, we just need   
   > enough users.   
   >   
   > My point about "innocent-looking" is that dimension of splitting   
   > field depends exponentialy on degree of polynomial.  So it does   
   > not take large input data to get high degree of splitting field.   
   > For example 5 indpendent roots of degree 5 lead to splitting   
   > field of dimension 3125.  And in this case computing splittng   
   > field is essentially equvalent to proving that roots are indepenent.   
   >   
   > Now, there are several potentially costly things during   
   > factorization.  One thing is that currently FriCAS uses   
   > Rotshild-Trager method, that is replaces polynomial of   
   > degree d with coefficient in field of dimension n by   
   > polynomial with rational coefficients of degree nd.  This   
   > replacement may cause signifcant growth of coefficients   
   > and also increases cost of factor recombination (see below).   
   > In FriCAS factorization starts from factorization over finite   
   > field.  When total degree is 1000 FriCAS needs of order of   
   > minutes to do it.  For degree 10000 one can expect hours.   
   > Next stage is Hensel lift, that is passing from factorization   
   > modulo p to factorization modulo p^k.  In many cases this   
   > is most expensive step (and this step is far from optimal   
   > in FriCAS).  Next step is factor recombination: one   
   > factor over integers may split into several factors   
   > modulo p^k.  FriCAS uses old method which is exponential   
   > in number of factors.  There is newer algorithm, starting   
   > from work of Mark van Hoej and improved by several subseqent   
   > papers.  This algorithm uses LLL to do factor recombination.   
   > Main point is that LLL here is used on much smaller   
   > problems compared to Lenstra: dimension is number of   
      
   [continued in next message]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)