# This Source Code Form is subject to the terms of the Mozilla Public
# License, v. 2.0. If a copy of the MPL was not distributed with this
# file, You can obtain one at https://mozilla.org/MPL/2.0/.
from __future__ import annotations
import itertools
import math
import operator
from collections.abc import Sequence
from dataclasses import dataclass
from typing import Literal, Optional
import numpy as np
import numpy.typing as npt
import scipy.sparse as ssp
from sisl import SparseCSR
from sisl._array import array_arange
from sisl._core.sparse_geometry import _SparseGeometry
from sisl._internal import set_module
from .permute import _reduce_bandwidth, btd_blocks, csr_graph
__all__ = [
"BlockArrayIndexer",
"BlockArray",
"PermuteBTD",
"btd_partition",
"downfold_partition",
]
@set_module("sisl_toolbox.btd")
@dataclass
class PermuteBTD:
"""Permutation table and block sizes of a block-tridiagonal matrix
Parameters
----------
permute :
the permutation table, ``permute[new] = old``.
If `blocks` is not passed, this should be a sequence of the permutation
indices for each block (e.g. ``np.split(permute, np.cumsum(blocks)[:-1])``),
the permutation table is then their concatenation, and the block sizes
are their lengths.
blocks :
the block sizes, ``blocks.sum() == len(permute)``
Examples
--------
The two forms are equivalent:
>>> PermuteBTD([2, 0, 1, 3], [1, 3])
>>> PermuteBTD([[2], [0, 1, 3]])
"""
permute: np.ndarray
blocks: Optional[np.ndarray] = None
def __post_init__(self):
if self.blocks is None:
permute = [np.asarray(p) for p in self.permute]
if len(permute) == 0 or any(p.ndim != 1 for p in permute):
raise ValueError(
f"{self.__class__.__name__} permute must be a non-empty "
"sequence of 1D arrays when blocks is not passed"
)
self.blocks = np.array([len(p) for p in permute])
self.permute = np.concatenate(permute)
self.permute = np.asarray(self.permute)
self.blocks = np.asarray(self.blocks)
if self.permute.ndim != 1 or self.blocks.ndim != 1:
raise ValueError(
f"{self.__class__.__name__} permute and blocks must be 1D arrays"
)
if self.blocks.sum() != len(self.permute):
raise ValueError(
f"{self.__class__.__name__} blocks must sum to the length of permute "
f"({self.blocks.sum()} != {len(self.permute)})"
)
def _graph(
csr: SparseCSR | _SparseGeometry | ssp.sparray,
dense: Optional[Sequence[npt.ArrayLike]] = None,
) -> ssp.csr_array:
"""Symmetric graph of `csr` (without the diagonal), with `dense` blocks added
Each array in `dense` are rows that are fully coupled (a clique).
"""
if isinstance(csr, _SparseGeometry):
csr = csr._csr
ptr, col = csr_graph(csr)
n = len(ptr) - 1
graph = ssp.csr_array((np.ones(len(col), dtype=np.int8), col, ptr), shape=(n, n))
return _add_dense(graph, dense)
def _add_dense(
graph: ssp.csr_array, dense: Optional[Sequence[npt.ArrayLike]] = None
) -> ssp.csr_array:
"""Add the fully coupled rows (cliques) in `dense` to `graph` (without the diagonal)"""
if dense:
n = graph.shape[0]
rows = []
cols = []
for idx in dense:
idx = np.unique(np.asarray(idx).ravel())
rows.append(np.repeat(idx, len(idx)))
cols.append(np.tile(idx, len(idx)))
rows = np.concatenate(rows)
cols = np.concatenate(cols)
# remove the diagonal
off = rows != cols
rows, cols = rows[off], cols[off]
graph = graph + ssp.csr_array(
(np.ones(len(rows), dtype=np.int8), (rows, cols)), shape=(n, n)
)
# only the pattern is used
graph.data[:] = 1
graph = graph.tocsr()
graph.sort_indices()
return graph
def _subgraph(graph: ssp.csr_array, idx: np.ndarray) -> ssp.csr_array:
"""The graph of the nodes `idx` (in that order)"""
graph = graph[idx][:, idx].tocsr()
graph.sort_indices()
return graph
def _graph_ptr_col(graph: ssp.csr_array) -> tuple[np.ndarray, np.ndarray]:
"""``(ptr, col)`` arrays of `graph` as required by the `permute` routines"""
return graph.indptr, graph.indices
def _btd_memory(blocks: npt.ArrayLike, dtype: npt.DTypeLike) -> float:
"""Return memory utilization in MB for the BTD matrix"""
bprev = 0
els = 0
for b in blocks:
els += bprev * b * 2 + b**2
# Extend to bytes
el2MB = np.dtype(dtype).itemsize / 1024**2
return els * el2MB
@set_module("sisl_toolbox.btd")
def btd_partition(
csr: SparseCSR | _SparseGeometry,
method: str = "gps",
cost: str = "speed",
refine: bool = True,
dense: Optional[Sequence[npt.ArrayLike]] = None,
**kwargs,
) -> PermuteBTD:
"""Permutation table and block sizes of the block-tridiagonal matrix of minimal cost
The permutation table reduces the bandwidth of `csr` (see
`~sisl_toolbox.btd.permute.reduce_bandwidth`), and the permuted matrix is partitioned
into the block-tridiagonal matrix that minimizes the `cost` model,
see `~sisl_toolbox.btd.permute.btd_blocks`.
The indices within each block are sorted, which improves memory access
when assembling and post-processing the blocks.
Parameters
----------
csr :
the sparse matrix, columns may extend into supercells.
For a sparse geometry object (e.g. `~sisl.Hamiltonian`) its sparse
pattern is used.
The rows are the nodes of the partitioning, i.e. use the atomic
sparse pattern (``H.toSparseAtom()``) to partition atoms, and ``H``
to partition orbitals.
method :
the bandwidth reduction method, see `~sisl_toolbox.btd.permute.reduce_bandwidth`
cost : {"speed", "memory", "speed-diagonal"}
the cost model of the block-tridiagonal matrix, see `~sisl_toolbox.btd.permute.btd_blocks`
refine :
refine the permutation table, see `~sisl_toolbox.btd.permute.reduce_bandwidth`
dense :
rows of `csr` that are fully coupled, one array per dense block.
E.g. the nodes (atoms or orbitals) of an electrode self-energy.
The dense blocks are added to the graph, so each dense block is
guaranteed to span at most 2 neighboring blocks.
**kwargs :
passed to the routine of `method`
Returns
-------
PermuteBTD : holding both the block-sizes and the permutation table.
"""
ptr, col = _graph_ptr_col(_graph(csr, dense))
perm = _reduce_bandwidth(ptr, col, method, refine, False, **kwargs)
blocks = btd_blocks(ptr, col, perm, cost)
# sorting within a block retains the block-tridiagonal structure
# but speeds up memory access by limiting permutation.
perm = perm[np.lexsort((perm, np.repeat(np.arange(len(blocks)), blocks)))]
return PermuteBTD(perm, blocks)
def _btd_blocks_sub(
csr: SparseCSR | _SparseGeometry,
permute: npt.ArrayLike,
cost: str = "speed",
dense: Optional[Sequence[npt.ArrayLike]] = None,
) -> np.ndarray:
"""Block sizes of the block-tridiagonal matrix of a sub-set of `csr` in the order of `permute`
Contrary to `~sisl_toolbox.btd.permute.btd_blocks`, `permute` need not
contain all rows of `csr`, only the rows in `permute` are partitioned.
Parameters
----------
csr :
the sparse matrix, columns may extend into supercells.
For a sparse geometry object (e.g. `~sisl.Hamiltonian`) its sparse
pattern is used.
permute :
the rows of `csr` in the order of the block-tridiagonal matrix
cost : {"speed", "memory", "speed-diagonal"}
the cost model of the block-tridiagonal matrix, see `~sisl_toolbox.btd.permute.btd_blocks`
dense :
rows of `csr` that are fully coupled, see `btd_partition`
Returns
-------
blocks : the block sizes, ``blocks.sum() == len(permute)``
"""
permute = np.asarray(permute).ravel()
# the graph in the order of `permute`, it remains symmetric without the diagonal
ptr, col = _graph_ptr_col(_subgraph(_graph(csr, dense), permute))
return btd_blocks(ptr, col, np.arange(len(permute)), cost)
def _device_permute(
graph: ssp.csr_array,
nodes: np.ndarray,
dense: Sequence[np.ndarray],
method: str = "gps",
refine: bool = True,
) -> np.ndarray:
"""Bandwidth reducing permutation table of the sub-set `nodes` of `graph`
The nodes of `graph` may be atoms or orbitals, all indices are nodes.
Parameters
----------
graph :
the (symmetric) graph of all nodes, see `_graph`
nodes :
the nodes of the device region
dense :
nodes that are fully coupled, e.g. the electrode
self-energies, all must be in `nodes`.
method :
the bandwidth reduction method, see `~sisl_toolbox.btd.permute.reduce_bandwidth`.
For ``"electrode"`` the (at most) 2 `dense` blocks are placed at
the start and end.
refine :
refine the permutation table
Returns
-------
permute : nodes in `graph` (``nodes[...]``)
"""
nodes = np.asarray(nodes).ravel()
local = np.full(graph.shape[0], -1, dtype=np.int64)
local[nodes] = np.arange(len(nodes))
dense = [local[d] for d in dense]
assert all((d >= 0).all() for d in dense)
ptr, col = _graph_ptr_col(_add_dense(_subgraph(graph, nodes), dense))
kwargs = {}
if method.lower() == "electrode":
if len(dense) > 2:
raise ValueError("method='electrode' requires at most 2 electrodes")
kwargs = dict(zip(("start", "end"), dense))
perm = _reduce_bandwidth(ptr, col, method, refine, False, **kwargs)
return nodes[perm]
def _downfold_permute(
graph: ssp.csr_array,
elec: np.ndarray,
device: np.ndarray,
exclude: np.ndarray,
cost: str = "speed",
refine: bool = True,
) -> tuple[np.ndarray, np.ndarray]:
"""Downfolding region of an electrode, its permutation table and BTD blocks
The downfolding region are the nodes (rows) connected to the electrode,
which are not in the device region, nor `exclude`.
The electrode may be partially in the device region, then only the
electrode nodes outside the device region are downfolded.
The last block are the nodes of the device region that couples to
the downfolding region (including the electrode nodes in the device region,
which couples densely through the electrode self-energy).
The downfolding region is ordered by a bandwidth reduction starting
from the electrode, the device nodes are placed last.
Parameters
----------
graph :
the (symmetric) graph of all nodes (atoms or orbitals), see `_graph`
elec :
nodes of the electrode, at least one must not be in the device region
device :
nodes of the device region
exclude :
nodes that are not part of the downfolding (e.g. buffer
and other electrodes).
A downfolding region coupling to these raises an error.
cost :
the cost model of the block-tridiagonal matrix
refine :
refine the permutation table
Returns
-------
down : the nodes of the downfolding region (in BTD order)
blocks : the BTD blocks of `down`, the last block are device nodes
"""
no = graph.shape[0]
node_elec = np.unique(np.asarray(elec).ravel())
is_device = np.zeros(no, dtype=bool)
is_device[device] = True
is_exclude = np.zeros(no, dtype=bool)
is_exclude[exclude] = True
if is_exclude[node_elec].any():
raise ValueError("electrode overlaps with the excluded indices")
# electrode nodes to be downfolded (not in the device region)
node_elec_r = node_elec[~is_device[node_elec]]
if len(node_elec_r) == 0:
raise ValueError("electrode is fully in the device region")
# breadth first search through the nodes that are not device nodes
region = np.zeros(no, dtype=bool)
region[node_elec_r] = True
front = node_elec_r
while len(front) > 0:
neighbors = np.unique(graph[front].indices)
if is_exclude[neighbors].any():
raise ValueError(
"downfolding region couples to excluded indices "
f"{neighbors[is_exclude[neighbors]].tolist()}"
)
front = neighbors[~(is_device[neighbors] | region[neighbors])]
region[front] = True
node_region = np.flatnonzero(region)
# device nodes coupling to the downfolding region, and the electrode
# nodes in the device region (coupled through the self-energy)
node_dev = np.unique(graph[node_region].indices)
node_dev = np.union1d(
node_dev[is_device[node_dev]], node_elec[is_device[node_elec]]
)
if len(node_dev) == 0:
raise ValueError("downfolding region does not couple to the device region")
# the local graph, the electrode and the device nodes are dense
nr = len(node_region)
nodes = np.concatenate([node_region, node_dev])
elec_r_local = np.searchsorted(node_region, node_elec_r)
elec_d_local = nr + np.searchsorted(node_dev, node_elec[is_device[node_elec]])
elec_local = np.concatenate([elec_r_local, elec_d_local])
dev_local = np.arange(nr, len(nodes))
sub = _add_dense(_subgraph(graph, nodes), [elec_local, dev_local])
ptr, col = _graph_ptr_col(sub)
perm = _reduce_bandwidth(
ptr, col, "electrode", refine, False, start=elec_r_local, end=dev_local
)
# ensure the device nodes are last
is_dev = perm >= nr
perm = np.concatenate([perm[~is_dev], perm[is_dev]])
# blocks of the downfolding region (without the device nodes)
perm_r = perm[:nr]
ptr, col = _graph_ptr_col(_subgraph(sub, perm_r))
blocks = btd_blocks(ptr, col, np.arange(nr), cost)
# only the last block may couple to the device nodes.
# Electrode nodes in the device region couples densely to all electrode
# nodes, so the downfolded electrode nodes end up in the last block.
couples = np.flatnonzero(np.diff(sub[perm_r][:, dev_local].tocsr().indptr))
first = np.searchsorted(np.cumsum(blocks), couples[0], side="right")
blocks = np.concatenate([blocks[:first], [blocks[first:].sum()], [len(node_dev)]])
return nodes[perm], blocks
@set_module("sisl_toolbox.btd")
def downfold_partition(
csr: SparseCSR | _SparseGeometry,
elecs: Sequence[npt.ArrayLike],
device: Optional[npt.ArrayLike] = None,
buffer: Optional[npt.ArrayLike] = None,
cost: str = "speed",
refine: bool = True,
) -> list[Optional[PermuteBTD]]:
"""Downfolding regions of the electrodes, their permutation tables and BTD blocks
The downfolding region of an electrode is the connected sub-graph of `csr`
containing the electrode rows, which is disconnected from the device region
(it stops at the device rows).
The last block are the rows of the device region that couples to
the downfolding region, i.e. where the downfolded self-energy lives.
An electrode may be partially in the device region, then only its rows
outside the device region are downfolded, and its rows in the device
region are part of the last block.
The downfolding region is ordered by a bandwidth reduction starting
from the electrode, the device rows are placed last.
All indices are rows of `csr`, i.e. use the atomic sparse pattern
(``H.toSparseAtom()``) with atomic indices, or ``H`` with orbital indices.
Parameters
----------
csr :
the sparse matrix of the full system, columns may extend into supercells.
For a sparse geometry object (e.g. `~sisl.Hamiltonian`) its sparse
pattern is used.
elecs :
rows of each electrode
device :
rows of the device region. Electrodes whose rows are all in the
device region are not downfolded, electrodes partially in the
device region are partially downfolded.
Defaults to all rows not in the electrodes nor in `buffer`.
buffer :
rows that are removed from the calculation
cost : {"speed", "memory", "speed-diagonal"}
the cost model of the block-tridiagonal matrix, see `~sisl_toolbox.btd.permute.btd_blocks`
refine :
refine the permutation tables, see `~sisl_toolbox.btd.permute.reduce_bandwidth`
Returns
-------
list :
for each electrode, a `PermuteBTD` with the rows of the
downfolding region (including the electrode and device rows),
or None for electrodes in the device region.
Raises
------
ValueError
if a downfolding region couples to the buffer or other (downfolded)
electrode rows.
"""
graph = _graph(csr)
n = graph.shape[0]
elecs = [np.asarray(idx).ravel() for idx in elecs]
if buffer is None:
buffer = np.array([], dtype=np.int64)
buffer = np.asarray(buffer).ravel()
if device is None:
is_device = np.ones(n, dtype=bool)
is_device[buffer] = False
for idx in elecs:
is_device[idx] = False
else:
is_device = np.zeros(n, dtype=bool)
is_device[np.asarray(device).ravel()] = True
device = np.flatnonzero(is_device)
# the electrode rows that are downfolded
elecs_r = [idx[~is_device[idx]] for idx in elecs]
ret = []
for i, idx in enumerate(elecs):
if len(elecs_r[i]) == 0:
# fully in the device region
ret.append(None)
continue
exclude = np.concatenate(
[buffer] + [e for j, e in enumerate(elecs_r) if j != i]
)
try:
down, blocks = _downfold_permute(graph, idx, device, exclude, cost, refine)
except ValueError as e:
raise ValueError(f"downfold_partition electrode {i}: {e}") from None
ret.append(PermuteBTD(down, blocks))
return ret
def _split_pivot(value: str) -> tuple[str, str]:
"""Split a pivoting method ``[atom+|orb+]<method>`` into the space and method
The space is ``"atoms"`` (default) or ``"orbitals"``, the method is lower-case.
"""
method = value.strip().lower()
for prefix, space in (
("atom+", "atoms"),
("atoms+", "atoms"),
("orb+", "orbitals"),
("orbs+", "orbitals"),
):
if method.startswith(prefix):
return space, method[len(prefix) :]
return "atoms", method
def _permute_a2o(geometry, permute: PermuteBTD) -> PermuteBTD:
"""Convert an atomic permutation table and BTD blocks to orbitals
Each atom is replaced by its orbitals (in order), and the block sizes
are the number of orbitals of the atoms in each block.
"""
atoms = permute.permute
starts = np.append(0, np.cumsum(permute.blocks)[:-1])
blocks = np.add.reduceat(geometry.orbitals[atoms], starts)
return PermuteBTD(geometry.a2o(atoms, all=True), blocks)
def _blocks_in_range(blocks_cum0: np.ndarray, indices: np.ndarray) -> np.ndarray:
"""Blocks spanned by the range ``[indices.min(), indices.max()]``
Parameters
----------
blocks_cum0 :
cumulative sum of the block sizes, starting with 0
indices :
matrix indices
"""
block1 = (indices.min() < blocks_cum0[1:]).nonzero()[0][0]
block2 = (indices.max() < blocks_cum0[1:]).nonzero()[0][0]
return np.arange(block1, block2 + 1)
def _is_int(key) -> bool:
"""Whether `key` is a scalar integer index"""
return isinstance(key, (int, np.integer)) and not isinstance(key, bool)
def _normalize_axes(axes, ndim: int) -> tuple[int, ...]:
"""Non-negative, bounds checked and unique `axes`"""
out = tuple(operator.index(a) for a in axes)
out = tuple(a + ndim if a < 0 else a for a in out)
if any(a < 0 or a >= ndim for a in out):
raise ValueError(f"axes {axes} out of bounds for array of dimension {ndim}")
if len(set(out)) != len(out):
raise ValueError(f"repeated axis in {axes}")
return out
def _as_slice(idx: np.ndarray) -> slice | np.ndarray:
"""`idx` as a slice if it is a contiguous ascending range, else `idx`"""
n = len(idx)
if idx[-1] - idx[0] == n - 1 and (np.diff(idx) == 1).all():
return slice(int(idx[0]), int(idx[-1]) + 1)
return idx
def _ix(*idx):
"""Orthogonal index of slices and 1D arrays"""
if sum(not isinstance(i, slice) for i in idx) <= 1:
# a single index array is orthogonal to the slices
return idx
return np.ix_(
*(np.arange(i.start, i.stop) if isinstance(i, slice) else i for i in idx)
)
def _same_blocks(blocks1, blocks2) -> bool:
"""Whether two sequences of (per axis) block sizes are equal"""
return len(blocks1) == len(blocks2) and all(
np.array_equal(b1, b2) for b1, b2 in zip(blocks1, blocks2)
)
def _densify(obj):
"""Convert all `BlockArray` in the (nested) `obj` to dense arrays"""
if isinstance(obj, BlockArray):
return obj.toarray()
if isinstance(obj, (tuple, list)):
return type(obj)(_densify(o) for o in obj)
if isinstance(obj, dict):
return {k: _densify(v) for k, v in obj.items()}
return obj
# whether a block is defined (vectorized over the grid of blocks)
_is_defined = np.frompyfunc(lambda M: M is not None, 1, 1)
# flag of contiguous arrays in a memory order
_CONTIGUOUS = {"C": "C_CONTIGUOUS", "F": "F_CONTIGUOUS"}
# ufuncs where a structural zero in any argument yields a structural zero
_ANNIHILATE = (np.multiply, np.logical_and, np.bitwise_and)
@set_module("sisl_toolbox.btd")
class BlockArrayIndexer:
"""Indexer of a `BlockArray` using block indices
``BI[i, j, ...]`` is the block of the indices in block ``i`` along the first
axis, block ``j`` along the second axis, etc.
Undefined blocks are returned as new zero arrays (which are *not*
stored in the array).
Assigning a block stores it (no copy) if it has the data-type and memory order
of the array, otherwise it is converted.
"""
__slots__ = ("_ba", "_grid")
def __init__(self, ba: BlockArray):
self._ba = ba
self._grid = ba._grid
def __len__(self) -> int:
"""Number of blocks along the first axis"""
return self._grid.shape[0]
def __iter__(self):
"""Loop the block indices of the defined blocks"""
for key in zip(*self._ba._defined().nonzero()):
yield tuple(map(int, key))
def _key(self, key) -> tuple[int, ...]:
"""`key` as a tuple of block indices (one integer per axis)"""
if type(key) is not tuple:
key = (key,)
if len(key) != self._grid.ndim:
raise ValueError(
f"{self.__class__.__name__} indexing must be done with a tuple of "
f"{self._grid.ndim} block indices."
)
return tuple(map(operator.index, key))
def __delitem__(self, key) -> None:
key = self._key(key)
if self._grid[key] is None:
raise KeyError(key)
self._grid[key] = None
def __contains__(self, key) -> bool:
return self._grid[self._key(key)] is not None
def _block(self, key: tuple):
"""Block `key` (None if undefined)
numpy validates the integers, the key is only checked when it
does not return a single block (e.g. slices or too few indices).
"""
M = self._grid[key]
if M is not None and M.dtype.hasobject:
# a sub-grid of blocks
self._key(key)
raise ValueError(
f"{self.__class__.__name__} indexing must be done with integer block indices."
)
return M
def __getitem__(self, key) -> np.ndarray:
if type(key) is not tuple:
key = (key,)
# the hot path, the checks of _block are inlined
M = self._grid[key]
if M is None:
ba = self._ba
return np.zeros(ba._block_shape(key), dtype=ba._dtype, order=ba._order)
if M.dtype.hasobject:
return self._block(key)
return M
def __setitem__(self, key, M) -> None:
if type(key) is not tuple:
key = (key,)
self._block(key)
self._grid[key] = self._ba._asblock(M, key)
def __getattr__(self, attr):
return getattr(self._ba, attr)
@set_module("sisl_toolbox.btd")
class BlockArray(np.ndarray):
r"""N-dimensional array split into blocks where undefined blocks are (structurally) zero
Each axis is split into blocks of the sizes in `blocks`, e.g. a
block-tridiagonal matrix is a 2D array with the same blocks along
both axes, ``BlockArray([blocks, blocks])``.
The array is a `numpy.ndarray` subclass whose elements are the blocks.
The underlying array is a grid of objects (one dimension per axis), each either
a dense `numpy.ndarray` (a defined block) or `None` (an undefined, zero, block).
`shape`, `dtype` and `len` refer to the (dense) array, i.e.
``shape == tuple(b.sum() for b in blocks)``.
Blocks are accessed and assigned through `block_indexer` with block indices,
the array can be extended with new blocks at any time.
All blocks have the data-type `dtype` and memory order `order`.
Indexing the array (``ba[i, j, ...]``) uses array indices and follows
the numpy semantics, returning dense arrays. If the index along each
axis is a sequence of complete blocks a `BlockArray` of these blocks
is returned instead (the blocks are shared when indexing with slices,
otherwise copied).
Assigning elements allocates the blocks that are needed (unless the
assigned values are zero).
Element-wise ufuncs (``-ba``, ``ba * 2``, ``ba + ba``, ``np.conj(ba)``, ...)
and matrix multiplications (``ba @ ba``, and ``ba @ x``, ``x @ ba`` for 2D arrays)
only operate on the defined blocks, when the undefined blocks remain zero.
The undefined blocks are exact zeros, so `np.multiply` only stores the
blocks defined in all arguments (like `scipy.sparse`).
Any other operation returns the result of the dense array (`toarray`),
e.g. ``ba + 1``.
Parameters
----------
blocks :
the size of the blocks along each axis (one 1D array per axis)
dtype :
data-type of the array, all blocks are converted to this data-type
order : {"C", "F"}
memory order of the blocks
Notes
-----
`numpy.asarray` returns the grid of blocks, use `toarray` for the dense array.
Examples
--------
>>> ba = BlockArray([[2, 3], [2, 3]], dtype=np.float64)
>>> ba.block_indexer[1, 1] = np.ones([3, 3])
>>> ba.shape
(5, 5)
>>> full = np.zeros(ba.shape, dtype=ba.dtype)
>>> full[ba.indices()] = ba[ba.indices()]
>>> np.allclose(full, ba.toarray())
True
"""
def __new__(
cls,
blocks: Sequence[npt.ArrayLike],
dtype: npt.DTypeLike = np.float64,
order: Literal["C", "F"] = "C",
):
blocks = tuple(np.asarray(b, dtype=np.intp) for b in blocks)
if len(blocks) == 0 or any(b.ndim != 1 or (b < 0).any() for b in blocks):
raise ValueError(
f"{cls.__name__} blocks must be a sequence (one per axis) of 1D "
"arrays of non-negative sizes"
)
order = order.upper()
if order not in ("C", "F"):
raise ValueError(f"{cls.__name__} order must be 'C' or 'F'")
# np.empty fills object arrays with None
obj = np.empty([len(b) for b in blocks], dtype=object).view(cls)
obj._set_meta(blocks, np.dtype(dtype), order)
return obj
def _set_meta(self, blocks: tuple, dtype: np.dtype, order: str) -> None:
self._blocks = blocks
self._blocks_cum0 = tuple(np.concatenate(([0], np.cumsum(b))) for b in blocks)
# block of each index (per axis)
self._index_blocks = tuple(np.repeat(np.arange(len(b)), b) for b in blocks)
self._shape = tuple(int(c[-1]) for c in self._blocks_cum0)
# block sizes as Python ints (fast scalar look-ups)
self._block_sizes = tuple(b.tolist() for b in blocks)
self._dtype = dtype
self._order = order
def __array_finalize__(self, obj) -> None:
if obj is None or not hasattr(obj, "_blocks"):
return
self._set_meta(obj._blocks, obj._dtype, obj._order)
@property
def _grid(self) -> np.ndarray:
"""The object array of blocks (`None` for undefined blocks)"""
return self.view(np.ndarray)
def _defined(self) -> np.ndarray:
"""Boolean array (of the grid shape) of the defined blocks"""
return _is_defined(self._grid).astype(bool)
def _iter_defined(self):
"""Loop ``(key, block)`` of the defined blocks"""
grid = self._grid
for key in zip(*self._defined().nonzero()):
yield key, grid[key]
def _block_shape(self, key) -> tuple[int, ...]:
"""Shape of block `key` (block indices)"""
return tuple(map(list.__getitem__, self._block_sizes, key))
def _block_slices(self, key) -> tuple[slice, ...]:
"""Slices of the indices of block `key` (block indices)"""
return tuple(slice(c[k], c[k + 1]) for c, k in zip(self._blocks_cum0, key))
def _asblock(self, M, key) -> np.ndarray:
"""`M` as block `key` (block indices) with the data-type and order of the array"""
shape = self._block_shape(key)
if (
type(M) is np.ndarray
and M.dtype == self._dtype
and M.shape == shape
and M.flags[_CONTIGUOUS[self._order]]
):
return M
M = np.asarray(M)
if M.shape != shape:
raise ValueError(
f"{self.__class__.__name__} could not assign array of shape "
f"{M.shape} into block of shape {shape}"
)
# numpy raises for casts that lose data (e.g. complex -> float)
return M.astype(self._dtype, order=self._order, casting="same_kind", copy=False)
def _map(self, func, grid=None, blocks=None, dtype=None, order=None) -> BlockArray:
"""New block array with the blocks ``func(M)`` of the defined blocks ``M`` in `grid`"""
new = BlockArray(
self._blocks if blocks is None else blocks,
self._dtype if dtype is None else dtype,
self._order if order is None else order,
)
if grid is None:
grid = self._grid
new._grid[...] = np.frompyfunc(lambda M: None if M is None else func(M), 1, 1)(
grid
)
return new
@property
def blocks(self) -> tuple[np.ndarray, ...]:
"""Size of the blocks along each axis"""
return self._blocks
@property
def shape(self) -> tuple[int, ...]:
"""Shape of the (dense) array"""
return self._shape
@property
def dtype(self) -> np.dtype:
"""Data-type of the array"""
return self._dtype
@property
def order(self) -> str:
"""Memory order of the blocks"""
return self._order
@property
def size(self) -> int:
"""Number of elements in the (dense) array"""
return math.prod(self._shape)
@property
def itemsize(self) -> int:
return self._dtype.itemsize
@property
def nbytes(self) -> int:
"""Number of bytes of the defined blocks"""
return sum(M.nbytes for _, M in self._iter_defined())
def __len__(self) -> int:
"""The length of the first dimension of the array"""
return self._shape[0]
def __repr__(self) -> str:
grid = self._grid
return (
f"<{self.__class__.__module__}.{self.__class__.__name__} "
f"shape={self.shape}, blocks={grid.shape}, "
f"defined={self._defined().sum()}/{grid.size}, "
f"dtype={self._dtype}, order={self._order!r}>"
)
__str__ = __repr__
def __iter__(self):
"""Loop the first dimension of the dense array"""
return iter(self.toarray())
def __bool__(self) -> bool:
return bool(self.toarray())
def __reduce__(self):
# ndarray.__reduce__ would store the (overridden) dtype in its state
return _rebuild_block_array, (
self._blocks,
self._dtype,
self._order,
self._grid,
)
def __copy__(self) -> BlockArray:
return self.copy()
def __deepcopy__(self, memo) -> BlockArray:
return self.copy()
[docs]
def copy(self) -> BlockArray:
"""Create a copy of this block array (all blocks are copied)"""
return self._map(lambda M: M.copy(order=self._order))
[docs]
def astype(
self, dtype, order=None, casting="unsafe", copy: bool = True
) -> BlockArray:
"""Block array with blocks converted to `dtype` (and `order`)"""
order = self._order if order is None or order in "KA" else order.upper()
return self._map(
lambda M: M.astype(dtype, order=order, casting=casting, copy=copy),
dtype=np.dtype(dtype),
order=order,
)
@property
def T(self) -> BlockArray:
"""Array with reversed axes, see `transpose`"""
return self.transpose()
[docs]
def transpose(self, *axes) -> BlockArray:
"""Array with permuted axes, the blocks are views of the transposed blocks
Reversing the axes swaps the memory order ("C" <-> "F"), for other
permutations the blocks are not contiguous.
"""
if len(axes) == 1 and (axes[0] is None or isinstance(axes[0], (tuple, list))):
axes = axes[0]
nd = self.ndim
if not axes:
axes = tuple(range(nd))[::-1]
axes = _normalize_axes(axes, nd)
if len(axes) != nd:
raise ValueError("axes don't match array")
order = self._order
if nd > 1 and axes == tuple(range(nd))[::-1]:
order = "F" if order == "C" else "C"
return self._map(
lambda M: M.transpose(axes),
grid=self._grid.transpose(axes),
blocks=tuple(self._blocks[a] for a in axes),
order=order,
)
@property
def real(self) -> BlockArray:
"""Real part of the array, the blocks are views"""
return self._map(lambda M: M.real, dtype=np.empty(0, self._dtype).real.dtype)
@property
def imag(self) -> BlockArray:
"""Imaginary part of the array, the blocks are views"""
if self._dtype.kind != "c":
return BlockArray(self._blocks, self._dtype, self._order)
return self._map(lambda M: M.imag, dtype=np.empty(0, self._dtype).real.dtype)
[docs]
def conj(self) -> BlockArray:
return np.conjugate(self)
conjugate = conj
[docs]
def dot(self, other, out=None):
if out is not None:
return np.dot(self.toarray(), _densify(other), out=out)
return self @ other
[docs]
def toarray(self) -> np.ndarray:
"""Convert to a dense array, where non-defined blocks will be zero"""
D = np.zeros(self._shape, dtype=self._dtype, order=self._order)
for key, M in self._iter_defined():
D[self._block_slices(key)] = M
return D
def _band(self, width: int, axes) -> BlockArray:
"""Block array (sharing blocks) of the blocks within `width` of the block diagonal"""
idx = np.indices(self._grid.shape)
if axes is not None:
idx = idx[list(_normalize_axes(axes, self.ndim))]
mask = idx.max(0) - idx.min(0) <= width
ret = BlockArray(self._blocks, self._dtype, self._order)
ret._grid[mask] = self._grid[mask]
return ret
[docs]
def tobtd(self, axes: Optional[Sequence[int]] = None) -> BlockArray:
"""Return only the block tridiagonal part of the array (blocks are shared)
Parameters
----------
axes :
the axes where the block indices may differ by at most 1, defaults to all axes
"""
return self._band(1, axes)
[docs]
def tobd(self, axes: Optional[Sequence[int]] = None) -> BlockArray:
"""Return only the block diagonal part of the array (blocks are shared)
Parameters
----------
axes :
the axes where the block indices are equal, defaults to all axes
"""
return self._band(0, axes)
[docs]
def diagonal(
self, offset: int = 0, axis1: int = 0, axis2: int = 1
) -> BlockArray | np.ndarray:
"""Diagonal of the array along `axis1` and `axis2`, see `numpy.diagonal`
The two axes are removed and the diagonal is the last axis.
If `offset` is 0 and the two axes have the same blocks, the
diagonal is a `BlockArray` (copies of the block diagonals), otherwise
a dense array.
"""
nd = self.ndim
a1, a2 = _normalize_axes((axis1, axis2), nd)
keep = [a for a in range(nd) if a not in (a1, a2)]
if offset == 0 and np.array_equal(self._blocks[a1], self._blocks[a2]):
return self._map(
lambda M: M.diagonal(0, a1, a2).copy(order=self._order),
grid=self._grid.diagonal(0, a1, a2),
blocks=tuple(self._blocks[a] for a in keep) + (self._blocks[a1],),
)
n1, n2 = self._shape[a1], self._shape[a2]
if offset >= 0:
i1 = np.arange(max(0, min(n1, n2 - offset)))
i2 = i1 + offset
else:
i2 = np.arange(max(0, min(n1 + offset, n2)))
i1 = i2 - offset
# the advanced indices are the last (adjacent) axes, so the diagonal is last
T = self.transpose(keep + [a1, a2])
return T._get_fancy(T._fancy_key([slice(None)] * len(keep) + [i1, i2]))
[docs]
def trace(
self, offset: int = 0, axis1: int = 0, axis2: int = 1, dtype=None, out=None
):
"""Sum along the diagonal of the array, see `numpy.trace`"""
return self.diagonal(offset, axis1, axis2).sum(axis=-1, dtype=dtype, out=out)
[docs]
def indices(self, defined: bool = True) -> tuple[np.ndarray, ...]:
"""Array indices (one array per axis) of the defined (or undefined) blocks
The indices are ordered by blocks (row-major over the blocks), and
within each block in the memory order of the blocks.
Parameters
----------
defined :
whether to return the indices of the defined blocks, or of
the undefined (zero) blocks
Examples
--------
>>> full = np.zeros(ba.shape, dtype=ba.dtype)
>>> full[ba.indices()] = ba[ba.indices()]
>>> np.allclose(full[ba.indices(defined=False)], 0)
True
"""
mask = self._defined()
if not defined:
mask = ~mask
out = [[] for _ in range(self.ndim)]
for key in zip(*mask.nonzero()):
idx = np.indices(self._block_shape(key))
for o, ix, c, k in zip(out, idx, self._blocks_cum0, key):
o.append(ix.ravel(order=self._order) + c[k])
if len(out[0]) == 0:
return tuple(np.empty(0, dtype=np.intp) for _ in out)
return tuple(np.concatenate(o) for o in out)
@property
def block_indexer(self) -> BlockArrayIndexer:
"""Get the indexer for this block array
The indexer allows manipulating the array using indices of the blocks,
rather than indices of the array elements.
"""
return BlockArrayIndexer(self)
# Indexing with array indices
def _normalize(self, idx, axis: int) -> np.ndarray:
"""Non-negative, bounds checked, indices of an index array `idx` (of any shape) along `axis`"""
idx = np.asarray(idx)
n = self._shape[axis]
if idx.dtype == bool:
if idx.ndim != 1 or len(idx) != n:
raise IndexError(
f"boolean index did not match axis {axis} with size {n}"
)
return idx.nonzero()[0]
if idx.size == 0:
return idx.astype(np.intp)
if idx.dtype.kind not in "iu":
raise IndexError(
"only integers, slices (`:`), ellipsis (`...`) and integer or "
"boolean arrays are valid indices"
)
idx = idx.astype(np.intp, copy=False)
if idx.min() < -n or idx.max() >= n:
raise IndexError(f"index out of bounds for axis {axis} with size {n}")
return np.where(idx < 0, idx + n, idx)
def _split_key(self, key) -> Optional[list]:
"""`key` as a list of normalized indices (one per axis), or None if it is not handled
Slices are retained, all other indices are normalized integer arrays
(0D arrays for integers).
"""
nd = self.ndim
if not isinstance(key, tuple):
if (
isinstance(key, np.ndarray)
and key.dtype == bool
and key.ndim == nd
and nd > 1
):
if key.shape != self.shape:
raise IndexError("boolean index did not match the array shape")
return list(key.nonzero())
key = (key,)
if any(k is None for k in key):
return None
if any(
isinstance(k, np.ndarray) and k.dtype == bool and k.ndim != 1 for k in key
):
return None
ellipsis = [i for i, k in enumerate(key) if k is Ellipsis]
if len(ellipsis) > 1:
raise IndexError("an index can only have a single ellipsis ('...')")
if ellipsis:
i = ellipsis[0]
key = key[:i] + (slice(None),) * (nd + 1 - len(key)) + key[i + 1 :]
if len(key) > nd:
raise IndexError(
f"too many indices for {self.__class__.__name__}: it is "
f"{nd}-dimensional, but {len(key)} were indexed"
)
key = list(key) + [slice(None)] * (nd - len(key))
return [
k if isinstance(k, slice) else self._normalize(k, axis)
for axis, k in enumerate(key)
]
def _orthogonal_key(self, keys: list) -> Optional[tuple]:
"""1D indices per axis if `keys` are orthogonal (as `np.ix_`), otherwise None"""
nd = len(keys)
idx = []
for axis, k in enumerate(keys):
if isinstance(k, slice) or k.ndim != nd:
return None
if any(s != 1 for a, s in enumerate(k.shape) if a != axis):
return None
idx.append(k.ravel())
return tuple(idx)
def _fancy_key(self, keys: list) -> tuple[np.ndarray, ...]:
"""Broadcastable index arrays (one per axis) equivalent to numpy indexing with `keys`
`keys` contains at least one index array.
The broadcast shape of the index arrays is placed at the first
index array when all index arrays are adjacent, otherwise first.
"""
nd = len(keys)
adv = [a for a, k in enumerate(keys) if not isinstance(k, slice)]
sl = [a for a, k in enumerate(keys) if isinstance(k, slice)]
bshape = np.broadcast_shapes(*(keys[a].shape for a in adv))
nb = len(bshape)
if adv[-1] - adv[0] == len(adv) - 1:
start = sum(a < adv[0] for a in sl)
else:
start = 0
ndim = len(sl) + nb
idx = [None] * nd
for r, a in enumerate(sl):
pos = r if r < start else r + nb
shape = [1] * ndim
ar = np.arange(*keys[a].indices(self._shape[a]))
shape[pos] = len(ar)
idx[a] = ar.reshape(shape)
for a in adv:
k = keys[a]
shape = (1,) * start + (1,) * (nb - k.ndim) + k.shape
idx[a] = k.reshape(shape + (1,) * (ndim - len(shape)))
return tuple(idx)
def _groups(self, idx: np.ndarray, axis: int) -> list:
"""Split the indices `idx` along `axis` into the blocks they belong to
Returns a list of ``(block, positions in idx, indices local to the block)``
where the positions and local indices are slices when contiguous.
"""
if len(idx) == 0:
return []
c = self._blocks_cum0[axis]
bidx = self._index_blocks[axis][idx]
order = np.argsort(bidx, kind="stable")
bounds = np.flatnonzero(np.diff(bidx[order])) + 1
groups = []
for pos in np.split(order, bounds):
b = bidx[pos[0]]
groups.append((b, _as_slice(pos), _as_slice(idx[pos] - c[b])))
return groups
def _fancy_groups(self, idx: list):
"""Loop ``(key, sel)`` for the elements ``sel`` (of the 1D arrays `idx`) in block `key`"""
if len(idx[0]) == 0:
return
shape = self._grid.shape
key = np.ravel_multi_index(
tuple(ib[x] for ib, x in zip(self._index_blocks, idx)), shape
)
order = np.argsort(key, kind="stable")
bounds = np.flatnonzero(np.diff(key[order])) + 1
for sel in np.split(order, bounds):
yield np.unravel_index(int(key[sel[0]]), shape), sel
def _block_sequence(self, idx: np.ndarray, axis: int) -> Optional[np.ndarray]:
"""Blocks of `idx` (along `axis`) if it is a sequence of complete blocks, otherwise None"""
if len(idx) == 0:
return None
c = self._blocks_cum0[axis]
bidx = self._index_blocks[axis][idx]
# the blocks that start in idx
seq = bidx[idx == c[bidx]]
full = array_arange(c[seq], c[seq + 1])
if len(full) == len(idx) and (full == idx).all():
return seq
return None
def _block_select(self, idx: tuple, share: bool) -> Optional[BlockArray]:
"""Block array of the indices `idx` (per axis) if they are sequences of complete blocks"""
seqs = []
for axis, x in enumerate(idx):
seq = self._block_sequence(x, axis)
if seq is None:
return None
seqs.append(seq)
func = (lambda M: M) if share else (lambda M: M.copy(order=self._order))
return self._map(
func,
grid=self._grid[np.ix_(*seqs)],
blocks=tuple(b[s] for b, s in zip(self._blocks, seqs)),
)
def __getitem__(self, key):
keys = self._split_key(key)
if keys is None:
return self.toarray()[key]
if all(not isinstance(k, slice) and k.ndim == 0 for k in keys):
bkey = tuple(ib[k] for ib, k in zip(self._index_blocks, keys))
M = self._grid[bkey]
if M is None:
return self._dtype.type(0)
return M[tuple(k - c[b] for k, c, b in zip(keys, self._blocks_cum0, bkey))]
if all(isinstance(k, slice) or k.ndim == 0 for k in keys):
# basic indexing
idx = tuple(
(np.arange(*k.indices(n)) if isinstance(k, slice) else k.reshape(1))
for k, n in zip(keys, self._shape)
)
if all(isinstance(k, slice) for k in keys):
ba = self._block_select(idx, True)
if ba is not None:
return ba
out = self._get_orthogonal(idx)
return out[tuple(slice(None) if isinstance(k, slice) else 0 for k in keys)]
idx = self._orthogonal_key(keys)
if idx is not None:
ba = self._block_select(idx, False)
if ba is not None:
return ba
return self._get_orthogonal(idx)
return self._get_fancy(self._fancy_key(keys))
def _get_orthogonal(self, idx: tuple) -> np.ndarray:
"""Dense array of the elements in ``np.ix_(*idx)``"""
out = np.zeros(tuple(len(x) for x in idx), dtype=self._dtype, order=self._order)
grid = self._grid
groups = [self._groups(x, axis) for axis, x in enumerate(idx)]
for combo in itertools.product(*groups):
M = grid[tuple(g[0] for g in combo)]
if M is not None:
out[_ix(*(g[1] for g in combo))] = M[_ix(*(g[2] for g in combo))]
return out
def _get_fancy(self, idx: tuple) -> np.ndarray:
"""Elements of the index arrays `idx` (one per axis, broadcast together)"""
idx = np.broadcast_arrays(*idx)
shape = idx[0].shape
idx = [x.ravel() for x in idx]
out = np.zeros(len(idx[0]), dtype=self._dtype)
cum = self._blocks_cum0
grid = self._grid
for key, sel in self._fancy_groups(idx):
M = grid[key]
if M is not None:
out[sel] = M[tuple(x[sel] - c[k] for x, c, k in zip(idx, cum, key))]
return out.reshape(shape)
def __setitem__(self, key, value) -> None:
keys = self._split_key(key)
if keys is None:
raise IndexError(
f"{self.__class__.__name__} does not support index {key!r}"
)
value = np.asarray(value)
if not np.can_cast(value.dtype, self._dtype, "same_kind"):
raise TypeError(
f"{self.__class__.__name__} cannot cast values from {value.dtype} to {self._dtype}"
)
if all(isinstance(k, slice) or k.ndim == 0 for k in keys):
# basic indexing
idx = tuple(
(np.arange(*k.indices(n)) if isinstance(k, slice) else k.reshape(1))
for k, n in zip(keys, self._shape)
)
shape = tuple(len(x) for x, k in zip(idx, keys) if isinstance(k, slice))
value = np.broadcast_to(value, shape).reshape(tuple(len(x) for x in idx))
self._set_orthogonal(idx, value)
else:
idx = np.broadcast_arrays(*self._fancy_key(keys))
value = np.broadcast_to(value, idx[0].shape)
self._set_fancy([x.ravel() for x in idx], value.ravel())
def _new_block(self, key) -> np.ndarray:
"""Allocate a zero block `key` and store it in the array"""
M = np.zeros(self._block_shape(key), dtype=self._dtype, order=self._order)
self._grid[key] = M
return M
def _set_orthogonal(self, idx: tuple, value: np.ndarray) -> None:
grid = self._grid
groups = [self._groups(x, axis) for axis, x in enumerate(idx)]
for combo in itertools.product(*groups):
key = tuple(g[0] for g in combo)
V = value[_ix(*(g[1] for g in combo))]
M = grid[key]
if M is None:
if not V.any():
continue
M = self._new_block(key)
M[_ix(*(g[2] for g in combo))] = V
def _set_fancy(self, idx: list, value: np.ndarray) -> None:
cum = self._blocks_cum0
grid = self._grid
for key, sel in self._fancy_groups(idx):
V = value[sel]
M = grid[key]
if M is None:
if not V.any():
continue
M = self._new_block(key)
M[tuple(x[sel] - c[k] for x, c, k in zip(idx, cum, key))] = V
# numpy protocols
def __array_ufunc__(self, ufunc, method, *inputs, out=None, **kwargs):
if method == "__call__" and "where" not in kwargs:
if ufunc is np.matmul:
ret = _matmul(*inputs, out=out, **kwargs)
elif ufunc.nout == 1 and ufunc.signature is None:
ret = _elementwise(ufunc, inputs, out, kwargs)
else:
ret = NotImplemented
if ret is not NotImplemented:
return ret
# dense fallback
if out is not None:
if any(isinstance(o, BlockArray) for o in out):
raise TypeError(
f"{ufunc.__name__} does not retain the zero blocks, the result "
f"cannot be stored in a {self.__class__.__name__}"
)
kwargs["out"] = out
return getattr(ufunc, method)(*_densify(inputs), **kwargs)
def __array_function__(self, func, types, args, kwargs):
handled = _ARRAY_FUNCTIONS.get(func)
if handled is not None:
return handled(*args, **kwargs)
return func(*_densify(args), **_densify(kwargs))
def _rebuild_block_array(blocks, dtype, order, grid) -> BlockArray:
"""Unpickle a `BlockArray`"""
ba = BlockArray(blocks, dtype, order)
ba._grid[...] = grid
return ba
def _elementwise(ufunc, inputs, out, kwargs):
"""Element-wise `ufunc` on the defined blocks, NotImplemented if the zero blocks are not retained"""
bas = [x for x in inputs if isinstance(x, BlockArray)]
if not bas:
return NotImplemented
ref = bas[0]
for x in inputs:
if isinstance(x, BlockArray):
if not _same_blocks(x._blocks, ref._blocks):
return NotImplemented
elif np.ndim(x) != 0:
return NotImplemented
if out is not None:
if (
len(out) != 1
or not isinstance(out[0], BlockArray)
or not _same_blocks(out[0]._blocks, ref._blocks)
):
return NotImplemented
out = out[0]
# value of the undefined blocks
zero = [np.zeros(1, x._dtype) if isinstance(x, BlockArray) else x for x in inputs]
with np.errstate(all="ignore"):
zero = ufunc(*zero, **kwargs)
if zero[0] != 0:
return NotImplemented
reduce = np.logical_and if ufunc in _ANNIHILATE else np.logical_or
pattern = reduce.reduce([x._defined() for x in bas])
if out is None:
ret = BlockArray(ref._blocks, zero.dtype, ref._order)
kwargs.setdefault("order", ref._order)
else:
ret = out
grid = ret._grid
grids = [x._grid if isinstance(x, BlockArray) else None for x in inputs]
for key in zip(*pattern.nonzero()):
args = []
for x, g in zip(inputs, grids):
if g is None:
args.append(x)
continue
M = g[key]
if M is None:
M = np.zeros(ref._block_shape(key), dtype=x._dtype)
args.append(M)
M = grid[key] if out is not None else None
if M is None:
M = ufunc(*args, **kwargs)
grid[key] = M if out is None else ret._asblock(M, key)
else:
ufunc(*args, out=M, **kwargs)
if out is not None:
grid[~pattern] = None
return ret
def _matmul(a, b, out=None, **kwargs):
"""Matrix multiplication only using the defined blocks"""
if out is not None or kwargs:
return NotImplemented
if isinstance(a, BlockArray) and isinstance(b, BlockArray):
# stacked matrices, the leading axes must have the same blocks
if (
a.ndim < 2
or a.ndim != b.ndim
or not _same_blocks(a._blocks[:-2], b._blocks[:-2])
or not np.array_equal(a._blocks[-1], b._blocks[-2])
):
return NotImplemented
ret = BlockArray(
a._blocks[:-1] + (b._blocks[-1],),
np.result_type(a._dtype, b._dtype),
a._order,
)
ga, gb, grid = a._grid, b._grid, ret._grid
ma, mb = a._defined(), b._defined()
for L in np.ndindex(*ga.shape[:-2]):
for k in range(ga.shape[-1]):
J = mb[L + (k,)].nonzero()[0]
for i in ma[L + (slice(None), k)].nonzero()[0]:
A = ga[L + (i, k)]
for j in J:
key = L + (i, j)
M = grid[key]
if M is None:
grid[key] = ret._asblock(A @ gb[L + (k, j)], key)
else:
M += A @ gb[L + (k, j)]
return ret
if isinstance(a, BlockArray):
b = np.asarray(b)
if a.ndim != 2 or b.ndim not in (1, 2) or len(b) != a._shape[1]:
return NotImplemented
cr, ck = a._blocks_cum0
ret = np.zeros(
(a._shape[0],) + b.shape[1:], dtype=np.result_type(a._dtype, b.dtype)
)
for (i, k), A in a._iter_defined():
ret[cr[i] : cr[i + 1]] += A @ b[ck[k] : ck[k + 1]]
return ret
a = np.asarray(a)
if b.ndim != 2 or a.ndim not in (1, 2) or a.shape[-1] != b._shape[0]:
return NotImplemented
ck, cc = b._blocks_cum0
ret = np.zeros(
a.shape[:-1] + (b._shape[1],), dtype=np.result_type(a.dtype, b._dtype)
)
for (k, j), B in b._iter_defined():
ret[..., cc[j] : cc[j + 1]] += a[..., ck[k] : ck[k + 1]] @ B
return ret
_ARRAY_FUNCTIONS = {
np.shape: lambda a: a.shape,
np.ndim: lambda a: a.ndim,
np.size: lambda a, axis=None: a.size if axis is None else a.shape[axis],
np.copy: lambda a, *args, **kwargs: a.copy(),
np.transpose: lambda a, axes=None: a.transpose(axes),
np.diagonal: lambda a, offset=0, axis1=0, axis2=1: a.diagonal(offset, axis1, axis2),
np.trace: lambda a, offset=0, axis1=0, axis2=1, dtype=None, out=None: a.trace(
offset, axis1, axis2, dtype, out
),
np.real: lambda a: a.real,
np.imag: lambda a: a.imag,
}
def _dense_method(name: str):
def method(self, *args, **kwargs):
return getattr(self.toarray(), name)(*args, **kwargs)
method.__name__ = name
method.__doc__ = f"Equivalent to ``self.toarray().{name}(...)``"
return method
def _unsupported_method(name: str):
def method(self, *args, **kwargs):
raise NotImplementedError(
f"{BlockArray.__name__}.{name} is not supported, use toarray() or block_indexer"
)
method.__name__ = name
return method
# The ndarray methods operate on the grid of blocks, they are replaced
# by their dense equivalents, or disabled when they would modify the array.
for _name in (
"all",
"any",
"argmax",
"argmin",
"argpartition",
"argsort",
"choose",
"clip",
"compress",
"cumprod",
"cumsum",
"flatten",
"item",
"max",
"mean",
"min",
"nonzero",
"prod",
"ptp",
"ravel",
"repeat",
"reshape",
"round",
"searchsorted",
"squeeze",
"std",
"sum",
"swapaxes",
"take",
"tobytes",
"tofile",
"tolist",
"var",
):
setattr(BlockArray, _name, _dense_method(_name))
for _name in (
"byteswap",
"fill",
"itemset",
"partition",
"put",
"resize",
"setfield",
"sort",
):
setattr(BlockArray, _name, _unsupported_method(_name))
del _name