Understanding the (partial) duplication of `AbstractAlgebra.hnf_kb!` in Hecke

[fingolfin]

In AA we have in src/Matrix.jl:5059:

function hnf_kb!(H, U, with_trafo::Bool = false, start_element::Int = 1)

Actually with https://github.com/Nemocas/AbstractAlgebra.jl/pull/2256 it will become

function hnf_kb!(H::MatrixElem{T}, U::MatrixElem{T}, with_trafo::Bool = false, start_element::Int = 1) where {T <: RingElement}

In Hecke, we have in src/LocalField/Matrix.jl:95:

function AbstractAlgebra.hnf_kb!(H::MatrixElem{T}, U::MatrixElem{T}, with_trafo::Bool = false, start_element::Int = 1) where T <: Hecke.LocalFieldValuationRingElem

Looking at the code, this is almost identical to the code in AA. The differences are:

1. a bunch irrelevant ones (commented out debug code, addition of AbstractAlgebra. prefixes, the restriction of T to LocalFieldValuationRingElem)
2. a switch from gcdx to the undocumented gcdxx
3. insertion of pivot_max = col1 of an if with_trafo block

I am mostly concerned about point 3. As I see it, most likely this is either a bug in the Hecke version of the code (e.g. accidental leftover from some debugging); or it is a fix for an issue, but then shouldn't it also be in AA?

The fact that 3 happens only inside an if with_trafo makes me consider the "it's a bug" version as more likely (it is also indented incorrectly, further supporting this).

Regarding point 2, using gcdxx seems indeed superior to the code in AA (which uses gcdx plus some divisions)? So it'd be nice to use it in AA as well. Then we could delete the copy of hnf_kb! in Hecke. But that would require adding a bunch of "missing" gcdxx methods (resp. adding one general "fallback" method which calls gcdx ? and then as many as we can that are optimized)

[fieker]

On Tue, Dec 16, 2025 at 06:03:45AM -0800, Max Horn wrote: fingolfin created an issue (thofma/Hecke.jl#2111) In AA we have in `src/Matrix.jl:5059`: ``` function hnf_kb!(H, U, with_trafo::Bool = false, start_element::Int = 1) ``` Actually with `Nemocas/AbstractAlgebra.jl#2256` it will become ``` function hnf_kb!(H::MatrixElem{T}, U::MatrixElem{T}, with_trafo::Bool = false, start_element::Int = 1) where {T <: RingElement} ``` In Hecke, we have in `src/LocalField/Matrix.jl:95`: ``` function AbstractAlgebra.hnf_kb!(H::MatrixElem{T}, U::MatrixElem{T}, with_trafo::Bool = false, start_element::Int = 1) where T <: Hecke.LocalFieldValuationRingElem ``` Looking at the code, this is almost identical to the code in AA. The differences are: 1. a bunch irrelevant ones (commented out debug code, addition of `AbstractAlgebra.` prefixes, the restriction of `T` to `LocalFieldValuationRingElem`) 2. a switch from `gcdx` to the undocumented `gcdxx` 3. insertion of `pivot_max = col1` of an `if with_trafo` block I am mostly concerned about point 3. As I see it, most likely this is either a bug in the Hecke version of the code (e.g. accidental leftover from some debugging); or it is a fix for an issue, but then shouldn't it also be in AA? The fact that 3 happens only inside an `if with_trafo` makes me consider the "it's a bug" version as more likely (it is also indented incorrectly, further supporting this). Regarding point 2, using `gcdxx` seems indeed superior to the code in AA (which uses `gcdx` plus some divisions)? So it'd be nice to use it in AA as well. Then we could delete the copy of `hnf_kb!` in Hecke. But that would require adding a bunch of "missing" `gcdxx` methods (resp. adding one general "fallback" method which calls `gcdx` ? and then as many as we can that are optimized)

The entire point of this function and the duplication is to be able to deal with inexact rings and their consequences gcdx vs gcdxx is an old one the reason your suggestion had not been done is due the need to write all the other gcdxx function, in essence change the euc interface. In the presence of zero divisors, however, gcdxx is neccessary... There are actually more differences dealing experimentally with the precision. One of the open problems is the specification of, e.g. gcdx the gcd, being a power of p, is unquely defined with infinite precision - as soon as the valuation of the input is known. The cofactors are never unique in gcdx - the normalisation is an artificial constraint. In the context here, the precision of the cofactors matters as it is impacting on the precision of the rest of the hnf matrix, it will be part of the unimodular transformation.. The differences are not directly in hnf_kb!, but in the tools: AbstractAlgebra.kb_reduce_column! AbstractAlgebra.kb_canonical_row! I copied this as a block in order to be able to experiment. Given that some/ most local rings are only in Hecke, some of this has to be done in Hecke...

…

-- Reply to this email directly or view it on GitHub: #2111 You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>