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   
   factors modulo p^k, and coefficients are much smaller too.   
   I plan to implement this algorithm, but ATM irreducuble   
   polynomial with large number of factors modulo p^k will   
   trigger very bad behaviour.  And for factoring over   
   algebraic numbers first stage in FriCAS (Rotshild-Trager   
      
   [continued in next message]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)