0
# Aggregation Methods
1

2
Algorithms for grouping fine grid points into coarse grid aggregates for Smoothed Aggregation AMG. Aggregation determines the coarse grid structure and significantly impacts solver performance.
3

4
## Capabilities
5

6
### Standard Aggregation Methods
7

8
Core aggregation algorithms for general problems.
9

10
```python { .api }
11
def standard_aggregation(C, **kwargs):
12
    """
13
    Standard aggregation algorithm.
14
    
15
    Greedy algorithm that creates aggregates by selecting seed points
16
    and adding strongly connected neighbors. Most commonly used
17
    aggregation method for Smoothed Aggregation AMG.
18
    
19
    Parameters:
20
    - C: sparse matrix, strength of connection matrix
21
    - **kwargs: additional parameters:
22
        * symmetrize: bool, symmetrize strength matrix (default True)
23
        * aggregate_mat: bool, return aggregation matrix (default False)
24
    
25
    Returns:
26
    array: aggregation array where AggOp[i] = j means
27
        fine point i belongs to aggregate j
28
    
29
    Notes:
30
    - Creates reasonably sized aggregates with good connectivity
31
    - Balances aggregate size and quality
32
    - Default choice for most problems
33
    """
34

35
def naive_aggregation(C, **kwargs):
36
    """
37
    Naive aggregation algorithm.
38
    
39
    Simple aggregation that pairs neighboring points without
40
    sophisticated connectivity analysis. Fast but may create
41
    poor aggregate quality.
42
    
43
    Parameters:
44
    - C: sparse matrix, strength of connection matrix
45
    - **kwargs: additional aggregation parameters
46
    
47
    Returns:
48
    array: aggregation array
49
    
50
    Notes:
51
    - Fastest aggregation method
52
    - May create disconnected or poor-quality aggregates
53
    - Useful for testing and comparison purposes
54
    """
55
```
56

57
**Usage Examples:**
58

59
```python
60
import pyamg
61
import numpy as np
62

63
# Standard aggregation for Poisson problem
64
A = pyamg.gallery.poisson((50, 50))
65
C = pyamg.strength.symmetric_strength_of_connection(A)
66
AggOp = pyamg.aggregation.standard_aggregation(C)
67
print(f"Created {AggOp.max() + 1} aggregates from {len(AggOp)} points")
68

69
# Naive aggregation for comparison
70
AggOp_naive = pyamg.aggregation.naive_aggregation(C) 
71
print(f"Naive: {AggOp_naive.max() + 1} aggregates")
72

73
# Use in solver construction
74
ml = pyamg.smoothed_aggregation_solver(A, aggregate='standard')
75
```
76

77
### Advanced Aggregation Methods
78

79
Sophisticated aggregation algorithms for challenging problems.
80

81
```python { .api }
82
def lloyd_aggregation(C, ratio=0.03, distance='unit', maxiter=10, **kwargs):
83
    """
84
    Lloyd clustering-based aggregation.
85
    
86
    Uses Lloyd clustering algorithm (k-means variant) to create
87
    aggregates with optimal geometric properties. Particularly
88
    effective for problems with geometric structure.
89
    
90
    Parameters:
91
    - C: sparse matrix, strength of connection matrix
92
    - ratio: float, desired coarsening ratio (0 < ratio < 1):
93
        * 0.03: aggressive coarsening (default)
94
        * 0.1: moderate coarsening
95
        * 0.2: mild coarsening
96
    - distance: str, distance measure for clustering:
97
        * 'unit': unit distance (default)
98
        * 'abs': absolute value distance  
99
        * 'min': minimum distance
100
    - maxiter: int, maximum Lloyd iterations
101
    - **kwargs: additional clustering parameters
102
    
103
    Returns:
104
    array: aggregation array with improved geometric properties
105
    
106
    Notes:
107
    - More expensive than standard aggregation
108
    - Can create more uniform aggregate sizes
109
    - Requires coordinate information for best results
110
    """
111

112
def balanced_lloyd_aggregation(C, ratio=0.03, **kwargs):
113
    """
114
    Balanced Lloyd clustering aggregation.
115
    
116
    Variant of Lloyd aggregation that enforces more uniform
117
    aggregate sizes while maintaining clustering quality.
118
    
119
    Parameters:
120
    - C: sparse matrix, strength of connection matrix
121
    - ratio: float, desired coarsening ratio
122
    - **kwargs: Lloyd clustering parameters
123
    
124
    Returns:
125
    array: aggregation array with balanced aggregate sizes
126
    
127
    Notes:
128
    - Attempts to create aggregates of similar size
129
    - May sacrifice some geometric optimality for balance
130
    - Good for problems requiring uniform coarsening
131
    """
132

133
def metis_aggregation(C, ratio=0.03, **kwargs):
134
    """
135
    METIS-based graph partitioning aggregation.
136
    
137
    Uses METIS graph partitioning library to create aggregates
138
    by partitioning the strength graph. Produces high-quality
139
    aggregates but requires METIS installation.
140
    
141
    Parameters:
142
    - C: sparse matrix, strength of connection matrix
143
    - ratio: float, desired coarsening ratio
144
    - **kwargs: METIS-specific parameters
145
    
146
    Returns:
147
    array: aggregation array from graph partitioning
148
    
149
    Notes:
150
    - Requires pymetis package installation
151
    - Creates high-quality graph partitions
152
    - More expensive than simpler methods
153
    - Excellent for unstructured problems
154
    
155
    Raises:
156
    ImportError: if METIS is not available
157
    """
158
```
159

