"dispatch" on whether or not a matrix is symmetric? (aka should I use a function barrier?)

New to Julia
1

Short version: is a pattern like issymmetric(x) && (x = Symmetric(x)) type-unstable, and will it have performance consequences? Details below.

I have a user-facing function that looks something like

function f(x::Matrix)
    for i in 1:big_number
        helper(x)
    end
end

And helper has a fast version and a slow version:

helper(x::AbstractMatrix) = ... # slow
helper(x::Symmetric) = ... # fast

I’d like to efficiently use the version of helper appropriate to whether or not x is symmetric, without requiring the user to themselves wrap x in a Symmetric view. That is, I don’t want to have two methods f(x::Symmetric) and f(x::AbstractMatrix).

So I have two ideas:

1. Use a function barrier:

function f(x)
    issymmetric(x) && (x = Symmetric(x))
    return _f_logic(x)
end
function _f_logic(x)
    for i in 1:big_number
        helper(x)
    end
end

2. Simply wrap x in Symmetric within the main function:

function f(x::Matrix)
    issymmetric(x) && (x = Symmetric(x))
    for i in 1:big_number
        helper(x)
    end
end

Now, I’d expect - and @code_warntype seems to confirm - that option 2 introduces type instability since the compiler can’t know the type of x within the big loop; that type depends on the issymmetric call which depends on runtime values. In practice, however, there’s no meaningful performance difference between these two approaches and option 2 seems rather more readable to me.

Am I missing something? Is there a more idiomatic way to deal with this use case?

1 Like
2

Why? Using Symmetric is the perfect way to signal that the matrix is symmetric.

The function barrier approach is your best option if symmetry needs to be checked in runtime. This is what all polyalgorithms do, eg \.

1 Like
3

To supplement what @Tamas_Papp said, check out the runtime checks for \ here:

https://github.com/JuliaLang/julia/blob/master/stdlib/LinearAlgebra/src/generic.jl#L1089

3 Likes
4

Why? Using Symmetric is the perfect way to signal that the matrix is symmetric

In this case, the user may generate the matrix without knowing or caring that it’s symmetric; it’s just a convenient property. I don’t want to offload the work of wondering whether a matrix has certain convenient properties onto the user.

5

Unfortunately in practice, matrices which “should be” symmetric may not end up as one because of floating error.

Whether this is important depends on your problem.

2 Likes
6

Yeah, that’s a great point. The use case here is that matrices are distance matrices defining instances of the traveling salesman problem. A matrix that should be symmetric but isn’t due to floating point error should still produce a valid problem instance, albeit one that solves more slowly.

One of my main goals with TravelingSalesmanHeuristics.jl is ease of use, so I’m willing to accept “occasional slower-than-needed algorithms because a matrix is barely asymmetric” as the cost of “not making the user explicitly indicate whether or not their problem is symmetric.”

7

You may want to consider forcing exact symmetry with

AS .= 0.5*(A .+ A')

that may be cheap in comparison with solving a non symmetric problem

1 Like