Solve triu

[fieker]

No description provided.

[codecov]

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 88.28%. Comparing base (7a473f4) to head (89c4f1c).

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #1920      +/-   ##
==========================================
+ Coverage   88.17%   88.28%   +0.11%     
==========================================
  Files         120      120              
  Lines       30303    30383      +80     
==========================================
+ Hits        26719    26823     +104     
+ Misses       3584     3560      -24     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

[thofma]

With this change we end up having both

function _solve_triu(U::MatElem{T}, b::MatElem{T}, unit::Bool = false) where {T <: FieldElement}

and

function _solve_triu(U::MatElem{T}, b::MatElem{T}; side::Symbol = :left) where {T <: RingElement}

which I find a bit confusing.

julia> @which AbstractAlgebra._solve_triu(QQ[1 2; 3 4], QQ[1 2; 3 4])
_solve_triu(U::MatElem{T}, b::MatElem{T}) where T<:FieldElement
     @ AbstractAlgebra ~/bla/AbstractAlgebra.jl/src/Matrix.jl:3454

julia> @which AbstractAlgebra._solve_triu(ZZ[1 2; 3 4], ZZ[1 2; 3 4])
_solve_triu(U::MatElem{T}, b::MatElem{T}; side) where T<:RingElement
     @ AbstractAlgebra ~/bla/AbstractAlgebra.jl/src/Matrix.jl:3505

Maybe we can discuss this quickly tomorrow after the meeting.

[fieker]

On Thu, Dec 05, 2024 at 09:28:49AM -0800, Tommy Hofmann wrote: With this change we end up having both ``` function _solve_triu(U::MatElem{T}, b::MatElem{T}, unit::Bool = false) where {T <: FieldElement} ``` and ``` function _solve_triu(U::MatElem{T}, b::MatElem{T}; side::Symbol = :left) where {T <: RingElement} ``` which I find a bit confusing.

Why? just because it is? Jokes apart, this is terrible. I guess we should - support solve_triu_left for fields - support the unit also for rings and hope? The unit is used when solving with inplace lu! decomposition. One of triangular matrices has only implied diagonal (=1)

…

``` julia> @which AbstractAlgebra._solve_triu(QQ[1 2; 3 4], QQ[1 2; 3 4]) _solve_triu(U::MatElem{T}, b::MatElem{T}) where T<:FieldElement @ AbstractAlgebra ~/bla/AbstractAlgebra.jl/src/Matrix.jl:3454 julia> @which AbstractAlgebra._solve_triu(ZZ[1 2; 3 4], ZZ[1 2; 3 4]) _solve_triu(U::MatElem{T}, b::MatElem{T}; side) where T<:RingElement @ AbstractAlgebra ~/bla/AbstractAlgebra.jl/src/Matrix.jl:3505 ``` Maybe we can discuss this quickly tomorrow after the meeting. -- Reply to this email directly or view it on GitHub: #1920 (comment) You are receiving this because you authored the thread. Message ID: ***@***.***>

[thofma]

I am afraid it get's more complicated than adding units to the new functions, since the existing _solve_triu and the new _solve_triu are incompatible when it comes to the "side":

julia> A = matrix(ZZ, 2, 2, [1, 2, 0, 3]);

julia> AbstractAlgebra._solve_triu(A, matrix(ZZ, 1, 2, [1, 2]))
[1   0]

julia> AbstractAlgebra._solve_triu(QQ.(A), matrix(QQ, 1, 2, [1, 0]))
ERROR: BoundsError: attempt to access 1×2 Matrix{Rational{BigInt}} at index [2, 1]
Stacktrace:
 [1] throw_boundserror(A::Matrix{Rational{BigInt}}, I::Tuple{Int64, Int64})

julia> AbstractAlgebra._solve_triu(QQ.(A), matrix(QQ, 2,  1, [1, 0]))
[1//1]
[0//1]

Can we come up with a new name for the new methods? Then we can consider _solve_triu some relict that we will never touch again. How about _solve_upper_triangular? Or __solve_triue for maximal confusion?

[fieker]

On Sat, Dec 07, 2024 at 02:10:02PM -0800, Tommy Hofmann wrote: I am afraid it get's more complicated than adding `units` to the new functions, since the existing `_solve_triu` and the new `_solve_triu` are incompatible when it comes to the "side":

solve_triu for fields exists only for side=:right, but does to it heritage as a flint function, the dimensions are not verified.

``` julia> A = matrix(ZZ, 2, 2, [1, 2, 0, 3]); julia> AbstractAlgebra._solve_triu(A, matrix(ZZ, 1, 2, [1, 2])) [1 0] julia> AbstractAlgebra._solve_triu(QQ.(A), matrix(QQ, 1, 2, [1, 0])) ERROR: BoundsError: attempt to access 1×2 Matrix{Rational{BigInt}} at index [2, 1] Stacktrace: [1] throw_boundserror(A::Matrix{Rational{BigInt}}, I::Tuple{Int64, Int64}) julia> AbstractAlgebra._solve_triu(QQ.(A), matrix(QQ, 2, 1, [1, 0])) [1//1] [0//1] ``` Can we come up with a new name for the new methods? Then we can consider `_solve_triu` some relict that we will never touch again. How about `_solve_upper_triangular`? Or `__solve_triue` for maximal confusion?

I am happy with new names - but also with a discussion why we need/ want the triu solvers - regardless of their name. - in Hecke new det, the triu_left is used over ZZ - when using the inplace lu! (e.g. computing inverses), the triu_right with units is used and, most likely, the tril as well more takers?

…

-- Reply to this email directly or view it on GitHub: #1920 (comment) You are receiving this because you authored the thread. Message ID: ***@***.***>

[fieker]

so, for current applications we need, apart from names,

• upper triangular left solver over ZZ for Det
• upper and lower triangular right solver over fields for LU (one with, one without units)

adding the unit support is trivial. The more intersting problem is if one checks, optionally, that the matrix is triangular. In my application it will be, in the LU solver it will not, so adding the assertion would trigger an error.
Currently, for ZZ there are Strassen versions for both right and left and, I think, for the tril! over fields.
Here as well: what do we want? Strassen makes a difference. Also, do we want inplace solvers?