Re: bnfisintnorm() is eager for memory

[Max Alekseyev <maxale@gmail.com>]

Karim, thank you! I'd appreciate any improvements to PARI in this respect. 

Ideally, I'd love to have an option for qbfsolve() to report all solutions below a given bound (asked about in the neighboring topic), which would save me from explicitly dealing with bnfinit / bnfisintnorm. But for now, it is what it is.

Regards,

Max

On Fri, Feb 23, 2024 at 9:14 AM Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:

Hi Max,

  it's easy from the representation I described: y = \prod {y_i}^{e_i}.

- Embed K into R using x -> ±sqrt(2305843005992468481), you get the two
real embeddings of y by embedding all y_i and performing floating
point computations; from this, you can compute y as a t_POLMOD with
floating point coefficients. This is stable since only multiplications are
involved (but exponents may overflow; one can compute  with logarithmic
embeddings to avoid the problem, this time taking into account cancellations
that occur when adding logs). You then know for sure whether that y has
"small enough" coefficients

- When a y is "small enough", you can round it (taking into
account a potential denominator 2). Or alternatively expand it mod p for
any given largish prime p (say larger than twice your bound): it's
guaranteed that the norm of y_i is supported on small primes; so for any
larger p there is no issue of (y_i mod p) not being invertible; then
centerlift the result multiplied by 2.

That gives an independent check of the floating point computation, but
it's not really relevant since one can always check whether
a (small!) result is correct.


The only problem is to get the bnfisintnorm function to output y in this
form: I can add an optional flag to bnfisintnorm to allow this. It's a 5
minutes job.

Cheers,

      K.B.

* Max Alekseyev [2024-02-23 13:59]:
> Hi Karim,
> Thank you for the analysis.
> What if I look for solutions where at least one of the coefficients is
> below 10^16 by absolute value? Is there a shortcut to get those or
> establish that there are none?
> Regards,
> Max
>
> On Fri, Feb 23, 2024 at 4:52 AM Karim Belabas <
> Karim.Belabas@math.u-bordeaux.fr> wrote:
>
> > * Max Alekseyev [2024-02-23 02:21]:
> > > In the following example, bnfisintnorm() runs out of memory even with a
> > > 32GB stack. Is there a way to overcome this?
> > >
> > > ? b = bnfinit('x^2-2305843005992468481,1)
> > > ? bnfisintnorm(b,2305843008139952128)
> >
> > Not really with the current specification for the function. One could
> > easily obtain the solutions as "algebraic numbers in factored form", but
> > have
> > a look at the simplest such solution 'y', attached to this mail:
> >
> > ? nfeltnorm(b, y)
> > %1 = 2305843008139952128
> >
> > y is given by a factorization matrix, corresponding to an _expression_
> > \prod_i {y_i}^{e_i}, where the y_i are small algebraic integers and the
> > e_i are (positive or negative) integers.
> >
> > Check the exponents y[,2]: its a vector with length 151 and sup-norm
> > 5345503542932135311077290.
> >
> > It's (relatively) easy to get all solutions in this form, with exponents
> > e_i of that magnitude. It's a completely explicit and well defined
> > _expression_, but no hope of expanding that as the expected t_POLMOD.
> >
> > A related difficulty: b.fu has a hard time finishing as well, about 2
> > minutes. The result has coefficients about exp(b.reg) ~ 10^6103581
> > and requires about 5 MB of storage (more than 5 times the size of the
> > original full bnf, which contains the same data in factored form and is
> > computed in 0.1 s).
> >
> > Cheers,
> >
> >     K.B.
> > --
> > Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
> > Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
> > http://www.math.u-bordeaux.fr/~kbelabas/
> >

    K.B.
--
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/