0
# Strength of Connection
1
2
Methods for determining the strength of connections between unknowns, fundamental to AMG coarsening strategies. Strength of connection measures identify which matrix entries represent strong coupling that must be preserved during coarsening.
3
4
## Capabilities
5
6
### Classical Strength Measures
7
8
Traditional strength of connection measures based on matrix entry magnitudes.
9
10
```python { .api }
11
def classical_strength_of_connection(A, theta=0.25):
12
"""
13
Classical strength of connection measure.
14
15
Determines strong connections based on ratio of off-diagonal
16
entries to diagonal entries. Entry A[i,j] is strong if
17
|A[i,j]| >= theta * max{|A[i,k]| : k != i}.
18
19
Parameters:
20
- A: sparse matrix, coefficient matrix
21
- theta: float, strength threshold (0 < theta <= 1):
22
* 0.25: standard choice, moderate strength
23
* 0.5: stricter strength requirement
24
* 0.1: weaker strength, more connections
25
26
Returns:
27
sparse matrix: strength matrix S where S[i,j] != 0
28
indicates strong connection from i to j
29
30
Notes:
31
- Most common strength measure for Classical AMG
32
- Works well for M-matrices and diagonally dominant systems
33
- May not be suitable for systems matrices or indefinite problems
34
"""
35
36
def symmetric_strength_of_connection(A, theta=0.0):
37
"""
38
Symmetric strength of connection measure.
39
40
Creates symmetric strength matrix by taking maximum of
41
classical strength in both directions. Suitable for
42
symmetric matrices and Smoothed Aggregation AMG.
43
44
Parameters:
45
- A: sparse matrix, coefficient matrix (preferably symmetric)
46
- theta: float, strength threshold (default 0.0)
47
48
Returns:
49
sparse matrix: symmetric strength matrix where
50
S[i,j] = S[j,i] and represents strong coupling
51
52
Notes:
53
- Default choice for Smoothed Aggregation AMG
54
- Preserves symmetry of strength pattern
55
- theta=0.0 includes all matrix connections
56
"""
57
```
58
59
**Usage Examples:**
60
61
```python
62
import pyamg
63
import numpy as np
64
65
# Classical strength for Poisson problem
66
A = pyamg.gallery.poisson((50, 50))
67
S_classical = pyamg.strength.classical_strength_of_connection(A, theta=0.25)
68
print(f"Classical SOC: {S_classical.nnz} strong connections")
69
70
# Symmetric strength for elasticity
71
A_elastic = pyamg.gallery.linear_elasticity((30, 30))
72
S_symmetric = pyamg.strength.symmetric_strength_of_connection(A_elastic)
73
print(f"Symmetric SOC: {S_symmetric.nnz} strong connections")
74
75
# Different strength thresholds
76
S_weak = pyamg.strength.classical_strength_of_connection(A, theta=0.1)
77
S_strong = pyamg.strength.classical_strength_of_connection(A, theta=0.5)
78
print(f"Weak ({S_weak.nnz}) vs Strong ({S_strong.nnz}) connections")
79
```
80
81
### Advanced Strength Measures
82
83
Sophisticated measures for challenging problems and special matrix types.
84
85
```python { .api }
86
def energy_based_strength_of_connection(A, theta=0.0, **kwargs):
87
"""
88
Energy-based strength of connection measure.
89
90
Determines strength based on energy contribution of connections
91
rather than algebraic magnitude. More robust for systems with
92
complex coupling patterns.
93
94
Parameters:
95
- A: sparse matrix, coefficient matrix
96
- theta: float, energy threshold
97
- B: array, near-nullspace vectors (optional)
98
- BtBinv: array, inverse of B^T B (optional)
99
100
Returns:
101
sparse matrix: energy-based strength matrix
102
103
Notes:
104
- Accounts for near-nullspace in strength computation
105
- More expensive than classical measures
106
- Better for elasticity and other systems problems
107
"""
108
109
def evolution_strength_of_connection(A, B=None, epsilon=4.0, k=2, proj_type='l2'):
110
"""
111
Evolution-based strength of connection measure.
112
113
Uses evolution process to determine strength based on
114
how connections affect error evolution. Most sophisticated
115
strength measure available.
116
117
Parameters:
118
- A: sparse matrix, coefficient matrix
119
- B: array, near-nullspace vectors (default: constant)
120
- epsilon: float, evolution parameter (default 4.0)
121
- k: int, number of evolution steps (default 2)
122
- proj_type: str, projection type ('l2', 'D_A')
123
124
Returns:
125
sparse matrix: evolution-based strength matrix
126
127
Notes:
128
- Most robust strength measure for difficult problems
129
- Higher computational cost than other measures
130
- Automatically adapts to problem characteristics
131
"""
132
133
def distance_strength_of_connection(A, theta=2.0):
134
"""
135
Distance-based strength of connection measure.
136
137
Determines strength based on geometric or algebraic
138
distance between degrees of freedom.
139
140
Parameters:
141
- A: sparse matrix, coefficient matrix
142
- theta: float, distance threshold
143
144
Returns:
145
sparse matrix: distance-based strength matrix
146
147
Notes:
148
- Useful when geometric information is available
149
- Can incorporate coordinate data
150
- Less common than algebraic measures
151
"""
152
```
153
154
**Usage Examples:**
155
156
```python
157
# Energy-based strength for elasticity
158
A = pyamg.gallery.linear_elasticity((25, 25))
159
B = np.ones((A.shape[0], 3)) # Rigid body modes
160
S_energy = pyamg.strength.energy_based_strength_of_connection(A, B=B)
161
162
# Evolution-based strength (most robust)
163
S_evolution = pyamg.strength.evolution_strength_of_connection(A, B=B, epsilon=4.0)
164
165
# Compare different measures
166
print(f"Energy SOC: {S_energy.nnz} connections")
167
print(f"Evolution SOC: {S_evolution.nnz} connections")
168
```
169
170
### Distance and Affinity Measures
171
172
Specialized measures for geometric and graph-based strength computation.
173
174
```python { .api }
175
def algebraic_distance(A, B=None, distance='unit', **kwargs):
176
"""
177
Compute algebraic distance between degrees of freedom.
178
179
Measures algebraic distance based on how connections
180
propagate through the matrix graph structure.
181
182
Parameters:
183
- A: sparse matrix, coefficient matrix
184
- B: array, near-nullspace vectors
185
- distance: str, distance measure:
186
* 'unit': unit distance (default)
187
* 'abs': absolute value distance
188
* 'min': minimum distance
189
- **kwargs: distance-specific parameters
190
191
Returns:
192
array: distance matrix or distance values
193
194
Notes:
195
- Fundamental component of many strength measures
196
- Used internally by other strength functions
197
- Can be used standalone for analysis
198
"""
199
200
def affinity_distance(A, B=None, distance='unit', **kwargs):
201
"""
202
Compute affinity-based distance measure.
203
204
Measures strength based on affinity (similarity) of
205
connections rather than direct algebraic relationships.
206
207
Parameters:
208
- A: sparse matrix, coefficient matrix
209
- B: array, near-nullspace vectors
210
- distance: str, affinity measure type
211
- **kwargs: affinity-specific parameters
212
213
Returns:
214
sparse matrix: affinity-based strength matrix
215
216
Notes:
217
- Useful for graph-based problems
218
- Can incorporate problem-specific similarity measures
219
- Experimental, less established than classical measures
220
"""
221
```
222
223
**Usage Examples:**
224
225
```python
226
# Algebraic distance computation
227
A = pyamg.gallery.poisson((40, 40))
228
distances = pyamg.strength.algebraic_distance(A, distance='unit')
229
230
# Affinity-based strength
231
S_affinity = pyamg.strength.affinity_distance(A)
232
```
233
234
## Strength Measure Selection
235
236
### Problem Type Guidelines
237
238
- **M-matrices, Poisson**: Classical strength (theta=0.25)
239
- **Symmetric problems**: Symmetric strength (theta=0.0)
240
- **Elasticity, systems**: Energy-based or evolution strength
241
- **General/difficult**: Evolution strength with adaptive parameters
242
- **Anisotropic**: Evolution or energy-based measures
243
244
### Parameter Tuning
245
246
```python
247
# Conservative (many connections)
248
S_conservative = pyamg.strength.classical_strength_of_connection(A, theta=0.1)
249
250
# Standard (balanced)
251
S_standard = pyamg.strength.classical_strength_of_connection(A, theta=0.25)
252
253
# Aggressive (fewer connections)
254
S_aggressive = pyamg.strength.classical_strength_of_connection(A, theta=0.5)
255
```
256
257
### Integration with Solvers
258
259
```python
260
# Use custom strength in solver construction
261
def custom_strength(A):
262
return pyamg.strength.evolution_strength_of_connection(A, epsilon=6.0)
263
264
ml = pyamg.ruge_stuben_solver(A, strength=custom_strength)
265
266
# Or pass strength parameters directly
267
ml = pyamg.smoothed_aggregation_solver(A, strength=('evolution', {'epsilon': 4.0}))
268
```
269
270
### Performance Considerations
271
272
- **Classical**: Fastest, O(nnz) complexity
273
- **Symmetric**: Fast, slight overhead for symmetrization
274
- **Energy**: Moderate cost, requires near-nullspace computation
275
- **Evolution**: Most expensive, O(k * nnz) for k evolution steps
276
- **Memory**: Evolution and energy require additional storage
277
278
### Analysis and Debugging
279
280
```python
281
# Analyze strength connectivity
282
A = pyamg.gallery.poisson((30, 30))
283
S = pyamg.strength.classical_strength_of_connection(A, theta=0.25)
284
285
# Connection statistics
286
print(f"Matrix nnz: {A.nnz}")
287
print(f"Strong connections: {S.nnz}")
288
print(f"Strength ratio: {S.nnz / A.nnz:.2f}")
289
290
# Visualize strength pattern (for small problems)
291
import matplotlib.pyplot as plt
292
plt.spy(S, markersize=1)
293
plt.title("Strength of Connection Pattern")
294
plt.show()
295
```
296
297
### Common Issues
298
299
- **Too many connections**: Increase theta, use stricter measure
300
- **Too few connections**: Decrease theta, use weaker measure
301
- **Poor coarsening**: Try evolution or energy-based measures
302
- **Slow setup**: Use simpler measures like classical or symmetric
303
- **Indefinite problems**: Avoid classical strength, use evolution-based