porepy.grids.partition module

This module contains functionality for the partitioning of grids based on various methods.

Intended support is by Cartesian indexing, and METIS-based.

Several functions require pymetis to be installed, which can be done using pip in a Python environment using

pip install pymetis

This will install metis itself in addition to the python bindings. There are other python bindings for metis as well, but pymetis has behaved well so far.

The main method in this module is partition(), which is a wrapper for all available methods.

determine_coarse_dimensions(target, fine_size)

Determine coarse partitioning for a logically Cartesian grid

The coarse partitioning of the grid is based on a target number of coarse cells.

The target size in general will not be a product of the possible grid dimensions (it may be a prime, or it may be outside the bounds [1, fine_size]). For concreteness, we seek to have roughly the same number of cells in each direction (given by the Nd-root of the target). If this requires more coarse cells in a dimension than there are fine cells there, the coarse size is set equal to the fine, and the remaining cells are distributed to the other dimensions.

Parameters

• target (int) – Target number of coarse cells.

• fine_size (ndarray) – Number of fine-scale cells in each dimension

Raises

ValueError – If the while-loop runs more iterations than the number of dimensions. This should not happen, in practice it means there is bug.

Returns

Coarse dimension sizes.

Return type

ndarray

extract_subgrid(g, c, sort=True, faces=False, is_planar=True)

Extract a subgrid based on cell/face indices.

For simplicity the cell/face indices will be sorted before the subgrid is extracted.

If the parent grid has geometry attributes (cell centers etc.), these are copied to the child.

No checks are done on whether the cells/faces form a connected area. The method should work in theory for non-connected cells, the user will then have to decide what to do with the resulting grid. This option has however not been tested.

Parameters

• g (Grid) – Grid object, parent.

• c (ndarray) – Indices of cells to be extracted.

• sort (bool) –

  default=True

  If True, c is sorted.

• faces (bool) –

  default=False

  If True, c is interpreted as faces, and the extracted grid will be a lower dimensional grid defined by the these faces.

• is_planar (bool) –

  default=True

  Only used when extracting faces from a 3D grid.

  If True, the faces must be planar. Set to False to use this function for extracting a non-planar 2D grid, but use at own risk.

Raises

IndexError – If index is as boolean and does not match the array size.

Returns

A 3-tuple containing

Grid:

Extracted subgrid. Will share (note, not copy) geometric fields with the parent grid. Also has an additional field parent_cell_ind giving correspondence between parent and child cells.

ndarray:

Index of the extracted faces, ordered so that element i is the global index of face i in the subgrid.

ndarray:

Index of the extracted nodes, ordered so that element i is the global index of node i in the subgrid.

Return type

tuple[porepy.grids.grid.Grid, numpy.ndarray, numpy.ndarray]

grid_is_connected(g, cell_ind=None)

Check if a grid is fully connected, as defined by its cell_connection_map().

The function is intended used in one of two ways:

1. To test if a subgrid will be connected before it is extracted. In this case, the cells to be tested is specified by cell_ind.

2. To check if an existing grid is composed of a single component. In this case, all cells are should be included in the analyzis.

Examples

>>> import numpy as np
>>> import porepy as pp
>>> import porepy.grids.partition as part
>>> g = pp.CartGrid(np.array([2, 2]))
>>> p = np.array([0, 1])
>>> is_con, l = part.grid_is_connected(g, p)
>>> is_con
True

>>> import numpy as np
>>> import porepy as pp
>>> import porepy.grids.partition as part
>>> g = pp.CartGrid(np.array([2, 2]))
>>> p = np.array([0, 3])
>>> is_con, l = part.grid_is_connected(g, p)
>>> is_con
False

Parameters

• g (Grid) – Grid to be tested. Only its cell_faces map is used.

• cell_ind (Optional[ndarray]) –

  default=None

  Index of cells to be included when looking for connections. Defaults to all cells in the grid.

Returns

A 2-tuple containing

bool:

True, if the grid is connected.

list:

Each list item contains an array with cell indices of a connected component.

Return type

tuple[bool, list[numpy.ndarray]]

overlap(g, cell_ind, num_layers, criterion='node')

Finds an extended set of cells that forms an overlap.

From a set of cell indices, this function finds an extended set of cells that forms an overlap (in the domain decomposition sense).

The cell set is increased by including all cells that share at least one node with the existing set. When multiple layers are asked for, this process is repeated.

The definition of neighborhood is specified by criterion.

Example

