# pyamg.strength#

Strength of Connection functions.

Requirements for the strength matrix C are:
1. Nonzero diagonal whenever A has a nonzero diagonal

2. Non-negative entries (float or bool) in [0,1]

3. Large entries denoting stronger connections

4. C denotes nodal connections, i.e., if A is an nxn BSR matrix with row block size of m, then C is (n/m) x (n/m)

Functions

 `affinity_distance`(A[, alpha, R, k, epsilon]) Affinity Distance Strength Measure. `algebraic_distance`(A[, alpha, R, k, epsilon, p]) Algebraic Distance Strength Measure. `classical_strength_of_connection`(A[, theta, ...]) Classical strength of connection measure. `distance_measure_common`(A, func, alpha, R, ...) Create strength of connection matrixfrom a function applied to relaxation vectors. `distance_strength_of_connection`(A, V[, ...]) Distance based strength-of-connection. Energy Strength Measure. `evolution_strength_of_connection`(A[, B, ...]) Evolution Strength Measure. `ode_strength_of_connection`(A[, B, epsilon, ...]) ode_strength_of_connection is deprecated! `relaxation_vectors`(A, R, k, alpha) Generate test vectors by relaxing on Ax=0 for some random vectors x. `symmetric_strength_of_connection`(A[, theta]) Symmetric Strength Measure.
pyamg.strength.affinity_distance(A, alpha=0.5, R=5, k=20, epsilon=4.0)[source]#

Affinity Distance Strength Measure.

Parameters:
Acsr_matrix

Sparse NxN matrix

alphascalar

Weight for Jacobi

Rinteger

Number of random vectors

kinteger

Number of relaxation passes

epsilonscalar

Drop tolerance

Returns:
Ccsr_matrix

Sparse matrix of strength values

Notes

No unit testing yet.

Does not handle BSR matrices yet.

See [LiBr] for more details.

References

[LiBr]

Oren E. Livne and Achi Brandt, “Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver”

pyamg.strength.algebraic_distance(A, alpha=0.5, R=5, k=20, epsilon=2.0, p=2)[source]#

Algebraic Distance Strength Measure.

Parameters:
Acsr_matrix

Sparse NxN matrix

alphascalar

Weight for Jacobi

Rinteger

Number of random vectors

kinteger

Number of relaxation passes

epsilonscalar

Drop tolerance

pscalar or inf

p-norm of the measure

Returns:
Ccsr_matrix

Sparse matrix of strength values

Notes

No unit testing yet.

Does not handle BSR matrices yet.

See [SaSaSc] for more details.

References

[SaSaSc]

Ilya Safro, Peter Sanders, and Christian Schulz, “Advanced Coarsening Schemes for Graph Partitioning”

pyamg.strength.classical_strength_of_connection(A, theta=0.1, block=True, norm='abs')[source]#

Classical strength of connection measure.

Return a strength of connection matrix using the classical AMG measure An off-diagonal entry A[i,j] is a strong connection iff:

```|A[i,j]| >= theta * max(|A[i,k]|), where k != i     (norm='abs')
-A[i,j]  >= theta * max(-A[i,k]),  where k != i     (norm='min')
```
Parameters:
Acsr_matrix or bsr_matrix

Square, sparse matrix in CSR or BSR format

thetafloat

Threshold parameter in [0,1]

blockbool, default True

Compute strength of connection block-wise

norm‘string’, default ‘abs’

Measure used in computing the strength:

```'abs' : |C[i,j]| >= theta * max(|C[i,k]|), where k != i
'min' : -C[i,j]  >= theta * max(-C[i,k]),  where k != i
```

where C = A for non-block-wise computations. For block-wise:

```'abs'  : C[i, j] is the maximum absolute value in block A[i, j]
'min'  : C[i, j] is the minimum (negative) value in block A[i, j]
'fro'  : C[i, j] is the Frobenius norm of block A[i, j]
```
Returns:
Scsr_matrix

Matrix graph defining strong connections. S[i,j] ~ 1.0 if vertex i is strongly influenced by vertex j, or block i is strongly influenced by block j if block=True.

`symmetric_strength_of_connection`

symmetric measure used in SA

`evolution_strength_of_connection`

