As advertised, an atempt at a minimal (non-)working example :
# Reproducible minimal example
with seed(0): M = matrix(AA, 3, 3, lambda u,v: AA.random_element())
# Working ring
WR = M.base_ring().algebraic_closure()
# A variable to carry the eigenvalues
l = SR.var("l")
# Vector of unknowns for the eigenvectors
V =vector(list(var("v", n=2))+[SR(1)])
# M.eigenvalues does not return. Get them by hand
# Equation determining the eigenspace
ESE = M-l*identity_matrix(WR, 3)
# Eigenvalues
EVa = ESE.det().roots(ring=WR)
# M.eigenvectors_left() doesn't return.
# Set up a system of equations whose roots define the eigenvectors.
Sys = ESE*V
# Solve for each eigenvalue
# solve([u.subs(l==EVa[0][0]) for u in Sys],list(V[:2])) fails.
# Try to solve manually by substitution
# First equation, first variable.
# solve(Sys[0].subs(l==EVa[0][0]), v0) fails.
# Try to solve by explicit algebraic manipulation
E00 = Sys[0].subs(l==EVa[0][0])
# Isolate v0
V00=E0/E00.coefficient(v0) # fast
At this point, tryoing to proint V00‘s value “never returns”. However, a
forst interruption (C-C) prints :
sage: V00
C-c
C-c---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py
in minpoly(self)
4492 try:
-> 4493 return self._minimal_polynomial
4494 except AttributeError:
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/structure/element.pyx
in sage.structure.element.Element.__getattr__
(build/cythonized/sage/structure/element.c:4754)()
493 """
--> 494 return self.getattr_from_category(name)
495
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/structure/element.pyx
in sage.structure.element.Element.getattr_from_category
(build/cythonized/sage/structure/element.c:4866)()
506 cls = P._abstract_element_class
--> 507 return getattr_from_other_class(self, cls, name)
508
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/cpython/getattr.pyx
in sage.cpython.getattr.getattr_from_other_class
(build/cythonized/sage/cpython/getattr.c:2633)()
360 dummy_error_message.name = name
--> 361 raise AttributeError(dummy_error_message)
362 attribute = <object>attr
AttributeError: 'AlgebraicNumber' object has no attribute '_minimal_polynomial'
During handling of the above exception, another exception occurred:
KeyboardInterrupt Traceback (most recent call last)
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/structure/element.pyx
in sage.structure.element.Element.__richcmp__
(build/cythonized/sage/structure/element.c:10418)()
1110 return (<Element>self)._richcmp_(other, op)
1111 else:
-> 1112 return coercion_model.richcmp(self, other, op)
1113
1114 cpdef _richcmp_(left, right, int op):
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/structure/coerce.pyx
in sage.structure.coerce.CoercionModel.richcmp
(build/cythonized/sage/structure/coerce.c:20625)()
1979 assert not (isinstance(x, Element) and
1980
(<Element>x)._parent.get_flag(Parent_richcmp_element_without_coercion))
-> 1981 return PyObject_RichCompare(x, y, op)
1982
1983 # Comparing with coercion didn't work, try something else.
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/structure/element.pyx
in sage.structure.element.Element.__richcmp__
(build/cythonized/sage/structure/element.c:10394)()
1108 # an instance of Element. The explicit casts below make
1109 # Cython generate optimized code for this call.
-> 1110 return (<Element>self)._richcmp_(other, op)
1111 else:
1112 return coercion_model.richcmp(self, other, op)
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/structure/element.pyx
in sage.structure.element.Element._richcmp_
(build/cythonized/sage/structure/element.c:10500)()
1112 return coercion_model.richcmp(self, other, op)
1113
-> 1114 cpdef _richcmp_(left, right, int op):
1115 r"""
1116 Basic default implementation of rich comparisons for elements
with
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py
in _richcmp_(self, other, op)
4897 ci1 = self._value.imag().abs()
4898 ci2 = other._value.imag().abs()
-> 4899 if ci1.overlaps(ci2) and self.minpoly() == other.minpoly():
4900 c = cmp_elements_with_same_minpoly(self, other,
self.minpoly())
4901 if c is not None:
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py
in minpoly(self)
4493 return self._minimal_polynomial
4494 except AttributeError:
-> 4495 self.exactify()
4496 self._minimal_polynomial = self._descr.minpoly()
4497 return self._minimal_polynomial
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py
in exactify(self)
4363 if isinstance(od, (ANRational, ANExtensionElement)):
4364 return
-> 4365 self._set_descr(self._descr.exactify())
4366
4367 def _set_descr(self, new_descr):
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py
in exactify(self)
8429 left = self._left
8430 right = self._right
-> 8431 left.exactify()
8432 right.exactify()
8433 gen = left._exact_field().union(right._exact_field())
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py
in exactify(self)
4363 if isinstance(od, (ANRational, ANExtensionElement)):
4364 return
-> 4365 self._set_descr(self._descr.exactify())
4366
4367 def _set_descr(self, new_descr):
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py
in exactify(self)
8429 left = self._left
8430 right = self._right
-> 8431 left.exactify()
8432 right.exactify()
8433 gen = left._exact_field().union(right._exact_field())
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py
in exactify(self)
4363 if isinstance(od, (ANRational, ANExtensionElement)):
4364 return
-> 4365 self._set_descr(self._descr.exactify())
4366
4367 def _set_descr(self, new_descr):
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py
in exactify(self)
8431 left.exactify()
8432 right.exactify()
-> 8433 gen = left._exact_field().union(right._exact_field())
8434 left_value = gen(left._exact_value())
8435 right_value = gen(right._exact_value())
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py
in union(self, other)
3230 op = QQx(op)
3231 # pari_nf = self._field.pari_nf()
-> 3232 pari_nf = self.pari_field()
3233 factors = list(pari_nf.nffactor(op).lift())[0]
3234 x, y = QQxy.gens()
/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py
in pari_field(self)
3134 if self._pari_field is None:
3135 pari_pol = self._field.pari_polynomial("y")
-> 3136 self._pari_field = pari_pol.nfinit(1)
3137 return self._pari_field
3138
cypari2/auto_gen.pxi in cypari2.gen.Gen_base.nfinit()
and a *second* interrupt prints :
KeyboardInterrupt:
Exception ignored in: 'sage.symbolic.expression.py_is_integer'
Traceback (most recent call last):
File "sage/structure/parent.pyx", line 1163, in
sage.structure.parent.Parent.__contains__
(build/cythonized/sage/structure/parent.c:10408)
File "sage/structure/parent.pyx", line 898, in
sage.structure.parent.Parent.__call__
(build/cythonized/sage/structure/parent.c:9388)
File "sage/structure/coerce_maps.pyx", line 287, in
sage.structure.coerce_maps.NamedConvertMap._call_
(build/cythonized/sage/structure/coerce_maps.c:6085)
File
"/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py",
line 5011, in _integer_
return AA(self)._integer_(ZZ)
File
"/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py",
line 5485, in _integer_
self.exactify()
File
"/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py",
line 4365, in exactify
self._set_descr(self._descr.exactify())
File
"/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py",
line 8182, in exactify
arg.exactify()
File
"/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py",
line 4365, in exactify
self._set_descr(self._descr.exactify())
File
"/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py",
line 8431, in exactify
left.exactify()
File
"/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py",
line 4365, in exactify
self._set_descr(self._descr.exactify())
File
"/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py",
line 8431, in exactify
left.exactify()
File
"/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py",
line 4365, in exactify
self._set_descr(self._descr.exactify())
File
"/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py",
line 8433, in exactify
gen = left._exact_field().union(right._exact_field())
File
"/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py",
line 3232, in union
pari_nf = self.pari_field()
File
"/usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py",
line 3136, in pari_field
self._pari_field = pari_pol.nfinit(1)
File "cypari2/auto_gen.pxi", line 23641, in cypari2.gen.Gen_base.nfinit
KeyboardInterrupt:
1.000000000000000?*v0 - 35.57125011095806?*v1 - 492.8896998473554?
Similarly, V00.coefficient(v0).is_one() “never returns”.
The current aritmetic on algebraics is therefore problematic for this kind
of problems.
Suggestions ?
Le lundi 31 janvier 2022 à 17:59:34 UTC+1, Emmanuel Charpentier a écrit :
> Thank you, Nils !
> Trying to pinpoint things by running a manual solution step by step, it
> seems that the stumbling oint is the division on two algebraics. I'll try
> to make a clear minimal example and report it.
> Le lundi 31 janvier 2022 à 00:49:22 UTC+1, Nils Bruin a écrit :
>
>> On Saturday, 29 January 2022 at 13:51:14 UTC-8 Emmanuel Charpentier wrote:
>>
>>> /usr/local/sage-9/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/rings/qqbar.py
>>>
>>> in pari_field(self)
>>>
>>>> 3134 if self._pari_field is None:
>>>> 3135 pari_pol = self._field.pari_polynomial("y")
>>>> -> 3136 self._pari_field = pari_pol.nfinit(1)
>>>> 3137 return self._pari_field
>>>> 3138
>>>>
>>>> cypari2/auto_gen.pxi in cypari2.gen.Gen_base.nfinit()
>>>> KeyboardInterrupt:
>>>>
>>>>
>>>> nf_init is a perfectly respectable place to hang. After interruption,
>> can you "%debug" and see what the value of pari_pol is? I'd expect that
>> nfinit determines the ring of integers, which means factoring the
>> discriminant. [QQbar shouldn't need the ring of integers of element
>> arithmetic, but this has been stumbled on before: QQbar often tries to find
>> an "optimized" form of the number field, which for small examples is often
>> quite doable and, if you end up doing a LOT of arithmetic in the same
>> field, is often worth the investment. However, because of factoring of the
>> discriminant, it's fully subexponential in complexity, whereas all the
>> things QQbar needs to do are polynomial time. So we already know that QQbar
>> will do things with the wrong theoretical asymptotic complexity. That can
>> come back and bite you, when reality and asymptotics start behaving
>> similarly (which happens eventually ... asymptotically speakinh)
>>
>
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/3201fd01-beb2-4afe-8057-d14c7e4c4bc9n%40googlegroups.com.
