Finite strength-graph aggregation and Galerkin hierarchy with explicit statuses

This is a finite aggregation-based algebraic multigrid setup procedure; it constructs a hierarchy and does not claim that any cycle converges. All arithmetic and comparisons below are exact. An admissible input consists of an integer $n_0\ge 1$, a real symmetric positive-definite matrix $A_0=(a_{ij})\in {\mathbb{R}}^{n_0\times n_0}$ whose off-diagonal entries satisfy $a_{ij}\le 0$, a real threshold $0<\theta <1$, a coarse-size threshold $n_{\min }\ge 1$, and a real level cap $L\in {\mathbb{R}}_{\ge 0}$. A matrix with these sign and definiteness conditions is the matrix class used here. The terms strength graph, aggregate, prolongation, and Galerkin hierarchy are defined by the steps below.

Initialize $\mathrm{\ell }=0$ once and retain $A_0$ in the output. Then execute the following level steps.

1. Set $n_{\mathrm{\ell }}=\dim A_{\mathrm{\ell }}$. If $n_{\mathrm{\ell }}\le n_{\min }$, return status coarse-reached.
2. If $\mathrm{\ell }+1>L$ before the next aggregation attempt, return status level-cap.
3. On vertices $1,\dots ,n_{\mathrm{\ell }}$, place an undirected edge $\{i,j\}$ for $i\mathrm{\ne }j$ exactly when $a_{ij}^{(\mathrm{\ell })}<0$ and at least one of $-a_{ij}^{(\mathrm{\ell })}\ge \theta {\max }_{k\mathrm{\ne }i}(-a_{ik}^{(\mathrm{\ell })}),-a_{ij}^{(\mathrm{\ell })}\ge \theta {\max }_{k\mathrm{\ne }j}(-a_{jk}^{(\mathrm{\ell })})$ holds. This finite graph is the strength graph at level $\mathrm{\ell }$.
4. Let $U=\{1,\dots ,n_{\mathrm{\ell }}\}$ and start with no aggregates. While $U\mathrm{\ne }\mathrm{\varnothing }$, let $i$ be the smallest element of $U$, create one aggregate $C_r=\{i\}\cup (N(i)\cap U),$ where $N(i)$ is its strength-graph neighbour set, then remove every element of $C_r$ from $U$. This produces an ordered family of aggregates.
5. Let $n_{\mathrm{\ell }+1}$ be the number of aggregates. If $n_{\mathrm{\ell }+1}\ge n_{\mathrm{\ell }}$, return status coarsening-stalled with the hierarchy through level $\mathrm{\ell }$. Otherwise form the indicator prolongation $(P_{\mathrm{\ell }}{)}_{ir}=1\text{ if }i\in C_r,(P_{\mathrm{\ell }}{)}_{ir}=0\text{ otherwise},$ form the Galerkin coarse matrix $A_{\mathrm{\ell }+1}=P_{\mathrm{\ell }}^{\mathsf{T}}{A}_{\mathrm{\ell }}{P}_{\mathrm{\ell }}$, append $P_{\mathrm{\ell }},A_{\mathrm{\ell }+1}$, replace $\mathrm{\ell }$ by $\mathrm{\ell }+1$, and return to step 1.

The result contains all completed matrices and prolongations and exactly one status: coarse-reached, level-cap, or coarsening-stalled. Reaching any status is not a convergence or quality certificate.