relaxation based strength measure

Notes

• A symmetric A does not necessarily yield a symmetric strength matrix S

• Calls C++ function classical_strength_of_connection

• The version as implemented is designed for M-matrices. Trottenberg et al. use max A[i,k] over all negative entries, which is the same. A positive edge weight never indicates a strong connection.

References

Briggs, W. L., Henson, V. E., McCormick, S. F., “A multigrid tutorial”, Second edition. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. xii+193 pp.

Trottenberg, U., Oosterlee, C. W., Schuller, A., “Multigrid”, Academic Press, Inc., San Diego, CA, 2001. xvi+631 pp.

Examples

```>>> import numpy as np
>>> from pyamg.gallery import stencil_grid
>>> from pyamg.strength import classical_strength_of_connection
>>> n=3
>>> stencil = np.array([[-1.0,-1.0,-1.0],
...                        [-1.0, 8.0,-1.0],
...                        [-1.0,-1.0,-1.0]])
>>> A = stencil_grid(stencil, (n,n), format='csr')
>>> S = classical_strength_of_connection(A, 0.0)
```
pyamg.strength.distance_measure_common(A, func, alpha, R, k, epsilon)[source]#

Create strength of connection matrixfrom a function applied to relaxation vectors.

pyamg.strength.distance_strength_of_connection(A, V, theta=2.0, relative_drop=True)[source]#

Distance based strength-of-connection.

Parameters:
Acsr_matrix or bsr_matrix

Square, sparse matrix in CSR or BSR format

Varray

Coordinates of the vertices of the graph of A

relative_dropbool

If false, then a connection must be within a distance of theta from a point to be strongly connected. If true, then the closest connection is always strong, and other points must be within theta times the smallest distance to be strong

Returns:
Ccsr_matrix

C(i,j) = distance(point_i, point_j) Strength of connection matrix where strength values are distances, i.e. the smaller the value, the stronger the connection. Sparsity pattern of C is copied from A.

Notes

• theta is a drop tolerance that is applied row-wise

• If a BSR matrix given, then the return matrix is still CSR. The strength is given between super nodes based on the BSR block size.

Examples

```>>> from pyamg.gallery import load_example
>>> from pyamg.strength import distance_strength_of_connection
>>> A = data['A'].tocsr()
>>> S = distance_strength_of_connection(data['A'], data['vertices'])
```
pyamg.strength.energy_based_strength_of_connection(A, theta=0.0, k=2)[source]#

Energy Strength Measure.

Compute a strength of connection matrix using an energy-based measure.

Parameters:
Asparse-matrix

matrix from which to generate strength of connection information

thetafloat

Threshold parameter in [0,1]

kint

Number of relaxation steps used to generate strength information

Returns:
Scsr_matrix

Matrix graph defining strong connections. The sparsity pattern of S matches that of A. For BSR matrices, S is a reduced strength of connection matrix that describes connections between supernodes.

Notes

This method relaxes with weighted-Jacobi in order to approximate the matrix inverse. A normalized change of energy is then used to define point-wise strength of connection values. Specifically, let v be the approximation to the i-th column of the inverse, then

(S_ij)^2 = <v_j, v_j>_A / <v, v>_A,

where v_j = v, such that entry j in v has been zeroed out. As is common, larger values imply a stronger connection.

Current implementation is a very slow pure-python implementation for experimental purposes, only.

See [2006BrBrMaMaMc] for more details.

References

Brannick, Brezina, MacLachlan, Manteuffel, McCormick. “An Energy-Based AMG Coarsening Strategy”, Numerical Linear Algebra with Applications, vol. 13, pp. 133-148, 2006.

Examples

```>>> import numpy as np
>>> from pyamg.gallery import stencil_grid
>>> from pyamg.strength import energy_based_strength_of_connection
>>> n=3
>>> stencil =  np.array([[-1.0,-1.0,-1.0],
...                      [-1.0, 8.0,-1.0],
...                      [-1.0,-1.0,-1.0]])
>>> A = stencil_grid(stencil, (n,n), format='csr')
>>> S = energy_based_strength_of_connection(A, 0.0)
```
pyamg.strength.evolution_strength_of_connection(A, B=None, epsilon=4.0, k=2, proj_type='l2', block_flag=False, symmetrize_measure=True)[source]#

