This page contains the Pyamg Package documentation.
Algorithms related to graphs
Compute a maximal independent vertex set for a graph
Parameters : | G : sparse matrix
algo : {‘serial’, ‘parallel’}
|
---|---|
Returns : | An array S where :
|
Notes
Diagonal entries in the G (self loops) will be ignored.
Luby’s algorithm is significantly more expensive than the greedy serial algorithm.
Compute a vertex coloring of a graph
Parameters : | G : sparse matrix
method : {string}
|
---|---|
Returns : | An array of vertex colors (integers beginning at 0) : |
Notes
Diagonal entries in the G (self loops) will be ignored.
Perform Lloyd clustering on graph with weighted edges
Parameters : | G : csr_matrix or csc_matrix
seeds : {int, array}
maxiter : int
|
---|
Notes
If G has complex values, abs(G) is used instead.
Compute the connected components of a graph
The connected components of a graph G, which is represented by a symmetric sparse matrix, are labeled with the integers 0,1,..(K-1) where K is the number of components.
Parameters : | G : symmetric matrix, preferably in sparse CSR or CSC format
|
---|---|
Returns : | components : ndarray
|
Notes
If the nonzero structure of G is not symmetric, then the result is undefined.
Examples
>>> print connected_components( [[0,1,0],[1,0,1],[0,1,0]] )
[0 0 0]
>>> print connected_components( [[0,1,0],[1,0,0],[0,0,0]] )
[0 0 1]
>>> print connected_components( [[0,0,0],[0,0,0],[0,0,0]] )
[0 1 2]
>>> print connected_components( [[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]] )
[0 0 1 1]
Generic AMG solver
Stores multigrid hierarchy and implements the multigrid cycle
The class constructs the cycling process and points to the methods for coarse grid solves. A multilevel_solver object is typically returned from a particular AMG method (see ruge_stuben_solver or smoothed_aggregation_solver for example). A call to multilevel_solver.solve() is a typical access point. The class also defines methods for constructing operator, cycle, and grid complexities.
Attributes
levels | level array | Array of level objects that contain A, R, and P. |
coarse_solver | string | String passed to coarse_grid_solver indicating the solve type |
Methods
aspreconditioner() | Create a preconditioner using this multigrid cycle |
cycle_complexity() | A measure of the cost of a single multigrid cycle. |
grid_complexity() | A measure of the rate of coarsening. |
operator_complexity() | A measure of the size of the multigrid hierarchy. |
solve() | Iteratively solves a linear system for the right hand side. |
Create a preconditioner using this multigrid cycle
Parameters : | cycle : {‘V’,’W’,’F’,’AMLI’}
|
---|---|
Returns : | precond : LinearOperator
|
See also
multilevel_solver.solve, scipy.sparse.linalg.LinearOperator
Examples
>>> from pyamg.aggregation import smoothed_aggregation_solver
>>> from pyamg.gallery import poisson
>>> from scipy.sparse.linalg import cg
>>> from scipy import rand
>>> A = poisson((100, 100), format='csr') # matrix
>>> b = rand(A.shape[0]) # random RHS
>>> ml = smoothed_aggregation_solver(A) # AMG solver
>>> M = ml.aspreconditioner(cycle='V') # preconditioner
>>> x, info = cg(A, b, tol=1e-8, maxiter=30, M=M) # solve with CG
Cycle complexity of this multigrid hierarchy for V(1,1), W(1,1), AMLI(1,1) and F(1,1) cycles when simple relaxation methods are used.
Cycle complexity is an approximate measure of the number of floating point operations (FLOPs) required to perform a single multigrid cycle relative to the cost a single smoothing operation.
Parameters : | cycle : {‘V’,’W’,’F’,’AMLI’}
|
---|---|
Returns : | cc : float
|
Notes
This is only a rough estimate of the true cycle complexity. The estimate assumes that the cost of pre and post-smoothing are (each) equal to the number of nonzeros in the matrix on that level. This assumption holds for smoothers like Jacobi and Gauss-Seidel. However, the true cycle complexity of cycle using more expensive methods, like block Gauss-Seidel will be underestimated.
Additionally, if the cycle used in practice isn’t a (1,1)-cycle, then this cost estimate will be off.
Grid complexity of this multigrid hierarchy
Stores one level of the multigrid hierarchy
All level objects will have an ‘A’ attribute referencing the matrix of that level. All levels, except for the coarsest level, will also have ‘P’ and ‘R’ attributes referencing the prolongation and restriction operators that act between each level and the next coarser level.
Notes
The functionality of this class is a struct
Attributes
A | csr_matrix | Problem matrix for Ax=b |
R | csr_matrix | Restriction matrix between levels (often R = P.T) |
P | csr_matrix | Prolongation or Interpolation matrix. |
Operator complexity of this multigrid hierarchy
Main solution call to execute multigrid cycling.
Parameters : | b : array
x0 : array
tol : float
maxiter : int
cycle : {‘V’,’W’,’F’,’AMLI’}
accel : {string, function}
callback : function
residuals : list
|
---|---|
Returns : | x : array
|
See also
Examples
>>> from numpy import ones
>>> from pyamg import ruge_stuben_solver
>>> from pyamg.gallery import poisson
>>> A = poisson((100, 100), format='csr')
>>> b = A * ones(A.shape[0])
>>> ml = ruge_stuben_solver(A, max_coarse=10)
>>> residuals = []
>>> x = ml.solve(b, tol=1e-12, residuals=residuals) # standalone solver
Return a coarse grid solver suitable for multilevel_solver
Parameters : | solver : {string, callable, tuple}
|
---|---|
Returns : | ptr : generic_solver
|
Examples
>>> from numpy import ones
>>> from scipy.sparse import spdiags
>>> from pyamg.gallery import poisson
>>> from pyamg import coarse_grid_solver
>>> A = poisson((10, 10), format='csr')
>>> b = A * ones(A.shape[0])
>>> cgs = coarse_grid_solver('lu')
>>> x = cgs(A, b)
Strength of Connection functions
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
Parameters : | A : csr_matrix
theta : float
|
---|---|
Returns : | S : csr_matrix
|
See also
Notes
References
[R1] | 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. ISBN: 0-89871-462-1 |
[R2] | Trottenberg, U., Oosterlee, C. W., Schuller, A., “Multigrid”, Academic Press, Inc., San Diego, CA, 2001. xvi+631 pp. ISBN: 0-12-701070-X |
Examples
>>> import numpy
>>> from pyamg.gallery import stencil_grid
>>> from pyamg.strength import classical_strength_of_connection
>>> n=3
>>> stencil = numpy.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)
Compute a 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 : | A : csr_matrix
theta : float
|
---|---|
Returns : | S : csr_matrix
|
See also
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.
References
[R3] | 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
>>> from pyamg.gallery import stencil_grid
>>> from pyamg.strength import symmetric_strength_of_connection
>>> n=3
>>> stencil = numpy.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)
Construct an AMG strength of connection matrix using an Evolution-based measure
Parameters : | A : {csr_matrix, bsr_matrix}
B : {array_like}
epsilon : scalar
k : integer
proj_type : {‘l2’,’D_A’}
block_flag : {boolean}
assume_const_nns : {boolean}
|
---|---|
Returns : | Atilde : {csr_matrix}
|
References
[R4] | Olson, L. N., Schroder, J., Tuminaro, R. S., “A New Perspective on Strength Measures in Algebraic Multigrid”, submitted, June, 2008. |
Examples
>>> import numpy
>>> from pyamg.gallery import stencil_grid
>>> from pyamg.strength import evolution_strength_of_connection
>>> n=3
>>> stencil = numpy.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, numpy.ones((A.shape[0],1)))
Distance based strength-of-connection
Parameters : | A : {csr_matrix}
V : {array}
relative_drop : {bool}
|
---|---|
Returns : | C : {csr_matrix}
|
Notes
theta is a drop tolerance that is applied row-wise
Examples
>>> import scipy
>>> from pyamg import smoothed_aggregation_solver
>>> from pyamg.strength import distance_strength_of_connection
>>> data = pyamg.gallery.load_example('airfoil')
>>> A = data['A'].tocsr()
>>> B = scipy.array(data['B'],dtype=float)
>>> S = distance_strength_of_connection(data['A'], data['vertices'])
>>> b = scipy.rand(data['A'].shape[0],)
>>> # Use distance strength on level 0, and symmetric on coarse levels
>>> strength = [('distance', {'V' : data['vertices']}), 'symmetric']
>>> sa = smoothed_aggregation_solver(A, B, strength=strength, max_coarse=10)
>>> x = sa.solve(b)