## 3 Graph Theory and G-Pre Preconditioning Algorithm Design  
### Graph Theory  
Graphs are ubiquitous in scientific computing. For example, a discretized lattice of partial differential equations can be conceptualized as a graph. Similarly, the sparse structure of a sparse matrix can be represented graphically. Graph partitioning and reordering are important problems in various fields, including scientific computing, VLSI design,  
Figure 1: Schematic diagram of the LU factorization process of \(A\). geographic information systems, operations research, and mission planning [53]. During the iterative solution of systems of linear equations in finite element methods, a key step in each iteration involves the product of sparse matrices and dense vectors. However, the sparse structure of the stiffness matrix and the intrinsic algorithmic properties of sparse matrix vector multiplication (SpMV) result in significant data storage requirements and low cache hit rates. This situation provides an opportunity to increase computational speed by enhancing the continuity of memory access. The SpMV process for sparse matrices is shown in Figure 2, where the black squares represent non-zero elements in the vector and a row of the matrix, and the light-colored areas represent a row of the matrix and a column of the vector. For each calculation, a single row of matrix \(M\) is multiplied by the elements in vector \(V\). The relevant data are read according to the position of the non-zero elements in the rows of matrix \(M\). The vector \(T\) is then obtained by multiplication and accumulation. The challenge of graph partitioning arises when solving the sparse system \(Ax=b\) in parallel. Graph partitioning is a crucial preconditioning stage in high-performance parallel computing. Efficient graph partitioning and the reordering of the graph associated with matrix \(A\) can distribute the computational workload evenly across computing nodes and significantly reduce communication overhead during parallel SpMV operations [54]. In this study, the graph partitioning algorithm METIS [53] was utilized. METIS is a well-known algorithm that divides graph nodes into cohesive clusters to effectively minimize edge cuts (defined as the number of edges connecting different clusters). The overall graph partitioning phase consists of three stages--coarsening, division, and refinement. In the reordering phase, the graph is partitioned using a multilevel full set of dissection strategies, and the number of partitions divided depends on the actual situation. Taking a graph divided into two subdomains as an example, as shown in Figure 3. The original graph region contains seven nodes, and the nodes are connected with edges. When the graph is divided and rearranged, each node has a different sequence number, the node with the most connected edges (the red node in Figure 3) is usually selected for division. When the graph is divided into two different subdomains, the nodes within the same subdomain are sequentially renumbered to create a reordered mapping to minimize the filling of sparse matrices [55]. As shown in Figure 4, graph reordering can be categorized as full graph reordering or partition reordering. Figure 4b represents full graph rearrangement, i.e., the rearrangement of elements in the entire graph. Full graph rearrangement results in a tightly arranged block of non-zero elements, and although it also centralizes the non-zero elements, having only one block of elements is not conducive to parallel computation. Figure 4c represents partitioned rearrangement, where the graph is first partitioned and then subdivided so that tightly arranged blocks of elements can be obtained in different partitions; this is favorable for parallel computation. Through graph partitioning and reordering, a reordered matrix with multiple partitions is obtained, where non-zero elements are tightly arranged. This arrangement facilitates the subsequent iterative solving process.