Opened 3 years ago
Closed 3 years ago
#27473 closed defect (fixed)
Matrix inversion fails over a Laurent series ring
Reported by:  kedlaya  Owned by:  

Priority:  major  Milestone:  sage8.9 
Component:  padics  Keywords:  matrix inversion, Laurent series 
Cc:  roed  Merged in:  
Authors:  Kiran Kedlaya  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  5fd44ec (Commits, GitHub, GitLab)  Commit:  5fd44ec1d5a5cfd5b10a8c64e23da28accf9eb44 
Dependencies:  Stopgaps: 
Description
As of 8.7beta6, this works fine (note change from adjoint
to adjugate
as per #10501):
sage: R.<t> = LaurentSeriesRing(QQ) sage: M = t*identity_matrix(2) sage: M.adjugate() * ~M.det() [t^1 0] [ 0 t^1]
but this fails:
sage: ~M ## Shorthand for M.inverse(), which behaves the same way  TypeError Traceback (most recent call last) <ipythoninput536c551a35e6a8> in <module>() > 1 ~M /home/kedlaya/sage/local/lib/python3.6/sitepackages/sage/matrix/matrix0.pyx in sage.matrix.matrix0.Matrix.__invert__ (build/cythonized/sage/matrix/matrix0.c:36096)() 5380 5381 A = self.augment(self.parent().identity_matrix()) > 5382 A.echelonize() 5383 5384 # Now we want to make sure that B is of the form [IX], in /home/kedlaya/sage/local/lib/python3.6/sitepackages/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix.echelonize (build/cythonized/sage/matrix/matrix2.c:48296)() 6725 if self.base_ring().is_field(): 6726 if algorithm in ['classical', 'partial_pivoting', 'scaled_partial_pivoting']: > 6727 self._echelon_in_place(algorithm) 6728 elif algorithm == 'strassen': 6729 self._echelon_strassen(cutoff) /home/kedlaya/sage/local/lib/python3.6/sitepackages/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix._echelon_in_place (build/cythonized/sage/matrix/matrix2.c:50128)() 7004 scale_factor = 0 7005 for c in range(nc): > 7006 abs_val = A.get_unsafe(r, c).abs() 7007 if abs_val > scale_factor: 7008 scale_factor = abs_val /home/kedlaya/sage/local/lib/python3.6/sitepackages/sage/structure/element.pyx in sage.structure.element.RingElement.abs (build/cythonized/sage/structure/element.c:18824)() 2718 ArithmeticError: absolute valued not defined on integers modulo n. 2719 """ > 2720 return abs(self) 2721 2722 def is_prime(self): TypeError: bad operand type for abs(): 'sage.rings.laurent_series_ring_element.LaurentSeries'
This worked back in 8.2, so it must be a recent change that broke it.
Change History (27)
comment:1 Changed 3 years ago by
comment:2 Changed 3 years ago by
... which of course they can have, but it's probably better to program the partial pivoting using the valuation directly. The definition of abs
would be lambda self: (self.is_zero()) select 0 else 2**(self.valuation())
or something similar, and is a very inefficient way of representing the valuation. So we probably need a scaled_partial_pivoting_absvalue
and a scaled_partial_pivoting_valuation
.
comment:3 Changed 3 years ago by
 Milestone changed from sage8.7 to sage8.8
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)
comment:4 Changed 3 years ago by
 Milestone sage8.8 deleted
As the Sage8.8 release milestone is pending, we should delete the sage8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage8.9).
comment:5 Changed 3 years ago by
 Branch set to u/kedlaya/matrix_inversion_fails_over_a_laurent_series_ring
comment:6 Changed 3 years ago by
 Commit set to 603f04141e3929e207bbaf603e8d10063762f671
 Status changed from new to needs_review
I followed nbruin's suggestion and added an algorithm scaled_partial_pivoting_valuation
. This shouldn't cause any side effects, but one should be careful when messing with core linear algebra.
New commits:
603f041  Add algorithm scaled_partial_pivoting_valuation

comment:7 Changed 3 years ago by
 Status changed from needs_review to needs_work
I see some failing doctests, so let me pull this until I have a chance to check these out.
comment:8 Changed 3 years ago by
 Commit changed from 603f04141e3929e207bbaf603e8d10063762f671 to 3a381dbbe5c6b806ba72d7b29ad3f8fe57f4d68d
Branch pushed to git repo; I updated commit sha1. New commits:
3a381db  Make echelon use abs for discretely valued fields when possible

comment:9 Changed 3 years ago by
The first commit broke a bunch of doctests involving matrices over padic fields. In principle it should be possible to fix this, but it is far easier to simply shortcircuit the echelon code so that it uses abs
even for discretely valued field unless the field does not support it, in which case we switch to valuation. The latest commit implements this, but I want to rerun all doctests before changing status again.
comment:10 Changed 3 years ago by
 Keywords matrix inversion Laurent series added
 Status changed from needs_work to needs_review
