search

linbox-team / linbox

LinBox - C++ library for exact, high-performance linear algebra
https://linbox-team.github.io/linbox
GNU Lesser General Public License v2.1
81 stars 28 forks source link

Characteristic polynomial of integer matrix has wrong degree #305

Open vneiger opened 11 months ago

vneiger commented 11 months ago

An issue in SageMath was raised here https://github.com/sagemath/sage/issues/35846 . When computing the characteristic polynomial of some 35 x 35 integer matrix, we get x^27, which does not have the correct degree. The same issue already appears within LinBox. Running the piece of code attached, with the current git version of LinBox, and with the matrix from the above Sage issue (attached as well in sms format), I get:

$ ./issue_charpoly
Characteristic Polynomial is X^27

whereas we expect a polynomial of degree 35. Trying with the same matrix on some Modular<double> coefficient domain (for this, comment/uncomment a couple of lines in the code), everything seems to be fine.

I wondered about some problem due to randomization and briefly tried to force a deterministic algorithm, but did not find quickly how to do this. May be related to https://github.com/linbox-team/linbox/issues/53 .

issue_sage_35846_charpoly.zip

gilvillard commented 10 months ago

I've raised https://github.com/linbox-team/fflas-ffpack/issues/381. I also get x^27 with ntl. I get a polynomial with nonzero coefficients between x^27 and x^35 without ntl. The behaviour seems to be wrong mod p already, hence both situations are affected (ok differently).

bdsaunders commented 10 months ago

Just fyi, when i use the blackbox method in linbox/algorithms/frobenius-small.h I get

usertime: 0.005487

x^13

x^9

x^7

x^5

x is that what it should be?

On Mon, Sep 4, 2023 at 12:20 PM Gilles Villard @.***> wrote:

I've raised linbox-team/fflas-ffpack#381 https://github.com/linbox-team/fflas-ffpack/issues/381. I also get x^27 with ntl. I get a polynomial with nonzero coefficients between x^27 and x^35 without ntl. The behaviour seems to be wrong mod p already, hence both situations are affected (ok differently).

— Reply to this email directly, view it on GitHub https://github.com/linbox-team/linbox/issues/305#issuecomment-1705507469, or unsubscribe https://github.com/notifications/unsubscribe-auth/AA4TUI74N3XSG32ZBGO66VDXYX5WPANCNFSM6AAAAAA2M3T22Q . You are receiving this because you are subscribed to this thread.Message ID: @.***>

gilvillard commented 10 months ago

Hi Dave, Yes, that's correct I think. Cheers