pyamg.strength#

Strength of Connection functions.

Requirements for the strength matrix C are:

Nonzero diagonal whenever A has a nonzero diagonal
Non-negative entries (float or bool) in [0,1]
Large entries denoting stronger connections
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_based_strength_of_connection`(A[, ...])	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.

See also

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.
See [2000BrHeMc] and [2001bTrOoSc]

References

[2000BrHeMc]

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.

[2001bTrOoSc]

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
>>> data = load_example('airfoil')
>>> 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

[2006BrBrMaMaMc]

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

[2008OlScTu]

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[0],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!

Use evolution_strength_of_connection instead (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.