[SciPy-user] Characteristic polynomial

Sun Dec 23 11:37:03 EST 2007

Hello again. I return with another question regarding characteristic
polynomials.

I am computing the characteristic polynomials for matrices. And while (for
millions of them) i get the right result, i found some cases, where i get
the "wrong".
Let me give you the examples, and then i will explain.

>>> A=matrix([[290, 324, 323, 364, 340, 341, 365, 336, 342, 326],
        [324, 290, 322, 338, 366, 341, 365, 336, 344, 324],
        [323, 322, 286, 337, 337, 366, 364, 361, 320, 323],
        [345, 327, 326, 315, 343, 344, 342, 363, 343, 312],
        [329, 347, 325, 343, 319, 345, 343, 364, 327, 327],
        [329, 329, 347, 344, 345, 323, 344, 342, 348, 328],
        [347, 347, 346, 342, 343, 344, 321, 341, 326, 311],
        [325, 325, 343, 363, 364, 342, 341, 313, 324, 309],
        [342, 344, 320, 362, 338, 366, 338, 335, 286, 307],
        [340, 339, 338, 330, 361, 362, 333, 329, 316, 265]])

>>> B=matrix([[290, 324, 336, 365, 341, 340, 364, 323, 342, 326],
        [324, 290, 336, 339, 367, 340, 364, 322, 344, 324],
        [325, 325, 313, 341, 342, 364, 363, 343, 324, 309],
        [346, 328, 341, 319, 346, 343, 342, 347, 345, 312],
        [330, 348, 342, 346, 321, 345, 344, 346, 329, 327],
        [328, 328, 364, 343, 345, 321, 341, 326, 346, 328],
        [346, 346, 363, 342, 344, 341, 317, 325, 324, 311],
        [323, 322, 361, 365, 365, 338, 336, 286, 320, 323],
        [342, 344, 335, 364, 340, 364, 336, 320, 286, 307],
        [340, 339, 329, 332, 363, 360, 331, 338, 316, 265]])

>>> poly(A)
array([  1.00000000e+00,  -3.00800000e+03,  -1.10612600e+06,
        -1.55679754e+08,  -1.10343405e+10,  -4.15092661e+11,
        -7.89507268e+12,  -6.51631023e+13,  -1.80794492e+14,
        -2.21111889e+00,  -2.95926167e-13])

>>> poly(B)
array([  1.00000000e+00,  -3.00800000e+03,  -1.10612600e+06,
        -1.55679754e+08,  -1.10343405e+10,  -4.15092661e+11,
        -7.89507268e+12,  -6.51631023e+13,  -1.80794492e+14,
         4.59224482e+00,   3.39308585e-14])

As you can see, the 2 polynomials are the same (up to the last 2 terms). The
last term is considered to be "almost" 0, so we can see that the difference
is the coefficient of x^1.

If we compute the exact same thing with Maple and Sage, we get (for both
matrices) :

*x^10 - 3008*x^9 - 1106126*x^8 - 155679754*x^7 - 11034340454*x^6 -
415092661064*x^5 - 7895072675601*x^4 - 65163102265268*x^3 -
180794492489124*x^2*

so, it is the same, since it doesn't "compute" the x^1 term.

This also happens for a few other matrices...

Can anybody help me with this? What is the right answer for the char. poly
(i guess it is the Sage's and Maple's one, since they agree).
Why does this difference occur? Is it "sage" to ignore the last 2 terms?

Thank you in advance.

Nikolas

On Dec 11, 2007 10:05 PM, Fernando Perez <fperez.net at gmail.com> wrote:

> On Dec 11, 2007 9:45 AM, Matthieu Brucher <matthieu.brucher at gmail.com>
> wrote:
> > You can't expect scipy to find the exact coefficients. sage is a
> symbolic
> > package, it will find the correct answers, but scipy will find only an
> > approximated one, up to the machine precision. This is what you see in
> your
> > exemple.
> > If you have integers, you could expect scipy to return long integers
> (exact
> > result), but this is not the case as almost everything is converted into
> a
> > float array before the actual C or Fortran routine is run.
>
> In this case Sage isn't using anything symbolic though: the issue is
> that Sage has from the ground up defined a type system where it knows
> what field its inputs are being computed over.  So if a matrix is made
> up of only integers, it knows that computations are to be performed in
> exact arithmetic over Z, and does so accordingly.
>
> Sage's origins are actually number theory, not symbolic computing, and
> its strongest area is precisely in exact arithmetic, with enormous
> sophistication for some of its algorithms.  Initially its (free)
> symbolic capabilities were all obtained via calls to Maxima, though
> now that Ondrej is actively helping with SymPy integration into Sage,
> that is changing and SymPy is natively available as well, which means
> that over time there will be more and more native (python) symbolic
> support as well.
>
> I'd agree though that for this kind of calculation, Sage is the tool to
> use.
>
> Cheers,
>
> f
> _______________________________________________
> SciPy-user mailing list
> SciPy-user at scipy.org
> http://projects.scipy.org/mailman/listinfo/scipy-user
>

-- 
Nikolas Karalis
Applied Mathematics and Physics Undergraduate
National Technical University of Athens, Greece
http://users.ntua.gr/ge04042
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20071223/f0e4d06c/attachment.html>