Appending a matrix to a vector of matrices

General Usage Performance
,
1

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
2

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
3

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
4

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.

5

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

1 Like
6

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.

7

And you should use push!, not append!

Why is that?

1 Like
8

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

1 Like
9

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
10 
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
11

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