Re: vector version of gcdext?

On Thu, 4 Oct 2018 at 10:31, John Cremona <john.cremona@gmail.com> wrote:

On Wed, 3 Oct 2018 at 20:04, John Cremona <john.cremona@gmail.com> wrote:
Thanks for the replies. I was planning to use this with polynomials in one variable over a cyclotomic field. I'll use mathnf.

To answer Bill in a bit more detail. I have a square matrix M with square-free char poly, f(x), factored as f=f1*f2*...*fn, for simplicity take n=2 so f=f1*f2*f3. I need the extended gcd of h1=f2f3, h2=f1f3, h3=f1f2 and then writing 1=g1h1+g2h2+g3h3, substiituting M for x we get the identity as a sum of three orthgonal idempotent matrices, which we can then use to block-diagonalise M as a sirect sum of 3 blocks, each with char poly one of the fi.

mathnf is working fine.

.. but sometimes extremely slow. I have an example with 9 polynomials of degrees [13, 13, 13, 13, 12, 12, 12, 12, 12] over a quadratic field, modulus t^2+t+1, and mathnf of the initial 1x8 matrix is taking forever. Unless there are other ideas I'll change my code when there are so many items in the initial list. I think that an iterative method using the 2-item gcdext will be fast.

John

John

On Wed, 3 Oct 2018 at 17:36, Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:
* Bill Allombert [2018-10-03 18:31]:
> On Wed, Oct 03, 2018 at 04:47:40PM +0100, J E Cremona wrote:
> > The function gcd() allows 2 inputs as in gcd(2,3) or a vector of inputs as
> > in gcd([6,10,15]), but the extended version only allows the first form.
> > It would not be hard to write an extended vector version (and I can of
> > course write my own) -- feature request?
>
> Hello John,
>
> The issue is that there are several solutions and no obvious canonical
> ones in that case. What would your extended vector version do ?
>
> Sometime we want small solutions, in which case a LLL based solution is
> better

That's what mathnf(t_VEC) implements [ Havas-Majewski ] for integer entries.
For polynomials, the implementation is not efficient, but OK for small
matrices.

> , and often we want the dual of gcdext, that is:
> given p_1...p_n, find a_1...a_n such that
>
> \sum a_i\*\prod_{i \neq j} p_j = 1
>
> (that is a_i = delta_i,j [mod p_j])

Not too hard to get that one from the other ...

Q = vecprod(P);
mathnf(vector(#P, i, Q/P[i]))

Cheers,

K.B.
--
Karim Belabas, IMB (UMR 5251) Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France) http://pari.math.u-bordeaux.fr/ [PARI/GP]
`