Re: Fast test for integer-rooted polynomial

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Wed, Apr 10, 2019 at 05:03:40PM +0200, Dirk Laurie wrote:
> Op Wo. 10 Apr. 2019 om 03:10 het Gordon Royle <gordon.royle@uwa.edu.au> geskryf:
> 
> > This is a very simple task, but I want to do it billions of times, and so I want it to be as fast as possible.
> >
> > I have written a suitable Pari/GP routine to do it, but just naively, and I wonder if there is a clever way to do it.
> >
> >
> > INPUT: Billions of symmetric matrices of smallish order (say at most 16 x 16) each of which has small integer entries.
> >
> > OUTPUT: The input matrices that have only integer eigenvalues.
> >
> > From the nature of the problem, I know that any integer eigenvalues lie in {0,1,2, …, n} where n is the order of the matrix.
> >
> >
> > What I do currently:
> >
> > - get Pari to compute the characteristic polynomial (charpoly())
> > - factor the characteristic polynomial
> > - check that the factors are all linear
> 
> Why don't you just compute the eigenvalues numerically, round them to
> the nearest integer, and abort if the rounding discards too much?
> Depending on what "small" means, this process can be made quite
> foolproof.

This is not useful with mateigen, because mateigen do
polroots(charpoly(M)) in this case.

nfroots(,charpoly(M)) will be faster.

Cheers,
Bill.