pyamg.strength#
Strength of Connection functions.
 Requirements for the strength matrix C are:
Nonzero diagonal whenever A has a nonzero diagonal
Nonnegative 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 Strength Measure. 

Algebraic Distance Strength Measure. 

Classical strength of connection measure. 

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

Distance based strengthofconnection. 

Energy Strength Measure. 

Evolution Strength Measure. 

ode_strength_of_connection is deprecated! 

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

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
pnorm 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 offdiagonal 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 blockwise
 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 nonblockwise computations. For blockwise:
'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 Mmatrices. 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 strengthofconnection.
 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 rowwise
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 energybased measure.
 Parameters:
 Asparsematrix
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 weightedJacobi in order to approximate the matrix inverse. A normalized change of energy is then used to define pointwise strength of connection values. Specifically, let v be the approximation to the ith 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 purepython implementation for experimental purposes, only.
See [2006BrBrMaMaMc] for more details.
References
[2006BrBrMaMaMc]Brannick, Brezina, MacLachlan, Manteuffel, McCormick. “An EnergyBased AMG Coarsening Strategy”, Numerical Linear Algebra with Applications, vol. 13, pp. 133148, 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 Evolutionbased 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 weightedJacobi
 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 offdiagonal 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.
See also
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 blocktype 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
[1996bVaMaBr]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)