[Georgi Guninski]

I think this is at least one bug on 10.5 on linux, attached is testcase

F=Graph(SNIP) #90 vertices
spe=F.spectrum()
a=spe[64]
print("(1):a=",a) #(1) -1.717980512878350? + 0.?e-60*I #XXX imaginary part
print("(2):a=",a,"poly=",a.minpoly()) #(2): -1.717980512878350? poly=
x^4 + 5*x^3 - 19*x - 16 #XXX imaginary part vanishes
"""
1. The spectrum must be real with no imaginary part
2. Why the imaginary part disappears after only print()
"""

[Nils Bruin]

It looks like a is an element of "Qbar". Elements there are tracked by keeping track of a way to compute a polynomial it is a root of as well as a complex "ball" that allows one to distinguish it from other roots of the polynomial. Certain operations will force the actual computation of the minimal polynomial. In the process one may discover information about the number. For instance, one may find it is actually rational or that it is real. Such info is then kept and may affect how the element prints. The representation that you get the first time is consistent with the imaginary part being 0. Computing the minimal polynomial then has the side effect of discovering that the imaginary part really is 0 rather than "not distinguished from 0" that you get the first time.

It looks like the system is working as specified.

[Dima Pasechnik]

On Mon, Apr 14, 2025 at 10:58 AM Nils Bruin <nbr...@sfu.ca> wrote:
>
> It looks like a is an element of "Qbar". Elements there are tracked by keeping track of a way to compute a polynomial it is a root of as well as a complex "ball" that allows one to distinguish it from other roots of the polynomial. Certain operations will force the actual computation of the minimal polynomial. In the process one may discover information about the number. For instance, one may find it is actually rational or that it is real. Such info is then kept and may affect how the element prints. The representation that you get the first time is consistent with the imaginary part being 0. Computing the minimal polynomial then has the side effect of discovering that the imaginary part really is 0 rather than "not distinguished from 0" that you get the first time.
>
> It looks like the system is working as specified.

One would wish there was a way to tell the system from the beginning
that this particular polynomial has only real roots.
Perhaps there is an easy way to implement is (a class of real-rooted
polynomials), no?

Dima

>
> On Monday, 14 April 2025 at 00:37:12 UTC-7 Georgi Guninski wrote:
>>
>> I think this is at least one bug on 10.5 on linux, attached is testcase
>>
>> F=Graph(SNIP) #90 vertices
>> spe=F.spectrum()
>> a=spe[64]
>> print("(1):a=",a) #(1) -1.717980512878350? + 0.?e-60*I #XXX imaginary part
>> print("(2):a=",a,"poly=",a.minpoly()) #(2): -1.717980512878350? poly=
>> x^4 + 5*x^3 - 19*x - 16 #XXX imaginary part vanishes
>> """
>> 1. The spectrum must be real with no imaginary part
>> 2. Why the imaginary part disappears after only print()
>> """
>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/sage-devel/16ea668c-b6df-45b2-87fd-d2d76a7d9c68n%40googlegroups.com.

[Nils Bruin]

On Monday, 14 April 2025 at 09:16:49 UTC-7 dim...@gmail.com wrote:

One would wish there was a way to tell the system from the beginning
that this particular polynomial has only real roots.
Perhaps there is an easy way to implement is (a class of real-rooted
polynomials), no?

Dima

Well, there is AA (algebraic reals) in addition to QQbar. If a number can be coerced into AA one would confirm that the imaginary part is really 0.

[Georgi Guninski]

I continue to think this is at least one bug.

There is an easy fix via change_ring():

sage: M=F.adjacency_matrix();f=M.characteristic_polynomial();f=f.change_ring(AA)
....: ;ro=f.roots();sum(e for _,e in ro)
90

[Nils Bruin]

I'm not sure what this fixes. Wouldn't M.characteristic_polynomial().degree() be a faster way of getting that answer? Or is your suggestion to force the spectrum into AA? The routine is documented as applying to both undirected and to digraphs and the latter can have nonreal spectral values. I expect changing it is only going to be cosmetic.

Even in printing the result is already unambiguous: given that the characteristic polynomial has rational coefficients, any nonreal root would have to have its imaginary part distinguished from 0 in order to separate it from its conjugate. So +0.?e-60*I must actually be really zero in this context. If you want to know for sure, ask the number; don't rely on an arbitrarily produced string representation.

[Georgi Guninski]

Just trying to show that real roots can be easily computed, not
relying on the bugs in roots over QQbar.
I don't see way to control the precision in the spectrum.
Who decides that small algebraic number is real, is it user's
responsibility, discarding visual non-zero?
e-60 is zero is e-58 zero or just small?
What if I need legitimate non-zero e-60?

[David Roe]

See the documentation on QQbar.  While I'm sure there are related bugs, I agree with Nils that in this case it's working as intended.  If you need a very small nonzero number, the system will compute with enough precision to determine that it is nonzero.

David

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD8cTddB82YnrHZ1N3mYG_Hjdijd2PFCAWF2Wm54%2BDtzLg%40mail.gmail.com.

[Nils Bruin]

On Tuesday, 15 April 2025 at 03:48:25 UTC-7 Georgi Guninski wrote:

Just trying to show that real roots can be easily computed, not
relying on the bugs in roots over QQbar.
I don't see way to control the precision in the spectrum.

The trick with QQbar: there IS no precision to control. The system is actually computing with exact algebraic numbers. It's using floating point approximations for efficiency, but it's making sure it's doing so with enough precision to separate conjugates (apart from bugs that are undoubtedly still there). If you want floating point approximations to the spectrum then ask for the roots of the characteristic polynomial in a floating point field (RealField or ComplexField).

Who decides that small algebraic number is real, is it user's
responsibility, discarding visual non-zero?

No you ask the system:

sage: R.<x>=QQ[]
sage: rts=f.roots(QQbar, multiplicities=False)
sage: a=rts[1]+rts[2]

sage: a
-1.000000000000000? + 0.?e-19*I
sage: a.imag() == 0
True
sage: a
-1

Checking equality in QQbar can be very expensive so the system avoids it when possible. Just bear in mind that the printing of an element of QQbar doesn't fully tell its identity. A floating point approximation never will. The question marks in the representation give a hint to that already.

Note that AA was bolted onto QQbar at a later stage. Root finding over AA is currently probably implemented by root finding over QQbar and then seeing which roots lie in AA. In principle it's possible to not do it that way but I doubt that you'd get much gain from it.

[Nils Bruin]

On Tuesday, 15 April 2025 at 08:45:53 UTC-7 Nils Bruin wrote:

Note that AA was bolted onto QQbar at a later stage. Root finding over AA is currently probably implemented by root finding over QQbar and then seeing which roots lie in AA. In principle it's possible to not do it that way but I doubt that you'd get much gain from it.

Actually the documentation of "roots" shows that AA and QQbar would be using different root separation algorithms:

```

   If L is "AA" or "RIF", and K is "ZZ", "QQ", or "AA", then the root
   isolation algorithm "sage.rings.polynomial.real_roots.real_roots()"
   is used.

   If L is "QQbar" or "CIF", and K is "ZZ", "QQ", "AA", "QQbar", or
   the Gaussian rationals, then the root isolation algorithm
   "sage.rings.polynomial.complex_roots.complex_roots()" is used.

```

Given that the expensive part of computing in QQbar/AA is rarely the interval arithmetic, I'm not so sure it will make a big difference which one is used.