Karim Belabas on Fri, 14 Feb 2014 11:23:19 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: precision of result when adding t_REAL with lots of cancellation |
* John Cremona [2014-02-14 09:29]: > On 13 February 2014 22:15, Peter Bruin <P.Bruin@warwick.ac.uk> wrote: > > I am not familiar enough with descent on elliptic curves to say if there > > is any way to avoid such large number field elements (compared to the > > apperently modest input size), or if one can somehow keep track of these > > elements in a more compact factored form. Maybe Denis can enlighten us? > > > > Bonjour. The number field elements in question are representatives > of a class in K^* / (K^*)^2 for some number field K. I know that > there are some very good tricks to obtain good representatives, asn > have been assuming that Denis's code uses these, but it would be good > to have that confirmed. Otherwise, a reminder of the paper in which > these tricks are described? It may solve that instance, but we have a deeper problem. I believe we are dealing with good representatives, in a wrong model. Namely, we have b = \prod_i y_i^e_i in K = Q[x] / (T) where the y_i are fixed small S-units (for a small set S) and the e_i are (possibly) *huge* integers. Working with b in factored form is trivial, and libpari offers OK support for that; e.g in order to compute signs of real embeddings, only (e_i mod 2) matters, and we are back to the signs of the y_i [ which can be precomputed ]. Same holds for ideallogs, etc. ( One remaining problem in libpari is that the above in not quite true for public functions: we express everything first in terms of *fundamental units*, then S-units, which is a very bad ideal. An experimental branch supports writing everything in terms of S-units, which slows down simple examples, and speeds up immensely the complicated ones. ) Working with b as an expanded t_POLMOD in Q[x] / (T) or as a t_COL in terms of K.zk [ better: no denominators... ] is unfortunate since the above doesn't hold any longer: floating point embeddings become hard to compute, etc. Unfortunately, that's the documented way of working under GP. In principle, one should be happy to stick to elements in factored form defined implicitly via linear algebra in terms of small generators. But the documented output of all GP routines are t_COLs in terms of K.zk (which is often impossible to obtain in tough examples). I see no way of changing this in a backward compatible way. This requires adapting existing high level code as well. For instance, all routines whose input is a bnrinit(,,1), containing explicit expanded generators [ which are mathematically unnecessary, although they make implementations a little simpler ! ] Also it's not so nice for users to no longer be able to check rigorously whether two objects A = B (in different representations) are mathematically equal. Indeed, writing A or B in normal form (as a t_POLMOD or t_COL) is very hard, whereas testing whether A = B (mod whatever) is fine. Will be done, sometime. It's a lot of work ... (mostly adapting high level routines + testing + documentation, though: the basic C code is already here). Cheers, K.B. -- Karim Belabas, IMB (UMR 5251) 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-bordeaux1.fr/~kbelabas/ F-33405 Talence (France) http://pari.math.u-bordeaux1.fr/ [PARI/GP] `