Navier Stokes equations are basis for describing flow of viscous material to model fluid. These equations are difficult to solve because of their non linear nature. At their fundamental level, fluids are composed of interacting particles. Lattice gas models capture microscopic behavior by applying simple collision and propagation rules at lattice site. Based on a discrete analogy, we would like to mimic the local behavior of the local system by the action of a group. To do this we construct cayley graphs from group. Consider Automorphism of group , as a space of possible symmetries. In that way, we can interpret the neighborhood evolution of the fluid system as a simple re-writing process where he closest vicinity elements could vary to non-break causality and in that way we wanted to unravel which set of rules allow us to conserve? a momentum in the fluid. So basically, we want to describe how a particle collision rewrite system must be constrained for it’s rules to allow symmetries identified from the automorphism of group
Lattice Gas Models.
Lattice Gas Models.
The Lattice gas models(LGA) can be used to model fluid behaviour. The class of cellular automata used for simulation of hydrodynamics. Cellular Automata introduced by Von Neumann and Ulam, consists of a lattice,each site of which can have a finite number of states, the automation evolves in discrete steps, the sites being simultaneously updated by a deterministic or a non deterministic rule. We will consider a simple model known as HPP and FPP.
HPP and FPP:
HPP and FPP:
The simplest model emerged from taking only a square lattice. In this model HPP1. We are considering a Square Lattice2. Particles have a finite number of possibles velocities velocities . i.e it can have only four possible directions.2. For a given time step Δt, the particle can only move to other lattice point. That is the neighbouring lattice point.4. The choice of 's is related to the choice of the lattice . Since r + Δt must belong to the lattice. Not more than one particle is to be found at a given time and node, moving in a given direction. The following rules govern the model: 1. A particle when doesn't have a head on collision continues to move in the same direction. 2. A head on collision deflects a particle perpendicularly to the direction of initial propagation. 3. These laws obey conservation of mass and momentum. These are the only non trivial laws obeyed by them. For a given lattice model, with number of grids and N number of particles. For a given macrostate, we can Binomial , ] number of microstates. The above steps are essentially a deterministic rewriting dynamical system that evolves configurations of microstates in discrete time and space, in this case a grid. So we apply the rules at each node at a current time step , to determine the next configuration. So by the updating at each and every time step , we can look at evolution of different microstates. This evolution of microstates gives the evolution of gas. Another example we can consider Triangular lattice , each can interact with six neighbours, updating again require collision and propagation.But here we consider both deterministic and Non deterministic rules for collision.
V
i
V
i
V
i
N
0
[
N
0
N
Cellular Automata on Graphs:
Cellular Automata on Graphs:
Collisions in HPP and FHP model conserve mass and momentum locally, whereas propagation conserves them globally. These dynamics are invariant with respect to the discrete transformations that conserve the lattice.
For example, the HPP model is invariant under discrete transformations that conserve square lattice: discrete translations, rotations by π/2 and mirror symmetries.
Similarly, for the FHP model , we have for triangular lattice: discrete translations , rotations by π/3 and mirror symmetries with respect to a lattice line.
We can see that they are invariant under symmetric group in Euclidean geometry. So in this project , we would like to generalize the techniques of LGCA to cayley graphs which depends on groups.
For example, the HPP model is invariant under discrete transformations that conserve square lattice: discrete translations, rotations by π/2 and mirror symmetries.
Similarly, for the FHP model , we have for triangular lattice: discrete translations , rotations by π/3 and mirror symmetries with respect to a lattice line.
We can see that they are invariant under symmetric group in Euclidean geometry. So in this project , we would like to generalize the techniques of LGCA to cayley graphs which depends on groups.
Cayley Graphs:
Cayley Graphs:
Cayley graphs are graphs associated to a group and a set of generators for that group (there is also an associated directed graph).They geometrically display the actions of a group. They are dependent on a specific set of generators.
Formally Definition of a Cayley graph: The (decorated) Cayley graph Γ(G, S) of a group G with generating set S is the directed graph with edges colored by elements of S and vertex set G where the edge relation is given by g → gs.(by action of s)
The (undecorated) Cayley graph, which we will also denote by Γ(G, S) is obtained from the decorated Cayley Graph by forgetting the directions, colors, and
multiedges.
Some examples are as follows.
Formally Definition of a Cayley graph: The (decorated) Cayley graph Γ(G, S) of a group G with generating set S is the directed graph with edges colored by elements of S and vertex set G where the edge relation is given by g → gs.(by action of s)
The (undecorated) Cayley graph, which we will also denote by Γ(G, S) is obtained from the decorated Cayley Graph by forgetting the directions, colors, and
multiedges.
Some examples are as follows.
In[]:=
Get["C:\\Users\\abhishek joshi\\Documents\\GitHub\\QuiverGeometry\\Kernel\\init.m"]
In[]:=
LatticeQuiver[{"Dihedral",5},GraphLegend->Automatic]
Out[]=
In[]:=
LineQuiver[8,1,PeripheralVertices->1,GraphLegend->Automatic]
Out[]=
In[]:=
CycleQuiver[6,1,PeripheralVertices->1,GraphLegend->Automatic]
Out[]=
In[]:=
SquareQuiver[{6,6},{"(1,0)","(0,1)"},PeripheralVertices->3,GraphLegend->Automatic]
Out[]=
In[]:=
LatticeQuiver["Triangular",Cardinals->{"(1,0)","(0,1)","-(1,1)"},PeripheralVertices->4,GraphLegend->Automatic]
Out[]=
Graph Automorphisms:
Graph Automorphisms:
A Graph Homomorphism π is a mapping from edges of a Graph G to the edges of Graph H that preserves locality: incident edges of G are mapped to incident edges of H.
A Graph endomorphism is a mapping from edges of G to itself.
Invertible graph endomorphisms are called Graph Automorphisms.
The set of graph automorphisms of G is written as AUT(G), and forms a group in which the group operation is composition of automorphisms.
For a choice of generating automorphisms,AUT(G) yields a Cayley quiver,in which vertices represent automorphisms and edges represent the action of the generating automorphisms on these.
Some examples:
A Graph endomorphism is a mapping from edges of G to itself.
Invertible graph endomorphisms are called Graph Automorphisms.
The set of graph automorphisms of G is written as AUT(G), and forms a group in which the group operation is composition of automorphisms.
For a choice of generating automorphisms,AUT(G) yields a Cayley quiver,in which vertices represent automorphisms and edges represent the action of the generating automorphisms on these.
Some examples:
Finite Line Quiver:
Finite Line Quiver:
A line quiver of length '4'
In[]:=
LineQuiver[4]
Out[]=
In this Line Quiver, we have a Identity automorphisms and a reversal automorphism denoted by f(for flip). In this there is translation automorphism of ‘edge effects’-the end vertices are only vertices of degree ‘1’. So they must to sent to themselves or each other i.e by reversal.
Below are the table of automorphism for Finite Line Quiver
Out[]=
f |
these automorphisms compose to form a group isomorphic to .
The cayley Quiver for this is
2
The cayley Quiver for this is
In[]:=
CycleQuiver[2,"f",GraphLegend->Automatic,EdgeLength->100]
Out[]=
Infinite Line Quiver:
Infinite Line Quiver:
For a infinite Line quiver we have
In[]:=
LineQuiver[7,PeripheralVertices->1]
Out[]=
In this example, we have two automorphisms translations, denoted by t and reversal denoted by f. In infinite line graph , we have no constraint as finite line quivers such as edge effects. So we can have translation automorphism.
Out[]=
t | |
f |
The cayley quiver is isomorphic to . Here is the cayley quiver for this
1
In[]:=
LatticeQuiver[{"Dihedral",Infinity},Cardinals->{"f","t"},GraphLegend->Automatic]
Cyclic Quiver
Cyclic Quiver
A cyclic quiver of length '6'
For this example , we have rotation and reflection automorphism denoted by r and f. There are only two non trivial automorphisms.
The cayley quiver for this is
Finite Square
Finite Square
Square quiver of length '3'
In this also , as the finite quiver, we cannot have translation automorphism, only rotation in this case and reflection about horizontal axis, denoted by r and h.
The cayley quiver for this is as shown below
Infinite Square Quiver
Infinite Square Quiver
The infinite square quiver
Same as Finite Quiver, we have rotation and flip about horizontal axis given by r and h
We also translation automorphism in x and y direction.
There is a analogous comparison between Isometry group of Euclidean space,i.e the Euclidean Group E(n). The E(n) group comprises of all translations,rotations and reflections , and arbitrary combinations of them.
The Euclidean group is the symmetry group of space itself, and contains group of symmetries.
The Euclidean group is the symmetry group of space itself, and contains group of symmetries.
The Lattice Gas Model:
The Lattice Gas Model:
We will apply the principles from above to specify collision rules such that they respect the symmetries identified in the automorphisms.
Construct a Gas Object:
Construct a Gas Object:
We need to specify on which edges to apply these rules
we will let the system evolve , we see that without the rules, the particles just go through each other.
Make a new gas with rules:
Make a new gas with rules:
We see that the particles are just following the rule in one direction, which is not exactly the conservation of linear momentum.
While also specifying the rotational symmetry rules as "Pcycles["xyXY"]" we have obtained the analogue of linear momentum.
We can repeat the whole process in triangular grid, to get the results
For a Triangular Lattice
For a Triangular Lattice
Real Gas Simulation
Real Gas Simulation
We would like to look at real gas behaviour by increasing the particles size, and look at the picture.
We can see that from graph rewrite rules we are able to invoke the notion of conservation of linear momentum. To do this we have utilised the automorphism group. Translation automorphism is one such group which allows us to specify rule everywhere.
Translation is a subgroup of automorphism group.
The beauty of this phenomena is that one set of rules apply everywhere.
Translation is a subgroup of automorphism group.
The beauty of this phenomena is that one set of rules apply everywhere.
Future Direction
Future Direction
The original goal of this project to model a fluid behaviour on graphs. For that we need to understand the concept of isotropic viscosity and stress tensor.The Lattice Gas automata has been proved efficient for low subsonic flows, i.e we can derive Navier Stokes equations.To understand we need to look at the discrete translations and rotations appearing in nonlinear terms related diffusion. The viscosity does not have the universality that we saw in terms of microscopic collisions. It very much depends relaxation(or dissipation) mechanisms which are characterised by the fluctuation dissipation relations. For that we need to look at the analogue of that in lattice gas model. I think it would be interesting to look at isotropic turbulence through the lens of Graph theory. We already know from the work of Taylor and Kolmogrov, that isotropic turbulence exhibits rotational and reflection symmetry in it's swirling pattern. We could potentially rewrite the rules to generate a turbulence pattern.
Keywords
Keywords
1.Cayley Quivers
2. Graph Automorphisms
3. Graph Rewriting
4. Lattice Gas Model
2. Graph Automorphisms
3. Graph Rewriting
4. Lattice Gas Model
Acknowledgements
Acknowledgements
Mentor: Taliesin Beynon
I am deeply grateful for all the support and guidance I received from my Project mentor Tali Beynon.Thank you for the code for Gas model and Cayley Quiver. Swastik Banerjee, Sinuhé Perea for fruitful discussion , I also thank Stephen Wolfram and the team of WSS22 for hosting an amazing experience.
I am deeply grateful for all the support and guidance I received from my Project mentor Tali Beynon.Thank you for the code for Gas model and Cayley Quiver. Swastik Banerjee, Sinuhé Perea for fruitful discussion , I also thank Stephen Wolfram and the team of WSS22 for hosting an amazing experience.
References
References
1.Wolfram, S. Cellular automaton fluids 1: Basic theory. J Stat Phys 45, 471–526 (Aug. 1986). DOI: https://doi.org/10.1007/BF01021083
2.https://quivergeometry.net/cayley-quivers/
3. A New Kind of science ,https://www.wolframscience.com/nks/p377--fluid-flow/
4.Frisch, d’Hutnietes , HassJacher, Lallem and, Pomeau, Rivet"Lattice Hydrodynamics in Two and Three Dimensions",Complex Systems
2.https://quivergeometry.net/cayley-quivers/
3. A New Kind of science ,https://www.wolframscience.com/nks/p377--fluid-flow/
4.Frisch, d’Hutnietes , HassJacher, Lallem and, Pomeau, Rivet"Lattice Hydrodynamics in Two and Three Dimensions",Complex Systems