Source code for clifford._layout_helpers

This module provides helpers that describe some aspect of a layout.

The two public classes are:

* BasisBladeOrder
* BasisVectorIds


from typing import TypeVar, Generic, Sequence, Tuple, List, Optional
import numpy as np
import functools
import operator

from . import _numba_utils
from ._bit_helpers import count_set_bits, set_bit_indices

def canonical_reordering_sign_euclidean(bitmap_a, bitmap_b):
    Computes the sign for the product of bitmap_a and bitmap_b
    assuming a euclidean metric
    a = bitmap_a >> 1
    sum_value = 0
    while a != 0:
        sum_value = sum_value + count_set_bits(a & bitmap_b)
        a = a >> 1
    if (sum_value & 1) == 0:
        return 1
        return -1

def _is_unique(x) -> bool:
    return len(x) == len(set(x))

[docs]class BasisBladeOrder: """ Represents the storage order in memory of basis blade coefficients. Bitmaps represent which basis vectors are present in a basis blade. For instance, in an algebra with basis vectors :math:`e_w, e_x, e_y, e_z`, the basis blade :math:`e_xz` is represented with ``0b1010``. Note that this appears reversed because binary numbers are written with the nth bit first. Attributes ---------- index_to_bitmap : numpy.ndarray An array mapping storage indices to bitmaps. bitmap_to_indices : numpy.ndarray A reverse mapping of :attr:`index_to_bitmap`. If bitmaps are missing, this array contains ``-1``. grades : numpy.ndarray An array mapping indices to the grade of the basis vector, that is the number of bits in the bitmap. See also -------- BasisVectorIds.order_from_tuples """ def __init__(self, bitmaps): if not _is_unique(bitmaps): raise ValueError("blade bitmaps are not unique") self.index_to_bitmap = np.array(bitmaps, dtype=int) self.grades = np.zeros(len(self.index_to_bitmap)) for i, bitmap in enumerate(self.index_to_bitmap): self.grades[i] = count_set_bits(bitmap) # chosen so that no product of basis blades lies outside this mapping largest = np.bitwise_or.reduce(self.index_to_bitmap) + 1 self.bitmap_to_index = np.full(largest, -1, dtype=int) self.bitmap_to_index[self.index_to_bitmap] = np.arange(len(self.index_to_bitmap), dtype=int) def __repr__(self) -> str: bitmap_strs = ['{:b}'.format(bitmap) for bitmap in self.index_to_bitmap] max_bits = max((len(s) for s in bitmap_strs), default=0) bitmap_strs = ['0b' + s.rjust(max_bits, '0') for s in bitmap_strs] return "{}([{}])".format(type(self).__name__, ', '.join(bitmap_strs)) def __hash__(self) -> int: return hash(self.index_to_bitmap.tobytes()) def __eq__(self, other): if self is other: return True if not isinstance(other, BasisBladeOrder): return NotImplemented return np.array_equal(self.index_to_bitmap, other.index_to_bitmap)
[docs] @classmethod def shortlex(cls, n_vectors: int) -> 'BasisBladeOrder': """ Get an optimized shortlex ordering. This sorts basis blades first by grade, and then lexicographically. """ return _ShortLexBasisBladeOrder(n_vectors)
class _ShortLexBasisBladeOrder(BasisBladeOrder): # lgtm [py/missing-call-to-init] def __init__(self, n_vectors: int): # deliberately skip the base class init, we can do a little better self._n = n_vectors # could attempt to optimize this by avoiding going via python integers # and copying the raw logic from # python/cpython.git:Modules/itertoolsmodule.c@combinations_next. from clifford import _powerset self.index_to_bitmap = np.empty(2**n_vectors, dtype=int) self.grades = np.empty(2**n_vectors, dtype=int) self.bitmap_to_index = np.empty(2**n_vectors, dtype=int) for i, t in enumerate(_powerset([1 << i for i in range(n_vectors)])): bitmap = functools.reduce(operator.or_, t, 0) self.index_to_bitmap[i] = bitmap self.grades[i] = len(t) self.bitmap_to_index[bitmap] = i del t # enables an optimization inside itertools.combinations def __repr__(self): return 'BasisBladeOrder.shortlex({})'.format(self._n) def __eq__(self, other): if self is other: return True if not isinstance(other, _ShortLexBasisBladeOrder): return NotImplemented return self._n == other._n def __reduce__(self): return __class__, (self._n,) IdT = TypeVar('IdT')
[docs]class BasisVectorIds(Generic[IdT]): """ Stores ids for the ordered set of basis vectors, typically integers. Provides helpers to convert between bitmaps indicating which vectors are present in a blade, and tuples of the original ids. For example:: >>> ids = BasisVectorIds([11, 22, 33]) >>> ids.bitmap_as_tuple(0b110) (22, 33) >>> sign, bitmap = ids.tuple_as_sign_and_bitmap((33, 22)) >>> assert sign, bitmap == (-1, 0b110) """ def __init__(self, blade_ids: Sequence[IdT]): if not _is_unique(blade_ids): raise ValueError("blade ids are not unique") self.values = blade_ids
[docs] def bitmap_as_tuple(self, bitmap: int) -> Tuple[IdT]: """ Convert a bitmap representation into a tuple of ids. """ return tuple(self.values[n] for n in set_bit_indices(bitmap))
[docs] def id_as_bitmap(self, id: IdT) -> int: """ Convert the id of a single vector into a bitmap representation. """ try: return (1 << self.values.index(id)) except ValueError: raise ValueError("Unknown basis {}".format(id)) from None
[docs] def tuple_as_sign_and_bitmap(self, blade: Tuple[IdT]) -> Tuple[int, int]: """ Convert a blade from a tuple of ids into a bitmap representation. """ bitmap_out = 0 s = 1 for b in blade: bitmap_b = self.id_as_bitmap(b) if bitmap_b & bitmap_out: raise ValueError("blade contains repeated basis vector {}".format(b)) # as we don't allow repeated indices, the euclidean version is fine s *= canonical_reordering_sign_euclidean(bitmap_out, bitmap_b) bitmap_out ^= bitmap_b return s, bitmap_out
[docs] def order_from_tuples(self, blades: Sequence[Tuple[IdT]]) -> BasisBladeOrder: """ Produce an ordering from a set of tuples. This is the inverse of :meth:`order_as_tuples`. >>> ids = BasisVectorIds(['x', 'y']) >>> ids.order_from_tuples([(), ('y',), ('x', 'y'), ('x',)]) BasisBladeOrder([0b00, 0b10, 0b11, 0b01]) """ bitmaps = [] for blade in blades: s, bitmap = self.tuple_as_sign_and_bitmap(blade) if s != 1: raise NotImplementedError( "The blade {} is not canonical, and sign flips in storage " "are not supported. Did you mean {}?" .format(blade, self.bitmap_as_tuple(bitmap)) ) bitmaps.append(bitmap) return BasisBladeOrder(bitmaps)
[docs] def order_as_tuples(self, ordering: BasisBladeOrder) -> List[Tuple[IdT]]: """ Represent an ordering with these ids. This is the inverse of :meth:`order_from_tuples`. >>> ids = BasisVectorIds(['x', 'y']) >>> ids.order_as_tuples(BasisBladeOrder([0b00, 0b10, 0b11, 0b01])) [(), ('y',), ('x', 'y'), ('x',)] """ return [self.bitmap_as_tuple(b) for b in ordering.index_to_bitmap]
[docs] @classmethod def ordered_integers(cls, n: int, *, first_index: int = 1) -> 'BasisVectorIds[int]': """ Create a set of `n` sequential integers as ids, starting from `first_index`. """ # special type is an optimization return _OrderedIntegerBasisVectorIds(n, first_index=first_index)
[docs] def augmented_with(self, n: int) -> 'BasisVectorIds': """ Return a new copy with `n` new ids at the end. """ value = list(self.values) next_id = max(value) + 1 value += list(range(next_id, next_id + n)) return BasisVectorIds(value)
def __repr__(self) -> str: return '{}({!r})'.format(type(self).__name__, self.values) def __reduce__(self): return __class__, (self.values,)
class _OrderedIntegerBasisVectorIds(BasisVectorIds[int]): def __init__(self, n, first_index=1): self._n = n self._first_index = first_index super().__init__(range(first_index, first_index + n)) def augmented_with(self, n): return _OrderedIntegerBasisVectorIds(self._n + n, first_index=self._first_index) def __repr__(self): if self._first_index == 1: return 'BasisVectorIds.ordered_integers({})'.format(self._n) else: return 'BasisVectorIds.ordered_integers({}, first_index={})'.format(self._n, self._first_index) def __reduce__(self): if self._first_index == 1: return __class__, (self._n,) else: return __class__, (self._n, self._first_index) def layout_short_name(layout) -> Optional[str]: """ helper to get the short name of a layout """ if hasattr(layout, '__name__') and '__module__' in layout.__dict__: return "{l.__module__}.{l.__name__}".format(l=layout) return None