I completed a run of doctests, so let's put this back up for review.
comment:11 Changed 3 years ago by
I would try "ring.one().abs" instead of "abs(ring.one())" and then catch AttributeError
.
Wrong doc here:
+  ``'scaled_partial_pivoting_valuation'``: Gauss elimination, using scaled + partial pivoting (if base ring has absolute value)
Otherwise, looks good.
comment:12 Changed 3 years ago by
 Commit changed from 3a381dbbe5c6b806ba72d7b29ad3f8fe57f4d68d to 22d9208e2f53300946e56c24d1391dcbe6a56291
Branch pushed to git repo; I updated commit sha1. New commits:
22d9208  Edits based on trac feedback

comment:13 Changed 3 years ago by
Latest commit makes the change regarding abs
. Regarding the doc, I fixed the line overrun; but was there also another issue?
comment:14 Changed 3 years ago by
You did not fix the correct doc lines. The one I talk about is a little bit below, and contains the word "absolute value", instead of the correct "valuation".
comment:15 Changed 3 years ago by
 Commit changed from 22d9208e2f53300946e56c24d1391dcbe6a56291 to ea7557191a8a0d32a4c385b93a2a91872ee06822
comment:16 Changed 3 years ago by
There is a failure in src/sage/matrix/matrix2.pyx : you need to catch TypeError
in the check for abs.
comment:17 Changed 3 years ago by
 Commit changed from ea7557191a8a0d32a4c385b93a2a91872ee06822 to e4ab5738cadb95d2fa9cb912fa420c74d6deecba
Branch pushed to git repo; I updated commit sha1. New commits:
e4ab573  Catch correct exception raised by abs

comment:18 Changed 3 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, let it be. Thanks
comment:19 Changed 3 years ago by
 Milestone set to sage8.9
comment:20 Changed 3 years ago by
 Branch changed from u/kedlaya/matrix_inversion_fails_over_a_laurent_series_ring to e4ab5738cadb95d2fa9cb912fa420c74d6deecba
 Resolution set to fixed
 Status changed from positive_review to closed
comment:21 Changed 3 years ago by
 Commit e4ab5738cadb95d2fa9cb912fa420c74d6deecba deleted
Still getting
File "src/sage/matrix/matrix2.pyx", line 8922, in sage.matrix.matrix2.Matrix.diagonal.inverse Failed example: ~M Exception raised: Traceback (most recent call last): File "/var/lib/buildbot/slave/sage3_git/build/local/lib/python3.7/sitepackages/sage/doctest/forker.py", line 681, in _run self.compile_and_execute(example, compiler, test.globs) File "/var/lib/buildbot/slave/sage3_git/build/local/lib/python3.7/sitepackages/sage/doctest/forker.py", line 1105, in compile_and_execute exec(compiled, globs) File "<doctest sage.matrix.matrix2.Matrix.diagonal.inverse[11]>", line 1, in <module> ~M File "sage/matrix/matrix0.pyx", line 5382, in sage.matrix.matrix0.Matrix.__invert__ (build/cythonized/sage/matrix/matrix0.c:36130) A.echelonize() File "sage/matrix/matrix2.pyx", line 6756, in sage.matrix.matrix2.Matrix.echelonize (build/cythonized/sage/matrix/matrix2.c:48757) self._echelon_in_place(algorithm) File "sage/matrix/matrix2.pyx", line 7076, in sage.matrix.matrix2.Matrix._echelon_in_place (build/cythonized/sage/matrix/matrix2.c:51166) if abs_val > max_abs_val: TypeError: '>' not supported between instances of 'int' and 'NoneType'
with e4ab5738ca
comment:22 Changed 3 years ago by
 Resolution fixed deleted
 Status changed from closed to new
comment:23 Changed 3 years ago by
 Branch changed from e4ab5738cadb95d2fa9cb912fa420c74d6deecba to u/kedlaya/e4ab5738cadb95d2fa9cb912fa420c74d6deecba
comment:24 Changed 3 years ago by
 Commit set to d97e89ec2f56bf98d8d50ac5e748d39228dea245
 Status changed from new to needs_review
That looks like a Py3 issue. Let's see if patchbot likes this better.
comment:25 Changed 3 years ago by
 Branch changed from u/kedlaya/e4ab5738cadb95d2fa9cb912fa420c74d6deecba to public/ticket/27473
 Commit changed from d97e89ec2f56bf98d8d50ac5e748d39228dea245 to 5fd44ec1d5a5cfd5b10a8c64e23da28accf9eb44
comment:26 Changed 3 years ago by
 Status changed from needs_review to positive_review
the py2 bot is green, and all tests pass on py3. I am setting this back to positive
comment:27 Changed 3 years ago by
 Branch changed from public/ticket/27473 to 5fd44ec1d5a5cfd5b10a8c64e23da28accf9eb44
 Resolution set to fixed
 Status changed from positive_review to closed
The error comes from:
It seems to be assumed that rings in
DiscreteValuationFields
have anabs
method.