DOUG: Aggregation

Input: Matrix A defined on nodes $\mathcal{N} , \epsilon \in [0, 1]$ , aggregate size bounds $a_{min}$ , $a_{max}$ , aggregation radius r and number of smoothing steps
Output: Set of ( non-overlapping) aggregates $W=\{ W_j : j=1,...,n_a \}$

Scale the matrix $A:=(\mbox{diag}A)^{-1/2} A \; (\mbox{diag}A)^{-1/2}$
Filter out weak connections from matrix for which $|A_{ij}|<\varepsilon\;\underset{k\neq i}{\max}|A_{ik}|$ ;
Initialise $C:=\emptyset$ ; $\mathcal{F}:=\mathcal{N}$ ;
repeat ... until
1. ; choose a seednode from (or randomly from set $\mathcal{F}$ if $C==\emptyset$ )
2. Set layer $L(0):=\{x_j\}$ ; $\mathcal{F}:=\mathcal{F}\setminus L(0)$ and
3. for
  1. Set layer $L(i):=\underset{x_k\in L(i-1)}{\bigcup} ( \{ x_\ell:A_{k\ell}\neq 0 \} )$
  2. If $i\leq r$ , add to all $x\in\mathcal{F}$ that are connected through to at least 2 nodes in , set $\mathcal{F}:=\mathcal{F}\setminus L(i)$ and set $W_j:=W_j\cup L(i)$ .
4. Find $i_{max}:=\underset{i\in\{r+1,...,2r+1\}}{\mbox{argmax}}|L(i)|$ (i.e. the largest layer) and add to all $x\in L(i_{max})$ of shortest path length from
set
Merge any aggregate that is too small (i.e. $|W_j| < a_{min}$ ) with a connected neighbouring aggregate (subject to the requirement $|W_j \cup W_k | \leq a_{max}$ ; it may be necessary to split up to achieve this) and shrink accordingly.

The smoothing is then done to get restriction matrix and coarse problem (see Smoothed Coarse Spaces).