Best way to construct a sparse matrix

General Usage Performance
1

Hi!

I’m writing a function that constructs a symmetric sparse matrix. I’ve tried two implementations:

function version1(x::Vector{Date}, k::Function)

    n   = length(x)
    mat = speye(Float64, n, n)

    for i = 1:n
        for j = 1:(i - 1)
            w = Dates.value(x[i] - x[j])
            w = k(w)
            (w > 0.0) && (mat[j, i] = w)
        end
    end

    return Symmetric(mat)
end

function version2(x::Vector{Date}, k::Function)

    n    = length(x)
    idx₁ = Vector{Int}(1:n)
    idx₂ = Vector{Int}(1:n)
    val  = fill(1.0, n)

    for i = 1:n
        for j = 1:(i - 1)
            w = Dates.value(x[i] - x[j])
            w = k(w)
            if w > 0.0
                push!(idx₁, j)
                push!(idx₂, i)
                push!(val, w)
            end
        end
    end

    return Symmetric(sparse(idx₁, idx₂, val))
end

I’ve tried them on both on a vector of 5400 dates. After an initial run for compilation, @time gives: version1: 7.849785 seconds (48 allocations: 83.900 MiB); version2: 0.676957 seconds (75 allocations: 283.136 MiB, 24.15% gc time). These results are consistent across multiple runs.

Is there are a reason to prefer version1? Are the memory savings worth the extra running time?

2

Use what is faster. GC will take care of memory.

That said, I would try something like k.(x .- x') (adjusted appropriately, but you did not provide an MWE) and then convert it to sparse, if it is sparse. But from the allocations, I am not so sure about that.

3

Changing the sparsity pattern is expensive so the second version is likely to prefer.

4

Thanks!

k.(x .- x')

It’s a nice idea. It is faster than version2 is the input vector is small, but it is slower when it’s large. (My guess: it doesn’t exploit symmetry and k is typically expensive to compute.)

if it is sparse

About 2/3 of the entries are zeros. I don’t know if it qualifies.