morphogen.homogenization.amg

Smoothed-aggregation algebraic multigrid (Vanek, Mandel & Brezina 1996).

A preconditioner of symmetric positive definite systems such as the stiffness matrices of the finite element problems. The hierarchy follows the classical recipe (also that of pyamg’s smoothed_aggregation_solver):

  • aggregates of unknowns from the graph of the matrix: an unknown with its neighbours (pass 1), then the remaining unknowns joined to a neighbouring aggregate (pass 2) or grouped together (pass 3);

  • tentative prolongator: on each aggregate, an orthonormal basis of the near-null modes (rigid-body motions in elasticity, constants in conduction), whose coefficients are the near-null modes of the coarse level;

  • prolongator smoothed by one damped Jacobi step, P = (I - 4/3 D^-1 A / rho) T;

  • Galerkin coarse matrices P^T A P, down to a few hundred unknowns, solved by a pseudo-inverse.

One V-cycle with a forward Gauss-Seidel sweep before the coarse correction and a backward sweep after it is a symmetric preconditioner for conjugate gradients.

On large matrices the sweeps and the products run on several threads (Smoother, product()): the unknowns are coloured so that no two of a colour are coupled, and those of a colour are relaxed together — a Gauss-Seidel sweep in the order of the colours, the same for any number of threads, on a copy of the matrix whose rows are sorted by colour (the rows of a colour scattered through the matrix would be read no faster by four threads than all of them in their order by one); the rows of a product are shared between the threads, each summed as SciPy sums it. Where the unknowns are components of the displacements of the nodes of a mesh, the colours are those of the nodes and the copy holds the 3 x 3 blocks of their couplings: one column index for nine values, and the three components of a node read together.

morphogen.homogenization.amg.THREADED = 50000

starting the threads of the compiled loop would cost more than they bring

Type:

Matrices with fewer stored values than this are multiplied on one thread

morphogen.homogenization.amg.COLOURED = 200000

Matrices with fewer stored values than this are relaxed in the order of their unknowns on one thread (a sweep in the order of the colours starts the threads once per colour)

morphogen.homogenization.amg.gauss_seidel(indptr, indices, data, x, b, forward)[source]

One Gauss-Seidel sweep on A x = b (CSR), in place, forward or backward.

morphogen.homogenization.amg.dense_product(matrix: ndarray, x: ndarray) → ndarray[source]

M x of a dense matrix and a vector on the threads of the compiled kernels. The product of BLAS (M @ x) runs on its own threads, which then stay busy for a tenth of a second (OpenBLAS: they wait for the next product) and take the cores of the kernels that follow: a sweep or a product several times slower, at each iteration where the coarsest level of a multigrid cycle is such a product.

morphogen.homogenization.amg.product(matrix: csr_matrix, x: ndarray) → ndarray[source]

A x of a CSR matrix and a vector: on several threads for a large matrix (the product of SciPy runs on one), with the same result to the bit.

class morphogen.homogenization.amg.NodeBlocks(matrix: csr_matrix, dofs: ndarray)[source]

Bases: object

A square matrix whose unknowns are components of the displacements of the nodes of a mesh, by the 3 x 3 blocks of the couplings of its nodes, in double precision (block CSR over the nodes that have an unknown: indptr, indices, sorted; data, nine values per block, row by row). It is the form that the products of the Krylov iterations read (product(): one column index for nine values, the three components of a neighbour read together; the same product to the bit as that of the stored values taken in the order of their columns), and from which the sweeps take their copy (Smoother).

dofs: the degree of freedom 3 node + component of each unknown, in increasing order. A component that is not an unknown (one that a condition holds) is an empty row and column of its block: the blocks have size rows, the unknown i at the row slot[i].

refresh() takes the values of another matrix of the same pattern — the tangent of the next Newton iteration of a loading path — at their places in the blocks, found once.

has_sorted_indices = True

the rows of the blocks are sorted)

Type:

