Howell form

[joschmitt]

I copied over the generic Howell form from Hecke. This requires the operations 'ann', 'gcdex' and 'quo' as Storjohann calls them; I implemented these under the names annihilator, gcdex and _div for ResElem.jl. Better names are welcome. I also added some lines that normalize the pivot elements with the canonical_unit to make the Howell form unique; is that correct?

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 98.02632% with 3 lines in your changes missing coverage. Please review.

Project coverage is 87.39%. Comparing base (762eab1) to head (d39d3fc).

Files	Patch %	Lines
src/MatrixNormalForms.jl	98.57%	2 Missing :warning:
src/Residue.jl	91.66%	1 Missing :warning:

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #1735 +/- ## ========================================== + Coverage 87.33% 87.39% +0.06% ========================================== Files 117 117 Lines 29777 29929 +152 ========================================== + Hits 26006 26157 +151 - Misses 3771 3772 +1 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[fieker]

On Tue, Jun 25, 2024 at 05:42:44AM -0700, Johannes Schmitt wrote:

I copied over the generic Howell form from Hecke. This requires the operations 'ann', 'gcdex' and 'quo' as Storjohann calls them; I implemented these under the names annihilator, gcdex and _div for ResElem.jl. Better names are welcome. gcdex = xxgcd in Hecke? Giving the 2x2 matrix of cofactors? bad name - but then, Hecke's is also bad.... why _div? Is this an exact or an euc division? In which case, div should do? or divrem? I also added some lines that normalize the pivot elements with the canonical_unit to make the Howell form unique; is that correct? Yep

You can view, comment on, or merge this pull request online at:

https://github.com/Nemocas/AbstractAlgebra.jl/pull/1735

-- Commit Summary --

• Copy Howell form from Hecke
• Normalize the pivots to make it unique
• Tests

-- File Changes --

M src/MatrixNormalForms.jl (252)
M src/Residue.jl (23)
M src/exports.jl (2)
M test/MatrixNormalForms-test.jl (34)

-- Patch Links --

https://github.com/Nemocas/AbstractAlgebra.jl/pull/1735.patch https://github.com/Nemocas/AbstractAlgebra.jl/pull/1735.diff

-- Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/pull/1735 You are receiving this because you are subscribed to this thread.

Message ID: @.***>

[joschmitt]

gcdex = xxgcd in Hecke? Giving the 2x2 matrix of cofactors? bad name - but then, Hecke's is also bad.... why _div? Is this an exact or an euc division? In which case, div should do? or divrem?

Yes, gcdex is what is called xxgcd in Hecke and gives the 2x2 matrix.

_div does not do an exact division. And I'm not sure I would call it "euclidean" in general? In the PhD thesis, Storjohann defines it for a principal ideal ring $R$ as

$\mathrm{Quo}(a, b)$: return a $q\in R$ such $a − qb \in \mathcal{R}(R, b)$

where $\mathcal{R}(R, b)$ is a "prescribed complete set of residues with respect to $b$".

[fieker]

On Tue, Jun 25, 2024 at 06:14:43AM -0700, Johannes Schmitt wrote:

gcdex = xxgcd in Hecke? Giving the 2x2 matrix of cofactors? bad name - but then, Hecke's is also bad.... why _div? Is this an exact or an euc division? In which case, div should do? or divrem?

Yes, gcdex is what is called xxgcd in Hecke and gives the 2x2 matrix.

_div does not do an exact division. And I'm not sure I would call it "euclidean" in general? In the PhD thesis, Storjohann defines it for a principal ideal ring $R$ as

$\mathrm{Quo}(a, b)$: return a $q\in R$ such $a − qb \in \mathcal{R}(R, b)$

where $\mathcal{R}(R, b)$ is a "prescribed complete set of residues with respect to $b$".

Do we have any non-euc ring where this is used/ useful? Z/nZ is euc as is O_K/I. However, already in O_K/I I don't think we have a unique residue system -- Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/pull/1735#issuecomment-2188925902 You are receiving this because you commented.

Message ID: @.***>