Can't invert an element of a matrix ring over an AcbField

[rburing]

Hi, I have some code that used to work that doesn't work anymore. Here is a minimal example:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.12.1 (2025-10-17)
 _/ |\__'_|_|_|\__'_|  |  Built by Homebrew (v1.12.1)
|__/                   |

julia> using Nemo

Welcome to Nemo version 0.52.3

Nemo comes with absolutely no warranty whatsoever

julia> CC = AcbField(53)
Complex Field with 53 bits of precision and error bounds

julia> A = identity_matrix(CC, 2)
[1.000000000000000                   0]
[                0   1.000000000000000]

julia> inv(A)
[1.000000000000000                   0]
[                0   1.000000000000000]

julia> R = matrix_ring(CC, 2)
Matrix ring of degree 2
  over complex Field with 53 bits of precision and error bounds

julia> B = R(A)
[1.000000000000000                   0]
[                0   1.000000000000000]

julia> inv(B)
ERROR: MethodError: no method matching _can_solve_internal_no_check(::AbstractAlgebra.Solve.LUTrait, ::AbstractAlgebra.Generic.MatSpaceElem{…}, ::AbstractAlgebra.Generic.MatSpaceElem{…}, ::Symbol; side::Symbol)
The function `_can_solve_internal_no_check` exists, but no method is defined for this combination of argument types.

Closest candidates are:
  _can_solve_internal_no_check(::AbstractAlgebra.Solve.LUTrait, ::AbstractAlgebra.Solve.SolveCtx{T, AbstractAlgebra.Solve.LUTrait}, ::MatElem{T}, ::Symbol; side) where T
   @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/L8iQ0/src/Solve.jl:1081
  _can_solve_internal_no_check(::AbstractAlgebra.Solve.HowellFormTrait, ::MatElem{T}, ::MatElem{T}, ::Symbol; side) where T
   @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/L8iQ0/src/Solve.jl:919
  _can_solve_internal_no_check(::AbstractAlgebra.Solve.RREFTrait, ::MatElem{T}, ::MatElem{T}, ::Symbol; side) where T
   @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/L8iQ0/src/Solve.jl:1014
  ...

Stacktrace:
 [1] _can_solve_internal(::AbstractAlgebra.Solve.LUTrait, A::AbstractAlgebra.Generic.MatSpaceElem{…}, b::AbstractAlgebra.Generic.MatSpaceElem{…}, task::Symbol; side::Symbol)
   @ AbstractAlgebra.Solve ~/.julia/packages/AbstractAlgebra/L8iQ0/src/Solve.jl:909
 [2] can_solve_with_solution(NF::AbstractAlgebra.Solve.LUTrait, A::AbstractAlgebra.Generic.MatSpaceElem{…}, b::AbstractAlgebra.Generic.MatSpaceElem{…}; side::Symbol)
   @ AbstractAlgebra.Solve ~/.julia/packages/AbstractAlgebra/L8iQ0/src/Solve.jl:649
 [3] can_solve_with_solution(A::AbstractAlgebra.Generic.MatSpaceElem{…}, b::AbstractAlgebra.Generic.MatSpaceElem{…}; side::Symbol)
   @ AbstractAlgebra.Solve ~/.julia/packages/AbstractAlgebra/L8iQ0/src/Solve.jl:645
 [4] can_solve_with_solution(A::AbstractAlgebra.Generic.MatSpaceElem{…}, b::AbstractAlgebra.Generic.MatSpaceElem{…})
   @ AbstractAlgebra.Solve ~/.julia/packages/AbstractAlgebra/L8iQ0/src/Solve.jl:644
 [5] can_solve_with_solution(M::AbstractAlgebra.Generic.MatRingElem{…}, B::AbstractAlgebra.Generic.MatRingElem{…})
   @ AbstractAlgebra.Generic ~/.julia/packages/AbstractAlgebra/L8iQ0/src/generic/MatRing.jl:63
 [6] inv(M::AbstractAlgebra.Generic.MatRingElem{AcbFieldElem})
   @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/L8iQ0/src/Matrix.jl:3718
 [7] top-level scope
   @ REPL[7]:1
Some type information was truncated. Use `show(err)` to see complete types.

[lgoettgens]

It looks like this was last touched (and thus maybe broken) by Nemocas/AbstractAlgebra.jl#2177 by @fieker.

cc @thofma @fingolfin @joschmitt

[thofma]

@joschmitt do you know what the easiest/best way to fix this is?

[joschmitt]

I'll try to have a look tomorrow. I have to remember / figure out what is implemented for those types.

[joschmitt]

I think this is what is going on:
B is a MatRingElem, the corresponding can_solve_with_solution https://github.com/Nemocas/AbstractAlgebra.jl/blob/6257b04e5d3778d0d41feae520e9e7a365d22c07/src/generic/MatRing.jl#L58 introduced in Nemocas/AbstractAlgebra.jl#2177 converts this to an Generic.MatSpaceElem and not (!) to an AcbMatrix.
Then the solving code is called with matrix_normal_form_type(CC) which is defined to be LUTrait() in Nemo because for AcbMatrix we have the corresponding solving functions. But for generic MatSpaceElem, we don't have a LU solver implemented. If I remember correctly, the argument was that solving just one system should be faster with rref and so we only have LU for the "solve context".

I see two solutions:

1. We implement the LU solver generically in AbstractAlgebra; should not be much work because generic lu is there.
2. We create the matrices with the correct type from the MatRingElem. That means that things get copied around a lot.

I would say that the question is basically whether we want the solving to be quick (in flint), but with memory overhead, or no overhead, but generic solving code. I do not know what these MatRingElems are used for, so I don't know what is preferred.

[lgoettgens]

If I understand you correctly, this should relate with the soon-ish change Nemocas/AbstractAlgebra.jl#1955 (John is working on it)

[rburing]

Thanks all for looking into this.

I do not know what these MatRingElems are used for, so I don't know what is preferred.

I used them for an implementation of Newton iteration for the series solution of a system of (homogeneous) first-order linear ODEs with rational function coefficients. The algorithm can be implemented either using matrices with polynomial entries, or polynomials with matrix coefficients. I implemented both, first in Julia as a prototype and then directly in FLINT with some optimizations (the version using matrices with polynomial entries later got merged into FLINT).

In the case of polynomials with matrix coefficients, I invert the (matrix) initial condition to start the series expansion of the inverse (and that's the only call to matrix inversion). This version is generally not fastest in the cases I tested, so it's not a big deal, but the error is still a regression.

[joschmitt]

If the internal structure of the MatRingElems is supposed to be improved anyway, I'll go with solution 2.