160
**Usage Examples:**
161

162
```python
163
# Lloyd aggregation with custom ratio
164
A = pyamg.gallery.linear_elasticity((30, 30))
165
C = pyamg.strength.symmetric_strength_of_connection(A)
166
AggOp_lloyd = pyamg.aggregation.lloyd_aggregation(C, ratio=0.05)
167

168
# Balanced aggregation
169
AggOp_balanced = pyamg.aggregation.balanced_lloyd_aggregation(C, ratio=0.05)
170

171
# METIS aggregation (if available)
172
try:
173
    AggOp_metis = pyamg.aggregation.metis_aggregation(C, ratio=0.05)
174
    print(f"METIS: {AggOp_metis.max() + 1} aggregates")
175
except ImportError:
176
    print("METIS not available")
177

178
# Compare aggregate counts
179
print(f"Lloyd: {AggOp_lloyd.max() + 1} aggregates")
180
print(f"Balanced: {AggOp_balanced.max() + 1} aggregates")
181
```
182

183
### Prolongation Smoothing
184

185
Methods for smoothing tentative prolongation operators created from aggregation.
186

187
```python { .api }
188
def jacobi_prolongation_smoother(A, T, C=None, omega=1.0):
189
    """
190
    Jacobi prolongation smoother.
191
    
192
    Applies weighted Jacobi smoothing to tentative prolongation
193
    operator to improve interpolation quality. Most common
194
    prolongation smoother.
195
    
196
    Parameters:
197
    - A: sparse matrix, fine level operator
198
    - T: sparse matrix, tentative prolongation operator
199
    - C: sparse matrix, strength of connection (optional)
200
    - omega: float, relaxation parameter (0 < omega <= 1):
201
        * 1.0: full Jacobi smoothing (default)
202
        * 4/3: common choice for SPD problems
203
        * 0.67: conservative smoothing
204
    
205
    Returns:
206
    sparse matrix: smoothed prolongation operator P
207
    
208
    Notes:
209
    - P = (I - omega * D^{-1} * A) * T where D = diag(A)
210
    - Improves interpolation quality at modest cost
211
    - Default choice for most problems
212
    """
213

214
def richardson_prolongation_smoother(A, T, omega=1.0, **kwargs):
215
    """
216
    Richardson prolongation smoother.
217
    
218
    Applies Richardson iteration to smooth tentative prolongation.
219
    Alternative to Jacobi with different stability properties.
220
    
221
    Parameters:
222
    - A: sparse matrix, fine level operator
223
    - T: sparse matrix, tentative prolongation
224
    - omega: float, relaxation parameter
225
    - **kwargs: additional smoothing parameters
226
    
227
    Returns:
228
    sparse matrix: Richardson-smoothed prolongation operator
229
    
230
    Notes:
231
    - Less common than Jacobi smoothing
232
    - May have different convergence properties
233
    - Experimental alternative smoother
234
    """
235

236
def energy_prolongation_smoother(A, T, **kwargs):
237
    """
238
    Energy-minimizing prolongation smoother.
239
    
240
    Computes prolongation that minimizes energy norm of
241
    interpolation error. Most sophisticated smoother but
242
    more expensive to compute.
243
    
244
    Parameters:
245
    - A: sparse matrix, fine level operator
246
    - T: sparse matrix, tentative prolongation
247
    - **kwargs: energy minimization parameters
248
    
249
    Returns:
250
    sparse matrix: energy-minimized prolongation operator
251
    
252
    Notes:
253
    - Optimal in energy norm sense
254
    - Higher computational cost than Jacobi
255
    - May provide better convergence for difficult problems
256
    """
257
```
258

259
**Usage Examples:**
260

261
```python
262
# Manual prolongation smoothing
263
A = pyamg.gallery.poisson((40, 40))
264
C = pyamg.strength.symmetric_strength_of_connection(A)
265
AggOp = pyamg.aggregation.standard_aggregation(C)
266

267
# Create tentative prolongation (usually done internally)
268
n_fine = A.shape[0]
269
n_coarse = AggOp.max() + 1
270
T = sp.csr_matrix((np.ones(n_fine), (np.arange(n_fine), AggOp)), 
271
                  shape=(n_fine, n_coarse))
272

273
# Apply different smoothers
274
P_jacobi = pyamg.aggregation.jacobi_prolongation_smoother(A, T, omega=4.0/3.0)
275
P_energy = pyamg.aggregation.energy_prolongation_smoother(A, T)
276

277
print(f"Tentative nnz: {T.nnz}")
278
print(f"Jacobi nnz: {P_jacobi.nnz}")  
279
print(f"Energy nnz: {P_energy.nnz}")
280

281
# Use in solver construction
282
ml = pyamg.smoothed_aggregation_solver(A, smooth='jacobi')
283
ml_energy = pyamg.smoothed_aggregation_solver(A, smooth='energy')
284
```
285

