TruncationStrategy types and constructors: consistency in names and implementations

[lkdvos]

This is a (breaking) change that attempts to make the truncation structs and their derived (lowercase) constructors a bit more uniform, while also removing some of them.

We previously had the following structs and constructors:

notrunc()::NoTruncation
truncrank(maxrank; by, rev)::TruncationKeepSorted
TruncationKeepBelow # direct constructor
TruncationKeepAbove # direct constructor
trunctol(val; by)::TruncationKeepFiltered
truncabove(val; by)::TruncationKeepFiltered
truncerror(err)::TruncationError

where both trunctol and truncabove would actually be equivalent to the TruncationKeepAbove and TruncationKeepBelow with an absolute tolerance, while not making use of the sorted implementations because they were implemented using filters.
Here, I merged TruncationKeepBelow and TruncationKeepAbove into TruncationByValue by adding an additional boolean flag to select between the two, while trying to be more consistent in the other names as well.

The updated scheme consists of:

notrunc()::NoTruncation
truncrank(maxrank; by, rev)::TruncationByOrder
truncfilter(f)::TruncationByFilter
trunctol(; atol, rtol, p, by, rev)::TruncationByValue
truncerror(; atol, rtol, p)::TruncationByError

Additionally, I exported all the lowercase constructors, and updated the docs accordingly.

PS: before actually tagging a 0.4 release, I would additionally like to change the formatter to runic (in a separate PR), to be consistent with the other packages in the organization.

[lkdvos]

@kshyatt , I think the GPU tests for svd_trunc are failing now and weren't before just because previously the implementation was never trying to make use of the sorted layout of the singular values (everything was dispatched to TruncationByFilter which simply calls findall). Do you happen to know what the best solution is here? I can try and specialize for GPU vectors to fall back to findall, or go to findfirst instead, since I'm assuming there is no binary search on GPU? Ideally we wouldn't have to specialize anything obviously, but I'm not sure if there is a way to write this that is natively GPU compatible.

[kshyatt]

If you're ok with pulling in another dependency, AcceleratedKernels.jl does have a searchsortedlast: https://github.com/JuliaGPU/AcceleratedKernels.jl?tab=readme-ov-file#4-functions-implemented

[lkdvos]

I'm not sure if that is really warranted here, for such a small use. I also am not sure how to make that work with the conditional loading with the GPU package extensions, since it also seems somewhat wrong to only load the CUDA code if AccelleratedKernels is loaded?

I guess findfirst is fine, I think the overall performance impact of a scan of a vector of length m should probably be dwarfed by the m x m SVD?

[kshyatt]

Yes a map + findfirst should work too.

…

On Sun, Sep 21, 2025 at 5:07 PM Lukas Devos ***@***.***> wrote: *lkdvos* left a comment (QuantumKitHub/MatrixAlgebraKit.jl#56) <#56 (comment)> I'm not sure if that is really warranted here, for such a small use. I also am not sure how to make that work with the conditional loading with the GPU package extensions, since it also seems somewhat wrong to only load the CUDA code if AccelleratedKernels is loaded? I guess findfirst is fine, I think the overall performance impact of a scan of a vector of length m should probably be dwarfed by the m x m SVD? — Reply to this email directly, view it on GitHub <#56 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAGKJY54P7WHWAX6UWRVWTT3T25JVAVCNFSM6AAAAACHCQ7RX6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTGMJWGA2TIMZRGM> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[codecov]

Codecov Report

❌ Patch coverage is 85.00000% with 9 lines in your changes missing coverage. Please review.

Files with missing lines	Patch %	Lines
src/implementations/truncation.jl	90.24%	4 Missing ⚠️
...ixAlgebraKitAMDGPUExt/MatrixAlgebraKitAMDGPUExt.jl	0.00%	2 Missing ⚠️
src/interface/truncation.jl	84.61%	2 Missing ⚠️
src/implementations/orthnull.jl	50.00%	1 Missing ⚠️

Files with missing lines	Coverage Δ
...MatrixAlgebraKitCUDAExt/MatrixAlgebraKitCUDAExt.jl	75.00% <100.00%> (+2.27%)	⬆️
src/MatrixAlgebraKit.jl	100.00% <ø> (ø)
src/algorithms.jl	92.80% <ø> (ø)
src/implementations/orthnull.jl	90.86% <50.00%> (ø)
...ixAlgebraKitAMDGPUExt/MatrixAlgebraKitAMDGPUExt.jl	71.42% <0.00%> (-7.52%)	⬇️
src/interface/truncation.jl	75.60% <84.61%> (+4.77%)	⬆️
src/implementations/truncation.jl	93.05% <90.24%> (-5.52%)	⬇️

🚀 New features to boost your workflow:

• ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[mtfishman]

@lkdvos I lost track, is the plan to replace all uses of findtruncated_sorted with findtruncated_svd?

[lkdvos]

Sorry, my bad, I wasn't fully finished incorporating the things we discussed, and apparently also accidentally committed some of the doodles I wrote during our discussion. I think I got most things figured out now

[Jutho]

Is it really worth returning a bool vector here, instead of just indices? Is findall(strategy.filter, values) so much worse? Or is that for GPU compatibility?

[Jutho]

Also, is the type annotation really useful? Is this a JET thing again?

[lkdvos]

I really don't have any opinion here. @mtfishman, what do you think? I am fine with either way.

[mtfishman]

I'm fine either way, I think the main considerations were:

1. It expresses the output better, since it encodes that the output indices don't repeat and don't have a specified ordering (i.e. they preserve the ordering).
2. We've found it helpful to use bool vectors for slicing block sparse arrays since they make it easier to preserve the block structure, but since some strategies output bool vectors and some don't, we have to convert them all anyway.

[Jutho]

After reading through the whole code, I think it would be nice if findtruncated has a well defined return type: either a list of indices, in which case a range in certain cases might be acceptable, or a Bool vector.

[Jutho]

Also, is the type annotation really useful? Is this a JET thing again?

[lkdvos]

Also, is the type annotation really useful? Is this a JET thing again?

This was mostly just a check since we don't have any input sanitation on the filter function, which might output Int, in which case you'd get very strange results.

Maybe the tests are more robust against future changes in the return type of findtruncated if they take the form

Great idea, I've implemented this now

Should we just always use BitVector as a return type for any findtruncated?

I'm not sure it is really necessary to restrict this. I think both options should work and have their merit, and if you implement a new truncation type it might be convenient to not have to be forced one way or the other. It's not that much extra complexity for now, and it is quite easy to go from one to the other so we can always post-process if needed?
I switched the filter implementation back to findall though.

[Jutho]

I would favour a consistent return type, at least functionally. I know that both boolean vector and list of indices can be used for indexing, but they do behave very different for other purposes. If I want to know the number of values kept, I would need to do sum for the boolean vector, and length for the list of indices, which is annoying if I don't know what to expect.

I am fine with either choice. I can see some benefits to the boolean vector return type, so if this is easier for @mtfishman that could be a good choice as well. The only consideration that comes to mind is that Julia find* methods return lists of indices, so there would be a bit of a mismatch.

Hence, I definitely support and approve of the current state of this PR.

[mtfishman]

Maybe a better way to support bool vectors would be to have findtruncated output a Base.LogicalIndex in those cases, which is what bool vectors get processed to by to_indices:

julia> to_indices(randn(3), ([true, false, true],))[1]
2-element Base.LogicalIndex{Int64, Vector{Bool}}:
 1
 3

EDIT: Or if we don't want to require that from findtruncated, we could insert calls to to_indices in certain places to canonicalize the index types, for example in the findtruncated definition of TruncationIntersection