p-adic precision in vector multiplication

[chriswuthrich]

Trying to resolve #4656, I found the following unpleasant bug.

this looks good :

sage: R = Qp(5,5)
sage: x = R(5).add_bigoh(1)
sage: x
O(5)
sage: x*R(1)
O(5)

But when multiplied with the identity matrix the precision is lost

sage: I = matrix(R, [[1,0],[0,1]])
sage: v = vector([R(1),x])
sage: v
(1 + O(5^5), O(5))
sage: v*I
(1 + O(5^5), 0)
sage: v[0]*I[1,0] + v[1]*I[1,1]
O(5)

This causes things like

sage: M = matrix(R,[[1,2],[3,4]])
sage: M*v
(1 + O(5^5), 3 + O(5^5))
sage: v[0]*M[0,0] + v[1]*M[0,1]
1 + O(5)
sage: v[0]*M[1,0] + v[1]*M[1,1]
3 + O(5)

This is an even worse example, which could be a different bug

sage: vv = vector(x)
sage: vv
(0)
sage: vv[0]
0
sage: x
O(5)

CC: @nilesjohnson @jpflori

Component: linear algebra

Keywords: padics vector

Author: Peter Bruin

Branch/Commit: 41cbe4c

Reviewer: Chris Wuthrich

Issue created by migration from https://trac.sagemath.org/ticket/8198

[chriswuthrich]

comment:1

I must admit that I have not searched through the tracs to see if this is a duplicate. Sorry.

Resolving the bug would result in the resolution of #4656, too, I believe.

[nilesjohnson]

comment:2

I found this bug also, while working on #9457. After a fair bit of struggling with elliptic curve code, I now think this is a significant part of the problem.

I noticed the following also; I can't tell if it's the same bug or not.

sage: R = QQ.completion(5,5)
sage: P.<T> = R[]
sage: Q.<T> = R[[]]
sage: P(R(0).add_bigoh(-1))
(O(5^-1))
sage: Q(R(0).add_bigoh(-1))
0
sage: P(R(0).add_bigoh(2))
(O(5^2))
sage: Q(R(0).add_bigoh(2))
0
sage: Q(R(1).add_bigoh(2))
1 + O(5^2)
sage: Q(R(1).add_bigoh(-1))
0
sage: Q(R(1/25).add_bigoh(-1))
5^-2 + O(5^-1)

[nilesjohnson]

comment:3

Replying to @nilesjohnson:

I noticed the following also; I can't tell if it's the same bug or not.

oh, this seems to be the same as #4656

[chriswuthrich]

comment:4

I narrowed down the last issue above. (vector calls Sequence which calls list):

sage: R = Qp(5,5)
sage: x = R(5).add_bigoh(1)
sage: list(x)
[0]

again the element is set to zero. The problem here is different than the original case. In fact list(x) should raise an error, just like list(0) does.

sage: list([x,x]) 
[O(5), O(5)]

works correctly. So this is really about matrix multiplication.

[chriswuthrich]

comment:7

Note the very last bug, is not longer a problem in 6.1 as vv = vector(x)
raises the error
TypeError: this local element is not iterable
and that should be ok.

[chriswuthrich]

comment:8

I don't even understand where vector * matrix multiplication is implemented...

[pjbruin]

comment:10

Replying to @categorie:

I don't even understand where vector * matrix multiplication is implemented...

In sage/matrix/matrix0.pyx (I discovered this when working on #804). It tries to be too smart for its own good and skips entries of the vector that are equal to 0... I made a patch and am now testing it.

[pjbruin]

Author: Peter Bruin

[pjbruin]

Commit: 41cbe4c

[pjbruin]

Branch: u/pbruin/ticket/8198-matrix_vector_multiplication

[chriswuthrich]

Reviewer: Chris Wuthrich

[chriswuthrich]

comment:12

Good. All tests pass.

I was not certain about the changes as I am not completely fluent in cython. Having read documentations, I think they make sense. I tested the speed in a few very limited cases and it does not seem to me that the new code is slower or faster (except of course when the field is Qp).

Thanks for the help.

[pjbruin]

comment:13

Thanks; hopefully this goes some way towards being able to fix the related tickets #4656, #5075 and #9457...

[vbraun]

Changed branch from u/pbruin/ticket/8198-matrix_vector_multiplication to 41cbe4c