>>> import numpy as np
>>> import porepy as pp
>>> import porepy.grids.partition as part
>>> g = pp.CartGrid([5, 5])
>>> ci = np.array([0, 1, 5, 6])
>>> part.overlap(g, ci, 1)
array([ 0,  1,  2,  5,  6,  7, 10, 11, 12])

Parameters

• g (Grid) – The grid; the cell-node relation will be used to extend the cell set.

• cell_ind (ndarray) – Cell indices of the initial cell set.

• num_layers (int) – Number of overlap layers.

• criterion (str) –

  default='node'

  Which definition of neighborhood to apply:

  • 'face': Each layer will add cells that share a face with the active face set.

  • 'node': Each layer will add cells sharing a vertex with the active set.

Returns

Indices of the extended cell set.

Return type

ndarray

partition(g, num_coarse)

Wrapper for partition methods that tries to apply the best possible algorithm.

The method will first try to use METIS; if this is not available (or fails otherwise), the partition_structured will be applied if the grid is Cartesian. The last resort is partitioning based on coordinates.

See also

• partition_metis(),

• partition_structured() and

• partition_coordinates() for further details.

Parameters

• g (Grid) – Grid to be partitioned.

• num_coarse (int) – Target number of coarse cells.

Returns

Partition vector with shape=(g.num_cells,) containing numbers indicating which cell belongs to which partitions.

Return type

ndarray

partition_coordinates(g, num_coarse, check_connectivity=True)

Brute force partitioning of a grid based on cell center coordinates.

The intention at the time of implementation is to provide a partitioning for general grids that does not rely on METIS being available. However, if METIS is available, partition_metis() should be preferred.

The idea is to divide the domain into a coarse Cartesian grid, and then assign a coarse partitioning based on the cell center coordinates.

It is not clear that this will create a connected coarse partitioning for all grid cells (it may be possible to construct pathological examples, probably involving non-convex cells). We optionally check for connectivity and raise an error if this is not fulfilled.

The method assumes that the cells have a center, that is, compute_geometry() has been called. If g does not have a field cell_centers, compute_geometry() will be called.

Parameters

• g (Grid) – Grid to be partitioned.

• num_coarse (int) – Target number of coarse cells. The real number of coarse cells will be close, but not necessarily equal.

• check_connectivity (bool) –

  default=True

  Check if the partitioning form connected coarse grids. Defaults to True.

Returns

Partition vector with shape=(g.num_cells,) containing numbers indicating which cell belongs to which partitions.

Raises

ValueError – If the partitioning is found to not form connected subgrids.

Return type

ndarray

partition_grid(g, ind)

Partition a grid into multiple subgrids based on an index set.

Note

No tests are made on whether the resulting grids are connected.

Example

>>> import numpy as np
>>> import porepy as pp
>>> import porepy.grids.partition as part
>>> g = pp.CartGrid(np.array([10, 10]))
>>> p = part.partition_structured(g, num_part=4)
>>> subg, face_map, node_map = part.partition_grid(g, p)

Parameters

• g (Grid) – Global grid to be partitioned.

• ind (ndarray) – Partition vector, one per cell. Should be 0-offset.

Returns

A 3-tuple containing

list:

List of grids, each element representing a grid.

list:

Each element contains the global indices of the local faces.

list:

Each element contains the global indices of the local nodes.

Return type

tuple[list[porepy.grids.grid.Grid], list[numpy.ndarray], list[numpy.ndarray]]

partition_metis(g, num_part)

Partition a grid using metis.

Parameters

• g (Grid) – Grid to be partitioned. The attribute cell_faces is required.

• num_part (int) – Number of partitions.

Returns

Partition vector with shape=(g.num_cells,) containing numbers [0, num_part) indicating which cell belongs to which partition.

Return type

ndarray

partition_structured(g, num_part=1, coarse_dims=None)

Define a partitioning of a grid based on logical Cartesian indexing.

The grid should have the attribute cart_dims, describing the Cartesian dimensions of the grid.

The coarse grid can be specified either by its Cartesian dimensions coarse_dims, or by its total number of partitions num_part. In the latter case, a partitioning will be inferred from the fine-scale Cartesian dimensions, in a way that gives roughly the same number of cells in each direction.

Parameters

• g (TensorGrid) – Grid to be partitioned. The attribute cell_face is required.

• num_part (int) –

  default=1

  Number of partitions.

• coarse_dims (Optional[ndarray]) –

  default=None

  Cartesian dimensions of the coarse grids.

Raises

ValueError – If both coarse_dims and num_part are None.

Returns

Partition vector with shape=(g.num_cells,) containing numbers [0, num_part) indicating which cell belongs to which partition.

Return type

ndarray