Some of the work I do in the study of discrete dislocation dynamics (a branch of materials modeling) involves topological changes on a graph: changes in the connectivity of nodes, as well as deletion and addition of nodes. This means the graph structure is unknown and dynamically changing. As such, there is very little that can be known of the graph at any point without traversing it completely.

I've been thinking that there must be a way to do some sort of $\mathcal{O}(\log N)$ ($N=$ number of graphs) parallelisation via reduction if we can communicate information between nodes. However, given that the structure of the graph is largely unknown and its storage in memory is not necessarily ordered, I'm thinking of not bothering.

Every algorithm I've come across exploits some feature that greatly limits the graph's properties, but in this case the only feature is that all of them are closed. The only way of knowing which nodes belong to which graph is to follow the connectivity. There's also the issue of the scaling constant and communication latency depending on how the data is segmented for parallelisation. So minimising inter-thread/core communication is quite important.

Admittedly, this could be somewhat naively achieved by traversing the connectivity and parallelising over closed graphs, thus running the serial algorithm for each closed graph, but the memory scaling of this naive algorithm is $\mathcal{O}(N)$ ($N=$ number of graphs), nevermind the number of nodes in each graph.

Does anyone have any ideas/suggestions? This would help a lot with some of our newer simulations with high dislocation densities.

  • $\begingroup$ +10. Thanks for asking this here Dan! If it gets an answer, it's on topic! Otherwise we can easily migrate it to MathOverflow or Mathematics.SE or ComputerScience.SE or TheoreticalComputerScience.SE. $\endgroup$ Jul 27, 2020 at 23:05
  • $\begingroup$ Indeed, discrete dislocation dynamics is pretty niche and quite interdisciplinary. This would help a lot with some of our denser simulations. $\endgroup$ Jul 27, 2020 at 23:30
  • $\begingroup$ Another stack with plenty of graph theory and algorithm questions is StackOverflow itself. $\endgroup$
    – Anyon
    Jul 27, 2020 at 23:34
  • $\begingroup$ @Anyon We have entertained discrete math problems here such as here and here. Dan: It might help if you mentioned that you're working on discrete dislocation dynamics (which we all know is a branch of Materials Modeling) and that this would help with some of the denser simulations. Often it helps to show how something relates to the subject of the site. $\endgroup$ Jul 27, 2020 at 23:45
  • 2
    $\begingroup$ Those other stack exchanges are other options, just thought it might be worth trying here first. $\endgroup$ Jul 27, 2020 at 23:49