286
### Near-Nullspace Handling
287

288
Functions for incorporating near-nullspace information into aggregation.
289

290
```python { .api }
291
def fit_candidates(AggOp, B, **kwargs):
292
    """
293
    Fit near-nullspace candidates to aggregation pattern.
294
    
295
    Creates tentative prolongation operator that preserves
296
    given near-nullspace vectors on each aggregate. Essential
297
    for problems with non-trivial nullspaces.
298
    
299
    Parameters:
300
    - AggOp: array, aggregation array mapping fine to coarse
301
    - B: array, near-nullspace vectors (n_fine × n_candidates):
302
        * Constant vector for scalar problems
303
        * Rigid body modes for elasticity
304
        * Custom modes for specific problems
305
    - **kwargs: fitting parameters
306
    
307
    Returns:
308
    sparse matrix: tentative prolongation operator that
309
        interpolates near-nullspace exactly
310
    
311
    Notes:
312
    - Critical for elasticity and other systems problems
313
    - B should span the near-nullspace of the operator
314
    - Quality of B significantly affects AMG performance
315
    """
316
```
317

318
**Usage Examples:**
319

320
```python
321
# Near-nullspace for elasticity problem
322
A = pyamg.gallery.linear_elasticity((25, 25))
323
n_dof = A.shape[0]
324

325
# Create rigid body modes (3 modes for 2D elasticity)
326
B = np.zeros((n_dof, 3))
327
# Translation modes
328
B[0::2, 0] = 1.0  # x-translation
329
B[1::2, 1] = 1.0  # y-translation
330
# Rotation mode (simplified)
331
B[0::2, 2] = np.arange(0, n_dof//2)  # x-coordinates
332
B[1::2, 2] = -np.arange(0, n_dof//2)  # -y-coordinates
333

334
# Create aggregation and fit candidates
335
C = pyamg.strength.symmetric_strength_of_connection(A)
336
AggOp = pyamg.aggregation.standard_aggregation(C)
337
T = pyamg.aggregation.fit_candidates(AggOp, B)
338

339
# Use in solver
340
ml = pyamg.smoothed_aggregation_solver(A, B=B)
341
```
342

343
## Aggregation Quality Analysis
344

345
### Aggregate Statistics
346

347
```python
348
def analyze_aggregation(AggOp, C=None):
349
    """Analyze aggregation quality."""
350
    n_fine = len(AggOp)
351
    n_coarse = AggOp.max() + 1
352
    
353
    # Basic statistics
354
    coarsening_ratio = n_coarse / n_fine
355
    avg_agg_size = n_fine / n_coarse
356
    
357
    # Size distribution
358
    agg_sizes = np.bincount(AggOp)
359
    min_size, max_size = agg_sizes.min(), agg_sizes.max()
360
    
361
    print(f"Coarsening ratio: {coarsening_ratio:.3f}")
362
    print(f"Average aggregate size: {avg_agg_size:.1f}")
363
    print(f"Aggregate size range: {min_size} - {max_size}")
364
    
365
    return {
366
        'coarsening_ratio': coarsening_ratio,
367
        'avg_size': avg_agg_size,
368
        'size_range': (min_size, max_size)
369
    }
370

371
# Example usage
372
A = pyamg.gallery.poisson((50, 50))
373
C = pyamg.strength.symmetric_strength_of_connection(A)
374
AggOp = pyamg.aggregation.standard_aggregation(C)
375
stats = analyze_aggregation(AggOp, C)
376
```
377

378
## Selection Guidelines
379

380
### Method Selection by Problem Type
381

382
- **General problems**: Standard aggregation
383
- **Geometric problems**: Lloyd or balanced Lloyd  
384
- **Unstructured meshes**: METIS aggregation
385
- **Testing/debugging**: Naive aggregation
386

387
### Parameter Tuning
388

389
```python
390
# Aggressive coarsening (fewer levels, less memory)
391
AggOp_aggressive = pyamg.aggregation.lloyd_aggregation(C, ratio=0.02)
392

393
# Conservative coarsening (more levels, better convergence)
394
AggOp_conservative = pyamg.aggregation.lloyd_aggregation(C, ratio=0.1)
395
```
396

397
### Performance vs Quality Trade-offs
398

399
- **Speed**: naive < standard < lloyd < metis
400
- **Quality**: naive < standard < lloyd ≈ metis
401
- **Memory**: Similar for all methods
402
- **Setup Cost**: naive < standard < lloyd < metis
403

404
### Common Issues
405

406
- **Poor convergence**: Try Lloyd or METIS aggregation
407
- **Expensive setup**: Use standard instead of Lloyd/METIS
408
- **Unbalanced aggregates**: Use balanced_lloyd_aggregation
409
- **Systems problems**: Ensure proper near-nullspace (B matrix)