Use IntSet's to represent a Supernode?

[dmbates]

I am planning to create a branch to see what I can do with using the Julia IntSet structure to represent a Supernode. It seems that there is a lot of overhead in creating various SimpleAdjacencyList structures during the partitioning. The first step would be to change the struct_set value in the generator for Supernode from a Set{Int}() to an IntSet but I think that other parts could also be reexpressed using IntSet.

Anyway I will play around with it and see if I can get anywhere/

[poulson]

Do you have any timings that you can share?

[dmbates]

Nothing yet. I'm still trying to work out what is happening in functions lke bisect. As I see it, the purpose of the gPruned graph is to remove self-edges and/or ensure that edge (i,j) occurs in both adjlist[i] and adjlist[j]. Is that correct?

I should do timings first. My impression is that some of the add_edge operations could get expensive because of the generality of operations like vertex_index. Certainly the time in constructing a Supernode is all being spent in bisect and recursive calls to Supernode.

[poulson]

The purpose of gPruned is to take a graph which (generally) has a larger set of target than source values and to both prune out the target values that are outside of the source set and to remove self-edges.

[dmbates]

Thanks.

[mlubin]

@dmbates, vertex_index should be O(1), but there were a number of recent changes to Graphs which affected this behavior (JuliaAttic/OldGraphs.jl#135). We may need some fixes there.

[dmbates]

A preliminary timing is that the version in the IJulia notebook takes 0.4 sec and allocates 9 MB on my desktop to create the Supernode from the adjacency list. Using the version in the package I get

julia> @time Supernode(simple_adjlist(A),p);
elapsed time: 0.104149494 seconds (4 MB allocated)

after warmup. Of course, this could be because of IJulia overhead but I don't think it should be.

[dmbates]

I added a function intsetv to MultiFrontalCholesky/src/util.jl. The purpose is to convert the part vector to a vector of 3 IntSets. (An alternative is to create an immutable type that consists of 3 IntSets.) Accessing the sizes of the partitions is as simple as

[length(i) for i in isv]

Similarly, the operation of partToPerm can be expressed as

vcat([collect(i) for i in isv]...)

I'll check if I can write a bisect function using this representation of the partition.

By the way, the 0's in the part vector are the left part, the 1's are the right part, what are the 2's called?

[poulson]

The part vector represents a nodal bisection of a graph, and so the 0 and 1 pieces are separated by the vertices of the separator (which is denoted by 2).