Re: Fast test for integer-rooted polynomial

[Dirk Laurie <dirk.laurie@gmail.com>]

Op Wo. 10 Apr. 2019 om 20:04 het Bill Allombert
<Bill.Allombert@math.u-bordeaux.fr> geskryf:
>
> 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.

Perhaps Pari/GP is an overkill for this particular job.

-- Dirk