(as a SciPy matrix

classmethod of(matrix, dofs) → NodeBlocks | None[source]

The blocks of a matrix, or none where they would not serve: a small matrix (THREADED), another format or precision, unknowns that are not in the order of their degrees of freedom.

product(x: ndarray) → ndarray[source]

A x, on several threads.

refresh(matrix: csr_matrix) → bool[source]

Takes the values of another matrix of the same unknowns, whose stored values all have a block here; returns false, and leaves the blocks as they are, for a matrix with other stored values. The places of the stored values are found once for the matrices that share the arrays of their pattern (which are kept, and must not be changed in place).

class morphogen.homogenization.amg.Smoother(matrix: csr_matrix, dofs: ndarray | None = None, blocks: NodeBlocks | None = None)[source]

Bases: object

Gauss-Seidel sweeps on a CSR matrix: in the order of the unknowns on one thread for a small matrix; for a large one (COLOURED, fewer than 2^31 unknowns), in the order of the colours of its unknowns (those of the graph of its couplings, _graph(): no stored value couples two unknowns of a colour, on either side of the diagonal), those of a colour relaxed in parallel, on a copy of the matrix sorted by colour (coloured). The forward and the backward sweeps are the adjoints of each other in both cases, and the result does not depend on the number of threads.

With colours, sorted(), start(), residual(), relax() and unsorted() work on vectors in the order of the colours (a multigrid cycle then sorts its right-hand side once, and its solution back once): size values, the unknown i at the place place[i].

dofs: the degree of freedom 3 node + component of each unknown, for unknowns that are components of the displacements of the nodes of a mesh, in increasing order. The colours are then those of the nodes (a third of the colours: no stored value couples two nodes of a colour), and the copy holds the 3 x 3 blocks of the couplings of the nodes (block is 3): the sweep is the Gauss-Seidel sweep in the order of the colours of the nodes, the three components of a node one after the other. The vectors in the order of the colours have three places per node; the place of a component that is not an unknown (a held one) stays zero. blocks: the blocks of the matrix, where they have been made already (NodeBlocks); refresh() then gives the sweeps the values that these blocks have taken since (the tangent of another Newton iteration: the same colours, the same places).

refresh(blocks: NodeBlocks) → bool[source]

The sweeps of the values that the blocks of the matrix have now (those that the copy of the sweeps was taken from: false otherwise, and for sweeps that do not work by nodes).

sorted(v: ndarray) → ndarray[source]

A vector in the order of the colours.

unsorted(v: ndarray) → ndarray[source]

A vector of the order of the colours, in the order of the unknowns.

start(b: ndarray) → ndarray[source]

The forward sweep from zero (vectors in the order of the colours).

residual(x: ndarray) → ndarray[source]

b - A x for the x that start() returns (in the order of the colours): the part of the matrix above the diagonal only.

relax(x: ndarray, b: ndarray, forward: bool) → None[source]

A sweep on vectors in the order of the colours, in place.

sweep(x: ndarray, b: ndarray, forward: bool) → None[source]

A sweep on vectors in the order of the unknowns, in place.

class morphogen.homogenization.amg.SmoothedAggregation(matrix, candidates=None, *, max_coarse: int = 500, max_levels: int = 20, dofs=None, blocks=None)[source]

Bases: object

Smoothed-aggregation hierarchy of a symmetric positive (semi-)definite matrix.

candidates (n x k) are the near-null modes (default: constants). Calling the object applies one V-cycle from a zero initial guess. dofs: the degree of freedom 3 node + component of each unknown, for unknowns that are components of the nodes of a mesh (the sweeps of the first level then work by nodes, see Smoother); blocks: the blocks of the matrix, where they have been made already (NodeBlocks; refresh() then gives the sweeps of the first level the values that they have taken since).

refresh(blocks: NodeBlocks) → bool[source]

The sweeps of the first level for the values that the blocks of the matrix have now (see Smoother.refresh()); the interpolations and the coarser levels are kept. The cycle stays a symmetric positive definite preconditioner: its coarse correction adds a positive term to the symmetric sweeps of the matrix as it is.

operator_complexity() → float[source]