Appending a matrix to a vector of matrices

I have a long list (vector) of matrices. They are size 3xn where n is typically 1 < n < 7. My long list typically varies between 100K and 1 million. My task is to reduce this list using a rather complicated and expensive equivalence relation (reduction factor is about 100x to 1000x, depending on the case).

My current solution, to identifying the unique matrices, is basically an N^2 search but with as many early loop exits as I can invent. As I accumulate unique matrices, I’m storing them (via append) in an initially empty vector. @time tells me that 85% of my time is spent in garbage collection. Presumably it’s expensive to append because of frequent reallocations and copying.

Also, I couldn’t figure out how to initialize an empty vector of matrices {Matrix{Float64}} so my initial vector is of type Any. Maybe that is also trouble?

How would I initialize an empty vector of {Matrix{Float64}}? So that I can append! or push! matrices to it?

Here are some attempts:

julia> testList = Vector{Matrix{Float64}}
Vector{Matrix{Float64}} (alias for Array{Array{Float64, 2}, 1})

julia> testm
3×3 Matrix{Float64}:
 -0.5  0.0  0.0
  0.0  0.0  0.5
  0.5  0.0  0.5

julia> append!(testList,testm)
ERROR: MethodError: no method matching append!(::Type{Vector{Matrix{Float64}}}, ::Matrix{Float64})
Closest candidates are:
  append!(::DataStructures.MutableLinkedList, ::Any...) at ~/.julia/packages/DataStructures/59MD0/src/mutable_list.jl:160
  append!(::StructArrays.StructVector, ::Any) at ~/.julia/packages/StructArrays/wbEEd/src/tables.jl:27
  append!(::Plots.Series, ::Any...) at ~/.julia/packages/Plots/Ra8fG/src/utils.jl:790
  ...
Stacktrace:
 [1] top-level scope
   @ REPL[276]:1

julia> push!(testList,testm)
ERROR: MethodError: no method matching push!(::Type{Vector{Matrix{Float64}}}, ::Matrix{Float64})
Closest candidates are:
  push!(::Any, ::Any, ::Any) at /Applications/Julia-1.7.app/Contents/Resources/julia/share/julia/base/abstractarray.jl:2970
  push!(::Any, ::Any, ::Any, ::Any...) at /Applications/Julia-1.7.app/Contents/Resources/julia/share/julia/base/abstractarray.jl:2971
  push!(::VSCodeServer.JSON.Parser.PushVector, ::Any) at ~/.vscode/extensions/julialang.language-julia-1.6.28/scripts/packages/JSON/src/pushvector.jl:20
  ...
Stacktrace:
 [1] top-level scope
   @ REPL[277]:1

julia> testList = Vector{Matrix{Float64}}[]
Vector{Matrix{Float64}}[]

julia> push!(testList,testm)
ERROR: MethodError: no method matching Vector{Matrix{Float64}}(::Matrix{Float64})
Closest candidates are:
  Array{T, N}(::AbstractArray{S, N}) where {T, N, S} at /Applications/Julia-1.7.app/Contents/Resources/julia/share/julia/base/array.jl:563
  Vector{T}() where T at /Applications/Julia-1.7.app/Contents/Resources/julia/share/julia/base/boot.jl:476
  Array{T, N}(::StaticArraysCore.SizedArray{S, T, N, M, TData} where {M, TData<:AbstractArray{T, M}}) where {T, S, N} at ~/.julia/packages/StaticArrays/8Dz3j/src/SizedArray.jl:66

You want


julia> testList = Vector{Matrix{Float64}}(undef, 0)
Matrix{Float64}[]

or

julia> Matrix{Float64}[]
Matrix{Float64}[]

This is just a type, not an instance of the type

1 Like

This isn’t a Vector, this is a type. You must construct an instance. Try

Vector{Matrix{Float64}}()

A question, is n constant?

2 Likes

And you should use push!, not append!

I actually don’t see how this should allocate a lot, you are just shuffling around references to pre-existing arrays. Most likely, it’s due to the Vector{Any} parameter.

Maybe you can speed this up too? If you can use SMatrix from StaticArrays.jl. Or improving it otherwise.

1 Like

n is constant for each call of the routine. That is, each list has a fixed n

I see now that the error message told me Vector{Matrix{Float64}} was a type. For some reason that didn’t click.

I just re-@timed some largish cases and the garbage collection is ~10%. I’ll do some playing around and report back.

@DNF I’ve rarely used SMatrix
types. Maybe now is a good time to learn…

Thanks for the quick responses @DNF and @pdeffebach. I’m stuck at home with covid (it finally got me) so it’s nice to have some help when I’m solo at home.

And you should use push!, not append!

Why is that?

append! is meant to append one collection to another. push! is meant to add an item to a collection.

1 Like

Thanks for the help. I made two more versions. One that didn’t allocate anything extra—it just used a Boolean array to mark the unique matrices. The second one used the proper initialization of the vector of matrices.

Both of these had run-times identical to my initial solution. So, I guess computing the equivalence relation is the bottleneck.

I’m struggling to convert a 3xn array into a static array. Can’t seem to get syntax correct. I can make explicit definition but can’t initialize a static array with a variable:

@SMatrix [-0.5  0.0  0.0;
         0.0  0.0  0.5;
         0.5  0.0  0.5]
3×3 SMatrix{3, 3, Float64, 9} with indices SOneTo(3)×SOneTo(3):
 -0.5  0.0  0.0
  0.0  0.0  0.5
  0.5  0.0  0.5

julia> testm
3×3 Matrix{Float64}:
 -0.5  0.0  0.0
  0.0  0.0  0.5
  0.5  0.0  0.5

julia> @SMatrix testm
ERROR: Bad input for @SMatrix
Stacktrace:
  [1] error(s::String)
    @ Base ./error.jl:33
  [2] static_matrix_gen(#unused#::Type{SMatrix}, ex::Any, mod::Module)
    @ StaticArrays ~/.julia/packages/StaticArrays/8Dz3j/src/SMatrix.jl:20
  [3] var"@SMatrix"(__source__::LineNumberNode, __module__::Module, ex::Any)
    @ StaticArrays ~/.julia/packages/StaticArrays/8Dz3j/src/SMatrix.jl:103
  ...
julia> @SMatrix{3,3}(testm)
ERROR: Bad input for @SMatrix
Stacktrace:
  [1] error(s::String)
    @ Base ./error.jl:33

julia> @SMatrix [-0.5  0.0  0.0;
         0.0  0.0  0.5;
         0.5  0.0  0.5]
3×3 SMatrix{3, 3, Float64, 9} with indices SOneTo(3)×SOneTo(3):
 -0.5  0.0  0.0
  0.0  0.0  0.5
  0.5  0.0  0.5
julia> SMatrix{3,3}(testm)
3×3 SMatrix{3, 3, Float64, 9} with indices SOneTo(3)×SOneTo(3):
 0.0  0.0  0.0
 0.0  0.0  0.0
 0.0  0.0  0.0
1 Like

Got it! Thanks! I think the covid is making things harder than normal for me. Thanks again.