DOUG 0.2

Aggregation

The algorithm is defined in SpMtx_aggregation::SpMtx_aggregate

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

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