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_based_strength_of_connection(A[, ...])

Energy Strength Measure.

evolution_strength_of_connection(A[, B, ...])

Evolution Strength Measure.

ode_strength_of_connection(A[, B, epsilon, ...])

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

thetafloat

Drop tolerance (distance)

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

symmetrize_measureboolean

Symmetrize the strength as (A + A.T) / 2

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]#

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.

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 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

[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)