Re: Problems with algdep()

["Karim Belabas" <Karim.Belabas@math.u-bordeaux1.fr>]

* Gonzalo Tornaria [2006-02-09 19:15]:
> In the first example, algdep(w1,4) returns a wrong answer; OTOH, running
> algdep(w1,8) returns a reducible polynomial (whose deg 4 factor is, in
> fact, the correct answer to the question).
> 
> The default precision (28) should be enough; changing it (say, to 57),
> fixes the algdep(w1,4) problem, but not the algdep(w1,8) problem.
> 
> In the second example, the answer is correct but reducible.
> 
> I understand why the answer would be reducible, since lindep() doesn't
> care about polynomials at all, and a reducible polynomial might be
> "smaller" (a different question is whether this is the sensible
> behaviour).
> 
> This does not, however, explain the last example, where algdep(w1,12)
> has the correct degree 4 factor, but its coefficients are
> much bigger.
[...]
> ? z1=2-sqrt(26);w1=(z1+I)/(z1-I)
> %1 = 0.8113905392500141676326132241 - 0.5845043993124185361124739615*I
> ? algdep(w1,4)
> %2 = 8058320*x^4 - 8782471*x^3 - 6696716*x^2 + 16929664*x - 7786219
> ? subst(%,x,w1)
> %3 = -40.92897558482005785799626475 - 30.76169632425638791179948667*I
> ? algdep(w1,8)
> %4 = 545*x^7 - 842*x^6 + 16*x^5 + 329*x^4 + 329*x^3 + 16*x^2 - 842*x +
> %545
> ? factor(%)
> %5 = 
> [x + 1 1]
> 
> [x^2 + x + 1 1]
> 
> [545*x^4 - 1932*x^3 + 2790*x^2 - 1932*x + 545 1]
> 
> ? subst(%[3,1],x,w1)
> %6 = 1.048697693 E-26 - 7.55454230 E-27*I
> 
> ---------------------------------------------------
> 
> ? s=3/8;r=2*cos(2*Pi*s);x=(r-sign(r))/2;y=sqrt(1-x^2);
> ? factor(algdep(x+I*y,20))
> %8 = 
> [x + 1 1]
> 
> [x^4 - 2*x^3 + x^2 - 2*x + 1 1]
> 
> ---------------------------------------------------
> 
> ? \p 200
> ? z1=2-sqrt(26);w1=(z1+I)/(z1-I);
> ? algdep(w1,12)
> %10 = 56353545*x^12 - 61469352*x^11 - 52043418*x^10 + 90409719*x^9 +
> 501729*x^8 - 20631014*x^7 - 45434470*x^6 + 144942235*x^5 - 203525140*x^4
> + 79566028*x^3 + 119795342*x^2 - 137115392*x + 46867820

During the current development cycle, PSLQ was made the default algorithm
in algdep and lindep about 4 years ago, because of a number of theoretical
advantages, which failed to materialize in our implementation (which is
both inefficient and unstable).

Since a lot of problems seem specific to this PSLQ implementation and
nobody could find an instance where that PSLQ would perform better than the
old LLL (which gradually improved over the years), I have reverted the
default algorithm to LLL in CVS [ the problems above disappear ]. An
example is documented in ??algdep.

Cheers,

    K.B.

P.S: In the next development cycle, I'll implement Phong & Stehle's L^2
algorithm, to improve the handling of knapsack lattices. This should be
as stable as the current LLL, and much faster. We'll see...
-- 
Karim Belabas                  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]