Matrix Inverse for Arbitrary Rings

[Michael Jung]

Dear developers,

I need to compute the inverses of matrices over commutative rings (namely scalar fields on manifolds). Unfortunately, the algorithms only process if the ring is a field or a corresponding fraction field is known. For now, I will pretend that the algebra of scalar fields is an algebraic field. However, for most cases, the algorithms work for arbitrary rings aswell when the matrix is invertible. I wonder why that hasn't been implemented yet. It would be nice if there was (for example) an additional attribute (something like "force=True") for the inverse function to pretend that the given ring is a field and at least try a computation.

Best regards,

Michael

[Vincent Delecroix]

Dear Michael,

At least, you need to know that the determinant is invertible...
See the related tickets

https://trac.sagemath.org/ticket/15160
https://trac.sagemath.org/ticket/27869

Note that the division free inversion of matrices is not a
completely trivial task. A simple way is to go via the matrix
of cofactors by computing determinant with division free
algorithms. This should be reasonable enough.

Best
Vincent

[Vincent Delecroix]

Or directly through the adjugate method

sage: R.<a,b,c,d> = ZZ[]
sage: RR = R.quotient(a*d-b*c-1)
sage: a,b,c,d = RR.gens()
sage: m = matrix(2, [a,b,c,d])
sage: n = m.adjugate() # we know that det=1 in this case
sage: m * n
[1 0]
[0 1]

[Michael Jung]

Thanks for you answer.

Ah well, I already tried to compute the adjugate of a corresponding
scalar field matrix, but it threw an error due to the is_field method.
So I thought it is not possible since the ring is no field (what I found
really strange, but god knows what algorithms are used). But I just
added a "proof=True" argument to scalar fields and now it's fine. I get
the feeling, interpreting error messages correctly is some kind of art. :D

Best regards,

Michael

Am 12.07.19 um 17:20 schrieb Vincent Delecroix:

[mic...@uni-potsdam.de]

However, I wonder why the adjugate method is not implemented by standard in case of the determinant being a unit. :-/

Regards,
Michael

Von meinem Huawei-Mobiltelefon gesendet

-------- Originalnachricht --------
Betreff: Re: [sage-devel] Matrix Inverse for Arbitrary Rings
Von: Michael Jung
An: sage-...@googlegroups.com
Cc:

Thanks for you answer.

Ah well, I already tried to compute the adjugate of a corresponding
scalar field matrix, but it threw an error due to the is_field method.
So I thought it is not possible since the ring is no field (what I found
really strange, but god knows what algorithms are used). But I just
added a "proof=True" argument to scalar fields and now it's fine. I get
the feeling, interpreting error messages correctly is some kind of art. :D

Best regards,

Michael

Am 12.07.19 um 17:20 schrieb Vincent Delecroix:
> Or directly through the adjugate method
>

> sage: R. = ZZ[]

--
You received this message because you are subscribed to a topic in the Google Groups "sage-devel" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-devel/4WVPLOHyMbc/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sage-devel+...@googlegroups.com.
To post to this group, send email to sage-...@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/01b4c7c8-f4a6-a816-35b3-4614300a6178%40uni-potsdam.de.
For more options, visit https://groups.google.com/d/optout.

[Vincent Delecroix]

Could you post the details of your example? adjugate is not supposed
to fail. And this should be fixed.

The problem is probably in matrix/matrix2.pyx:2355

f = self.lift().charpoly(var).change_ring(R)
----> elif R.is_field(proof = False) and R.is_exact():
f = self._charpoly_hessenberg(var)

The function is_field is indeed failing in many circumstances
(throwing a NotImplementedError) and we should not rely on
this.

Vincent

[Vincent Delecroix]

You could also use

m.adjuate(algorithm="df")

(df stands for division free).

Le 12/07/2019 à 18:44, mic...@uni-potsdam.de a écrit :
> However, I wonder why the adjugate method is not implemented by standard in case
> of the determinant being a unit. :-/
>
> Regards,
> Michael
>
> Von meinem Huawei-Mobiltelefon gesendet
>
>
> -------- Originalnachricht --------
> Betreff: Re: [sage-devel] Matrix Inverse for Arbitrary Rings
> Von: Michael Jung
> An: sage-...@googlegroups.com
> Cc:
>
>
> Thanks for you answer.
>
> Ah well, I already tried to compute the adjugate of a corresponding
> scalar field matrix, but it threw an error due to the is_field method.
> So I thought it is not possible since the ring is no field (what I found
> really strange, but god knows what algorithms are used). But I just
> added a "proof=True" argument to scalar fields and now it's fine. I get
> the feeling, interpreting error messages correctly is some kind of art. :D
>
> Best regards,
>
> Michael
>
> Am 12.07.19 um 17:20 schrieb Vincent Delecroix:
> > Or directly through the adjugate method
> >

> > sage: R.= ZZ[]

> 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
> <mailto:sage-devel+...@googlegroups.com>.

> To post to this group, send email to sage-...@googlegroups.com

> <mailto:sage-...@googlegroups.com>.

