# Accelerating FVM-Based Parallel Fluid Simulations with Better Grid Renumbering Methods
## 4 CQ: The Cell-Quotient Grid Renumbering Algorithm for Large-Scale Parallel Fluid Simulations
### Cell-Quotient (CQ) Numbering Algorithm
```
1:\(mesh_{o}\)
2:\(mesh_{n}\)
3:initialise: convergence index \(e\in[0.01,0.05]\),\(value=DOUBLE\_MAX\)
4:while\(value\geq e\)do
5: initialise \(\beta_{o}\): sparse matrix maximum bandwidth
6:for all\(mesh_{o}\_element(i)\) in \(mesh_{o}\_nElement()\),and \(i=0,1,\ldots,n\)do
7: initialise \(I\):Press the sum of all neighbor numbers of \(mesh_{o}\_element(i)\) into \(I\)
8: initialise \(L\): Press the total number of neighboring cells of \(mesh_{o}\_element(i)\) into \(L\)
9:endfor
10: initialise \(K\)
11:for all\(I(i),L(i)\) in \(I\),\(L\), and \(i=0,1,\ldots,n\)do
12:\(cell\_quotient(i)=I(i)/L(i)\)
13: Establish the \(key-value\) relationship between \(mesh_{o}\_element(i)\) and \(cell\_quotient[i]\) in \(K\)
14:endfor
15:for all members in K do
16: renumbering all the \(mesh_{o}\_element(i)\).\(id()\) according to the ascending order of \(cell\_quotient\)
17: update \(mesh_{n}\) with the renumbered element ids. 18:endfor
19: initialise \(\beta_{n}\): sparse matrix maximum bandwidth after renumbering
20:\(value=(\beta_{o}-\beta_{n})/\beta_{o}\)
21: clear \(I,L,K\)
22: if \(value<0\) goto step 3,and continue calculation
23:endwhile
```  
**Algorithm 2** CQ Numbering Algorithm \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Cell ID** &
\begin{tabular}{c} **Disorder** \\ **Neighboring Cell** \\ \end{tabular} & **Sum of Number** & **CQ** \\ \hline
1 & 3,5 & 8 & 4.0 \\
2 & 4,6 & 10 & 5 \\
3 & 1,7,8 & 16 & 5.3 \\
4 & 2,7,8 & 17 & 5.7 \\
5 & 1,8 & 9 & 4.5 \\
6 & 2,7 & 9 & 4.5 \\
7 & 3,4,6 & 13 & 4.3 \\
8 & 3,4,5 & 12 & 4.0 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The cell quotient calculation method for the disorder grid. The meaning of each column is the same as in Table 1.  
Step 1 is the initialization of the program before starting the loop. It mainly sets the convergence coefficient \(\epsilon\), which is usually set from 0.01 to 0.05. Step 2 starts the main loop of the program. Step 2 and step 18 calculate the maximum bandwidth of the sparse matrix before and after renumbering, respectively. Step 19 updates the current value. Steps 4 to 9 calculate the neighbor numbers of all grids and the number of neighbor grids. Steps 11 to 14 establish the \(key-value\) relationship between the cell quotient and the corresponding mesh in container \(K\). Step 15 is the renumbered gird. Step 15 is the key step for renumbering. Step 21 prevents renumbering from becoming ineffective. However, the algorithm has certain implementation difficulties. (1) Since all the cases in this paper use unstructured grids, the neighbors cannot be traversed directly with indexes. (2) The algorithm is extremely dependent on the initial numbering. If the initial numbering is too chaotic, as the case size gradually increases, the iteration time of the numbering method with this quotient will be very long and the algorithm is unstable, which defeats the original purpose of the efficient renumbering algorithm. Therefore, this paper is the implementation of the CQ algorithm under the premise of Greedy algorithm. The classical Greedy algorithm is used as the initial numbering method, and the CQ algorithm is used for the second renumbering at the end. At the same time, due to the object-oriented development feature of ACT framework adopted in this paper, each unit has a \"neighbor\" pointer. Therefore, the above two difficulties can be well solved. It was proved that the numbering time of both the Greedy algorithm and the CQ algorithm based on the Greedy algorithm is several seconds in parallel computing, which is negligible in CFD numerical simulation.