Karim Belabas on Mon, 08 Dec 2008 11:04:07 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Using {fa} in nfdisc() computations


* Kurt Foster [2008-12-08 04:24]:
> The optional {fa} parameter [factor() matrix]  seems like just the thing 
> for speeding up the computations in a situation I'm looking at.  I've got a 
> parametric family of polynomials.  I want the exact nfdisc()s for a whole 
> swarm of them.  I could, of course, just feed the polynomials to nfdisc() 
> and let it crunch away.  This does work, of course, but  it occurred to me 
> it might be faster if I could take advantage of the fact that the poldiscs 
> have a parametric algebraic factorization, and the algebraic factors are 
> generally much smaller than the poldisc(), in the sense that
>
> log(abs(algebraic factor))/log(abs(poldisc)
>
> will usually be a lot less than 1.  Thus, factoring the algebraic factors 
> should be a LOT quicker than tackling the whole poldisc.

The optional {fa} parameter is a little obsolete ( and its few uses in
libpari have been replaced by better alternatives over time ).

It should be a lot simpler to use addprimes(): something like

  \\ add these prime divisors to our trial division list
  F = addprimes( factor(AlgebraicFactor)[,1] );
  D = nfdisc(pol)
  removeprimes(F);

I see but one real use for the 'fa' argument: select a small list of
primes, usually a single one, and pass the matrix

[
  P[1],  valuation(disc, P[1]);
  ...
  P[k],  valuation(disc, P[k]);
  cofactor, 1
]

to obtain an order maximal at exactly those primes, without bothering
with the other ones. In practice, nfdisc(x, 1) yields the same or better
results with less trouble. (I have never needed the above technique for a
*large* prime.)

See also

  http://www.math.u-bordeaux.fr/~belabas/pari/doc/faq.html#nfpartialfact

Cheers,

    K.B.

P.S:
> But in order to produce the factor() matrix fa for the poldisc, I've got to 
> "combine" the factorization matrices of the algebraic factors.  There's 
> probably a slick way to do this, but I'm a dunce at programming.  Would 
> factor()ing the algebraic factors and "combining" the results actually be 
> likely to be faster than tackling the whole poldisc?  If so, what's an 
> expeditious way to combine the factor() matrices of the separate algebraic 
> factors into the correct factor() matrix for the poldisc?

There are functions in libpari to do exactly that, e.g. merge_factor(), but
they are not accessible to GP and require C programming.

--
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-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`