> Visit this group at https://groups.google.com/group/sage-devel.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sage-devel/dl7pqn-savxcy-c3kyrr-ld2v7z-oouf47-unxr5iijgtgt6znkqiunpzgc-gim7j-wss1rww1px0bee6l75-y2bm7n-6lcrnt-seeslnrvzqjq-249vzu-5z0fob-t3ken-edzk4u-oze8q7-ji71vv7rgxx2.1562949872823%40email.android.com
> <https://groups.google.com/d/msgid/sage-devel/dl7pqn-savxcy-c3kyrr-ld2v7z-oouf47-unxr5iijgtgt6znkqiunpzgc-gim7j-wss1rww1px0bee6l75-y2bm7n-6lcrnt-seeslnrvzqjq-249vzu-5z0fob-t3ken-edzk4u-oze8q7-ji71vv7rgxx2.1562949872823%40email.android.com?utm_medium=email&utm_source=footer>.

[Michael Jung]

Dear Vincent,

you're exactly right. Here is a minimal example:

sage: M = Manifold(2, 'M', structure='top')
sage: X.<x,y> = M.chart()
sage: matrix = MatrixSpace(X.function_ring(), 2)([x,0,0,y]); matrix

[x 0]
[0 y]
sage: sage: matrix.adjugate()

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-4d376cef30d0> in <module>()
----> 1 matrix.adjugate()

/home/michi/GitProjects/sage/local/lib/python2.7/site-packages/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix.adjugate (build/cythonized/sage/matrix/matrix2.c:66666)()
   8948             return X
   8949 
-> 8950         X = self._adjugate()
   8951         self.cache('adjugate', X)
   8952         return X

/home/michi/GitProjects/sage/local/lib/python2.7/site-packages/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix._adjugate (build/cythonized/sage/matrix/matrix2.c:66896)()
   9064         MS = self._parent
   9065 
-> 9066         f = self.charpoly()
   9067 
   9068         # A will be the adjugate of M and N is used to store powers of M

/home/michi/GitProjects/sage/local/lib/python2.7/site-packages/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix.charpoly (build/cythonized/sage/matrix/matrix2.c:20041)()
   2353             elif is_IntegerModRing(R):
   2354                 f = self.lift().charpoly(var).change_ring(R)
-> 2355             elif R.is_field(proof = False) and R.is_exact():
   2356                 f = self._charpoly_hessenberg(var)
   2357             else:

TypeError: is_integral_domain() got an unexpected keyword argument 'proof'

It seems like huge parts of the code rely on is_field(). It'd be desireable to make the code more flexible in this way and implement the adjugate method as standard inversion algorithm for more general rings.

Regards,

Michael

[Vincent Delecroix]

Le 13/07/2019 à 03:17, Michael Jung a écrit :
> It seems like huge parts of the code rely on is_field(). It'd be desireable
> to make the code more flexible in this way and implement the adjugate
> method as standard inversion algorithm for more general rings.

+1

This function is_field is not behaving well enough. In some part of
the code you can even see some workarounds like

try:
is_field = R.is_field()
except TypeError:
is_field = False

The argument "proof=False" was basically the reason for avoiding
the above workaround but it is not supported by any ring.

I tried a branch where instead of relying on is_field I test with

R in Fields()

where Fields is the category (in the SageMath sense) of fields
(see sage.categories.fields). The function is_field predates the
sage categories.

Though testing the matrix code becomes a bit slower. Even if the
above is replaced with

R in _Fields

where _Fields is already initialized.

Vincent

[Michael Jung]

It is supposed to work for inheritances of Ring (see sage.rings.ring):

def is_field(self, proof=True):
    if self.is_zero():
         return False
    if proof:
        raise NotImplementedError("No way to prove that %s is an integral domain!" % self)
    else:
        return False

But due to the categories, rings do not inherit from Ring (anymore?) but from Parent, right? So the is_field method is not a priori implemented.

You could try something like

try:
    is_field = R.is_field()
except TypeError:

    is_field = (R in Rings())

as a compromise? Would that make the code faster?

Anyway, the generalization to rings is another step that should be taken. But I don't dare to make any changes in the matrix files by myself.

Hope, I could help. :)

Regards,

Michael

[Simon King]

Hi Michael,

On 2019-07-13, Michael Jung <mic...@uni-potsdam.de> wrote:
> You could try something like
> try:
> is_field = R.is_field()
> except TypeError:
> is_field = (R in Rings())
> as a compromise? Would that make the code faster?

I think today the preferred way to test if something is a ring or
integral domain or field is via categories ("R in Fields()").

Best regards,
Simon

[Michael Jung]

Yes, I see. (And of course I meant "R in Fields()" and "except AttributeError".)

Does anybody open a ticket about this issue? I'd like to follow.

Off-Topic question: Is Sage capable of checking whether a multivariable (differentiable) function has a zero in a given domain?

Best,

Michael

[Vincent Delecroix]

https://trac.sagemath.org/ticket/28189

Le 13/07/2019 à 15:51, Michael Jung a écrit :
> Yes, I see. (And of course I meant "R in Fields()" and "except
> AttributeError".)
>
> Does anybody open a ticket about this issue? I'd like to follow.
>

> Off-Topic question: Is Sage capable of checking *whether *a multivariable

> (differentiable) function has a zero in a given domain?
>
> Best,
> Michael
>
> Am Samstag, 13. Juli 2019 14:23:31 UTC+2 schrieb Simon King:
>>
>> Hi Michael,
>>