Evolution Strength Measure.

Construct strength of connection matrix using an Evolution-based measure

Parameters:
Acsr_matrix, bsr_matrix

Sparse NxN matrix

Bstring, array

If B=None, then the near nullspace vector used is all ones. If B is an (NxK) array, then B is taken to be the near nullspace vectors.

epsilonscalar

Drop tolerance

kinteger

ODE num time steps, step size is assumed to be 1/rho(DinvA)

proj_type{‘l2’,’D_A’}

Define norm for constrained min prob, i.e. define projection

block_flagboolean

If True, use a block D inverse as preconditioner for A during weighted-Jacobi

Returns:
Atildecsr_matrix

Sparse matrix of strength values

See [2008OlScTu] for more details.

References

Olson, L. N., Schroder, J., Tuminaro, R. S., “A New Perspective on Strength Measures in Algebraic Multigrid”, submitted, June, 2008.

Examples

```>>> import numpy as np
>>> from pyamg.gallery import stencil_grid
>>> from pyamg.strength import evolution_strength_of_connection
>>> n=3
>>> stencil =  np.array([[-1.0,-1.0,-1.0],
...                        [-1.0, 8.0,-1.0],
...                        [-1.0,-1.0,-1.0]])
>>> A = stencil_grid(stencil, (n,n), format='csr')
>>> S = evolution_strength_of_connection(A,  np.ones((A.shape,1)))
```
pyamg.strength.ode_strength_of_connection(A, B=None, epsilon=4.0, k=2, proj_type='l2', block_flag=False, symmetrize_measure=True)[source]#

ode_strength_of_connection is deprecated!

pyamg.strength.relaxation_vectors(A, R, k, alpha)[source]#

Generate test vectors by relaxing on Ax=0 for some random vectors x.

Parameters:
Acsr_matrix

Sparse NxN matrix

alphascalar

Weight for Jacobi

Rinteger

Number of random vectors

kinteger

Number of relaxation passes

Returns:
xarray

Dense array N x k array of relaxation vectors

pyamg.strength.symmetric_strength_of_connection(A, theta=0)[source]#

Symmetric Strength Measure.

Compute strength of connection matrix using the standard symmetric measure

An off-diagonal connection A[i,j] is strong iff:

```abs(A[i,j]) >= theta * sqrt( abs(A[i,i]) * abs(A[j,j]) )
```
Parameters:
Acsr_matrix

Matrix graph defined in sparse format. Entry A[i,j] describes the strength of edge [i,j]

thetafloat

Threshold parameter (positive).

Returns:
Scsr_matrix

Matrix graph defining strong connections. S[i,j]=1 if vertex i is strongly influenced by vertex j.

`symmetric_strength_of_connection`

symmetric measure used in SA

`evolution_strength_of_connection`

relaxation based strength measure

Notes

• For vector problems, standard strength measures may produce undesirable aggregates. A “block approach” from Vanek et al. is used to replace vertex comparisons with block-type comparisons. A connection between nodes i and j in the block case is strong if:

```||AB[i,j]|| >= theta * sqrt( ||AB[i,i]||*||AB[j,j]|| ) where AB[k,l]
```

is the matrix block (degrees of freedom) associated with nodes k and l and ||.|| is a matrix norm, such a Frobenius.

• See [1996bVaMaBr] for more details.

References

Vanek, P. and Mandel, J. and Brezina, M., “Algebraic Multigrid by Smoothed Aggregation for Second and Fourth Order Elliptic Problems”, Computing, vol. 56, no. 3, pp. 179–196, 1996. http://citeseer.ist.psu.edu/vanek96algebraic.html

Examples

```>>> import numpy as np
>>> from pyamg.gallery import stencil_grid
>>> from pyamg.strength import symmetric_strength_of_connection
>>> n=3
>>> stencil = np.array([[-1.0,-1.0,-1.0],
...                        [-1.0, 8.0,-1.0],
...                        [-1.0,-1.0,-1.0]])
>>> A = stencil_grid(stencil, (n,n), format='csr')
>>> S = symmetric_strength_of_connection(A, 0.0)
```