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: sage-8.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:

Status badges

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)
<ipython-input-53-6c551a35e6a8> in <module>()
----> 1 ~M

/home/kedlaya/sage/local/lib/python3.6/site-packages/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 [I|X], in

/home/kedlaya/sage/local/lib/python3.6/site-packages/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/site-packages/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/site-packages/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 chapoton

The error comes from:

M.echelonize('scaled_partial_pivoting')

It seems to be assumed that rings in DiscreteValuationFields have an abs method.

comment:2 Changed 3 years ago by nbruin

... 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.

Last edited 3 years ago by nbruin (previous) (diff)

comment:3 Changed 3 years ago by embray

  • Milestone changed from sage-8.7 to sage-8.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 embray

  • Milestone sage-8.8 deleted

As the Sage-8.8 release milestone is pending, we should delete the sage-8.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 (sage-8.9).

comment:5 Changed 3 years ago by kedlaya

  • Branch set to u/kedlaya/matrix_inversion_fails_over_a_laurent_series_ring

comment:6 Changed 3 years ago by kedlaya

  • Authors set to Kiran Kedlaya
  • 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:

603f041Add algorithm scaled_partial_pivoting_valuation

comment:7 Changed 3 years ago by kedlaya

  • 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 git

  • Commit changed from 603f04141e3929e207bbaf603e8d10063762f671 to 3a381dbbe5c6b806ba72d7b29ad3f8fe57f4d68d

Branch pushed to git repo; I updated commit sha1. New commits:

3a381dbMake echelon use abs for discretely valued fields when possible

comment:9 Changed 3 years ago by kedlaya

The first commit broke a bunch of doctests involving matrices over p-adic fields. In principle it should be possible to fix this, but it is far easier to simply short-circuit 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 kedlaya

  • 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 chapoton

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 git

  • Commit changed from 3a381dbbe5c6b806ba72d7b29ad3f8fe57f4d68d to 22d9208e2f53300946e56c24d1391dcbe6a56291

Branch pushed to git repo; I updated commit sha1. New commits:

22d9208Edits based on trac feedback

comment:13 Changed 3 years ago by kedlaya

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 chapoton

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 git

  • Commit changed from 22d9208e2f53300946e56c24d1391dcbe6a56291 to ea7557191a8a0d32a4c385b93a2a91872ee06822

Branch pushed to git repo; I updated commit sha1. New commits:

11ce5cfCorrect line of docstring
ea75571Remove extra space

comment:16 Changed 3 years ago by chapoton

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 git

  • Commit changed from ea7557191a8a0d32a4c385b93a2a91872ee06822 to e4ab5738cadb95d2fa9cb912fa420c74d6deecba

Branch pushed to git repo; I updated commit sha1. New commits:

e4ab573Catch correct exception raised by abs

comment:18 Changed 3 years ago by chapoton

  • 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 chapoton

  • Milestone set to sage-8.9

comment:20 Changed 3 years ago by vbraun

  • 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 vbraun

  • 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/site-packages/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/site-packages/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 vbraun

  • Resolution fixed deleted
  • Status changed from closed to new

comment:23 Changed 3 years ago by kedlaya

  • Branch changed from e4ab5738cadb95d2fa9cb912fa420c74d6deecba to u/kedlaya/e4ab5738cadb95d2fa9cb912fa420c74d6deecba

comment:24 Changed 3 years ago by kedlaya

  • 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 chapoton

  • Branch changed from u/kedlaya/e4ab5738cadb95d2fa9cb912fa420c74d6deecba to public/ticket/27473
  • Commit changed from d97e89ec2f56bf98d8d50ac5e748d39228dea245 to 5fd44ec1d5a5cfd5b10a8c64e23da28accf9eb44

You did something strange with your branch. I pushed a clean (and squashed) one instead, with the same fix for py3.


New commits:

268d9dbAdd algorithm scaled_partial_pivoting_valuation
5fd44ecMake echelon use abs for discretely valued fields when possible

comment:26 Changed 3 years ago by chapoton

  • 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 vbraun

  • Branch changed from public/ticket/27473 to 5fd44ec1d5a5cfd5b10a8c64e23da28accf9eb44
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.