# UnstructMG

**Repository Path**: yuntiy/unstruct-mg

## Basic Information

- **Project Name**: UnstructMG
- **Description**: Unstructured Algebraic Multigrid
- **Primary Language**: Unknown
- **License**: AGPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2025-09-16
- **Last Updated**: 2025-09-16

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## UnstructMG: Unstructured Algebraic Multigrid

UnstructMG is part of the TH-HPCA Multigrid Toolkit. Designed for solving sparse linear systems on unstructured grids (i.e., general graphs), it shares the same applicability scope as hypre-BoomerAMG, YHAMG, and Trilinos-MueLu.

### Basic Configuration
#### Number of Levels

Users may specify `C_nlevs` and `num_levs` with different values. Notice that the value of `C_nlevs` must be no greater than `num_levs`. Their meanings are as follows:

- `C_nlevs`: number of levels generated automatically in the **setup** phase.
- `num_levs`: number of levels actually run in the **solve** phase.

The levels not appearing in the solve phase are labeled by a boolen array `skipped`, where value 1 indicates that level would NOT be visited. Typically, the finest-level (i.e., the input level of users) should not be skipped.


#### Cycle Type
UnstructMG currently supports two kinds of cycles. V-cycle and W-cycle are specified as `'V'` and `'W'`, respectively, in `cycle` field. 


### Aggregation Methods

Specified in `coarsen` field. Valid types are listed in the tables by CoarsenID. More methods balancing efficiency and convergence are still under development.

#### Pairwise Aggregation

Pairwise means that each coarse-level point is formed by aggregating two fine-level points. The different variants in the following table represent distinct algorithmic implementations of this method for distributed parallel computing.

| Method      | CoarsenID | Description |
| ----------- | --------- | ----------- |
| naive       | `0`       | Processes ignore off-process nonzero entries and use local information to form coarser-level aggregates |
| coupled     | `1`       | Each process first handles points located on its partition boundary, respecting inter-process dependencies, with lower-rank processes taking priority. After completing boundary points, each process aggregate its interior points independently.             |
| modified    | `2`        | A heuristic algorithm adapted from parallel graph partitioning (ParMetis). Processes perform multiple iterations: in odd-numbered iterations, lower-rank processes may initiate aggregation requests to neighboring processes' points, while in even-numbered iterations, the reverse occurs.       |


#### Neighborwise Aggregation

Neighborwise means that each coarse-level point is formed by aggregating a fine-level point (called the root point) together with its neighboring points.

| Method      | CoarsenID | Description   |
| ----------- | --------- | ------------- |
| naive       | `10`      | 'naive' means the same parallel concept as the above of pairwise aggregation. |

#### Smoothed Aggregation

The interpolation matrix in unsmoothed aggregation is replaced by $P=(I-\omega D^{-1}A^f)\tilde{P}$, where $\tilde{P}$ is the unsmoothed interpolation matrix. The smoothing weight $0\leq \omega<1$ can be specified in `smwgt` field.


<!-- ### Restriction / Interpolation

#### Plain 



#### Smoothed Interpolation -->

### Smoothers

Specified in `smoother` field. Valid types are listed in the tables by Name. All these smoothers are built on block-Jacobi decomposition. The weights $0<w<1$ in the formulas can be specified in `weight` field. Usually, $w=0.7$ and $w=1.0$ is good for weighed Jacobi and symmetric GS, respectively.

| Method | Name | Mathematic Formula |
| ------ | --------- | ----------- |
| Weighted Jacobi | `PJ` | $x^{(t+1)}=x^{(t)}+wD^{-1}(b - Ax^{(t)})$, where $D=\text{diag}(A)$        |
| Gauss-Seidel (GS) | `PGS` | Forward: $x^{(t+1)}=x^{(t)}+wD^{-1}(b - Lx^{(t+1)} - (D+U)x^{(t)})$, Backward: $x^{(t+2)}=x^{(t+1)}+wD^{-1}(b - (L+D)x^{(t+1)} - Ux^{(t+2)})$, where $A=L+D+U$ and $D=\text{diag}(A)$ |
| ILU    | `ILU` or `ILUT` | $x^{(t+1)}=x^{(t)}+\tilde{U}^{-1}\tilde{L}^{-1}(b - Ax^{(t)})$, where $A\approx\tilde{L}\tilde{U}$   |

#### Weighted Jacobi

Straight-forward to implement. No read-after-write (RAW) dependence.

#### Gauss-Seidel (GS)

Hybrid type to implement. Similar to hypre-BoomerAMG and YHAMG, the off-core dependencies are ignored to enable sufficient multi-threading parallelism.

#### Incomplete Lower-Upper Factorization (ILU)

Multi-threading parallelism respecting the dependency order is enabled by the P2P synchronization sparsification algorithm in https://doi.org/10.1007/978-3-319-07518-1_8