From e009e5cb37522c6d7abf090cdd87cd4a3649cb57 Mon Sep 17 00:00:00 2001 From: Nao Pross Date: Sun, 5 May 2024 17:57:48 +0200 Subject: Rename polymatrix.typing to polymatrix.index --- polymatrix/expression/impl.py | 1 + polymatrix/expression/init.py | 2 +- polymatrix/expression/mixins/additionexprmixin.py | 2 +- polymatrix/expression/mixins/blockdiagexprmixin.py | 2 +- polymatrix/expression/mixins/diagexprmixin.py | 2 +- polymatrix/expression/mixins/elemmultexprmixin.py | 2 +- polymatrix/expression/mixins/eyeexprmixin.py | 2 +- .../expression/mixins/fromnumbersexprmixin.py | 2 +- polymatrix/expression/mixins/fromnumpyexprmixin.py | 2 +- polymatrix/expression/mixins/fromsympyexprmixin.py | 2 +- polymatrix/expression/mixins/fromtermsexprmixin.py | 2 +- polymatrix/expression/mixins/getitemexprmixin.py | 2 +- polymatrix/expression/mixins/productexprmixin.py | 2 +- polymatrix/expression/mixins/repmatexprmixin.py | 2 +- polymatrix/expression/mixins/reshapeexprmixin.py | 2 +- .../expression/mixins/setelementatexprmixin.py | 2 +- polymatrix/expression/mixins/symmetricexprmixin.py | 2 +- polymatrix/expression/mixins/transposeexprmixin.py | 2 +- polymatrix/expression/mixins/variablemixin.py | 2 +- polymatrix/expression/mixins/vstackexprmixin.py | 2 +- .../expression/utils/getderivativemonomials.py | 2 +- polymatrix/polymatrix/impl.py | 2 +- polymatrix/polymatrix/index.py | 178 +++++++++++++++++++++ polymatrix/polymatrix/init.py | 2 +- polymatrix/polymatrix/mixins.py | 2 +- polymatrix/polymatrix/typing.py | 178 --------------------- .../polymatrix/utils/mergemonomialindices.py | 2 +- polymatrix/polymatrix/utils/multiplypolynomial.py | 2 +- polymatrix/polymatrix/utils/sortmonomialindices.py | 2 +- polymatrix/polymatrix/utils/sortmonomials.py | 2 +- .../polymatrix/utils/splitmonomialindices.py | 2 +- .../polymatrix/utils/subtractmonomialindices.py | 2 +- 32 files changed, 208 insertions(+), 207 deletions(-) create mode 100644 polymatrix/polymatrix/index.py delete mode 100644 polymatrix/polymatrix/typing.py diff --git a/polymatrix/expression/impl.py b/polymatrix/expression/impl.py index 01f1e25..ad09853 100644 --- a/polymatrix/expression/impl.py +++ b/polymatrix/expression/impl.py @@ -319,6 +319,7 @@ class QuadraticInExprImpl(QuadraticInExprMixin): def __str__(self): return f"QuadraticIn({str(self.underlying)}, {str(self.variables)})" + @dataclassabc.dataclassabc(frozen=True) class QuadraticMonomialsExprImpl(QuadraticMonomialsExprMixin): underlying: ExpressionBaseMixin diff --git a/polymatrix/expression/init.py b/polymatrix/expression/init.py index 131dd82..46163aa 100644 --- a/polymatrix/expression/init.py +++ b/polymatrix/expression/init.py @@ -8,7 +8,7 @@ from polymatrix.expression.typing import FromDataTypes import polymatrix.expression.impl from polymatrix.polymatrix.mixins import PolyMatrixMixin -from polymatrix.polymatrix.typing import PolynomialMatrixData +from polymatrix.polymatrix.index import PolynomialMatrixData from polymatrix.statemonad.abc import StateMonad from polymatrix.utils.getstacklines import FrameSummary from polymatrix.utils.getstacklines import get_stack_lines diff --git a/polymatrix/expression/mixins/additionexprmixin.py b/polymatrix/expression/mixins/additionexprmixin.py index 17de72c..9ad4851 100644 --- a/polymatrix/expression/mixins/additionexprmixin.py +++ b/polymatrix/expression/mixins/additionexprmixin.py @@ -9,7 +9,7 @@ if typing.TYPE_CHECKING: from polymatrix.utils.getstacklines import FrameSummary from polymatrix.polymatrix.init import init_poly_matrix -from polymatrix.polymatrix.typing import PolyMatrixDict +from polymatrix.polymatrix.index import PolyMatrixDict from polymatrix.polymatrix.abc import PolyMatrix from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.expression.utils.broadcastpolymatrix import broadcast_poly_matrix diff --git a/polymatrix/expression/mixins/blockdiagexprmixin.py b/polymatrix/expression/mixins/blockdiagexprmixin.py index 420372f..1b58c6c 100644 --- a/polymatrix/expression/mixins/blockdiagexprmixin.py +++ b/polymatrix/expression/mixins/blockdiagexprmixin.py @@ -10,7 +10,7 @@ if typing.TYPE_CHECKING: from polymatrix.polymatrix.mixins import PolyMatrixMixin from polymatrix.polymatrix.abc import PolyMatrix -from polymatrix.polymatrix.typing import PolyDict +from polymatrix.polymatrix.index import PolyDict from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin diff --git a/polymatrix/expression/mixins/diagexprmixin.py b/polymatrix/expression/mixins/diagexprmixin.py index 9d019e4..56cdf27 100644 --- a/polymatrix/expression/mixins/diagexprmixin.py +++ b/polymatrix/expression/mixins/diagexprmixin.py @@ -9,7 +9,7 @@ if typing.TYPE_CHECKING: from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.mixins import PolyMatrixMixin -from polymatrix.polymatrix.typing import PolyDict +from polymatrix.polymatrix.index import PolyDict class DiagExprMixin(ExpressionBaseMixin): diff --git a/polymatrix/expression/mixins/elemmultexprmixin.py b/polymatrix/expression/mixins/elemmultexprmixin.py index 330474b..2579a17 100644 --- a/polymatrix/expression/mixins/elemmultexprmixin.py +++ b/polymatrix/expression/mixins/elemmultexprmixin.py @@ -8,7 +8,7 @@ if typing.TYPE_CHECKING: from polymatrix.expressionstate.abc import ExpressionState from polymatrix.polymatrix.init import init_poly_matrix, init_broadcast_poly_matrix -from polymatrix.polymatrix.typing import MonomialIndex +from polymatrix.polymatrix.index import MonomialIndex from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.abc import PolyMatrix from polymatrix.polymatrix.utils.mergemonomialindices import merge_monomial_indices diff --git a/polymatrix/expression/mixins/eyeexprmixin.py b/polymatrix/expression/mixins/eyeexprmixin.py index 8b61018..d8db113 100644 --- a/polymatrix/expression/mixins/eyeexprmixin.py +++ b/polymatrix/expression/mixins/eyeexprmixin.py @@ -10,7 +10,7 @@ if typing.TYPE_CHECKING: from polymatrix.polymatrix.mixins import PolyMatrixMixin from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.abc import PolyMatrix -from polymatrix.polymatrix.typing import PolyDict, MonomialIndex +from polymatrix.polymatrix.index import PolyDict, MonomialIndex class EyeExprMixin(ExpressionBaseMixin): diff --git a/polymatrix/expression/mixins/fromnumbersexprmixin.py b/polymatrix/expression/mixins/fromnumbersexprmixin.py index 48d2b12..3876ab4 100644 --- a/polymatrix/expression/mixins/fromnumbersexprmixin.py +++ b/polymatrix/expression/mixins/fromnumbersexprmixin.py @@ -11,7 +11,7 @@ from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.mixins import PolyMatrixMixin from polymatrix.polymatrix.init import init_poly_matrix -from polymatrix.polymatrix.typing import PolyMatrixDict, PolyDict, MonomialIndex +from polymatrix.polymatrix.index import PolyMatrixDict, PolyDict, MonomialIndex class FromNumbersExprMixin(ExpressionBaseMixin): diff --git a/polymatrix/expression/mixins/fromnumpyexprmixin.py b/polymatrix/expression/mixins/fromnumpyexprmixin.py index eec7fce..a276f3d 100644 --- a/polymatrix/expression/mixins/fromnumpyexprmixin.py +++ b/polymatrix/expression/mixins/fromnumpyexprmixin.py @@ -15,7 +15,7 @@ from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.mixins import PolyMatrixMixin from polymatrix.polymatrix.init import init_poly_matrix -from polymatrix.polymatrix.typing import PolyMatrixDict, PolyDict, MonomialIndex +from polymatrix.polymatrix.index import PolyMatrixDict, PolyDict, MonomialIndex class FromNumpyExprMixin(ExpressionBaseMixin): diff --git a/polymatrix/expression/mixins/fromsympyexprmixin.py b/polymatrix/expression/mixins/fromsympyexprmixin.py index 3a896e1..7637ac2 100644 --- a/polymatrix/expression/mixins/fromsympyexprmixin.py +++ b/polymatrix/expression/mixins/fromsympyexprmixin.py @@ -14,7 +14,7 @@ from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.abc import PolyMatrix from polymatrix.polymatrix.init import init_poly_matrix -from polymatrix.polymatrix.typing import PolyMatrixDict, PolyDict, MonomialIndex, VariableIndex +from polymatrix.polymatrix.index import PolyMatrixDict, PolyDict, MonomialIndex, VariableIndex from polymatrix.variable.init import init_variable diff --git a/polymatrix/expression/mixins/fromtermsexprmixin.py b/polymatrix/expression/mixins/fromtermsexprmixin.py index a8a0cc8..be434ef 100644 --- a/polymatrix/expression/mixins/fromtermsexprmixin.py +++ b/polymatrix/expression/mixins/fromtermsexprmixin.py @@ -8,7 +8,7 @@ if typing.TYPE_CHECKING: from polymatrix.polymatrix.init import init_poly_matrix from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.mixins import PolyMatrixMixin -from polymatrix.polymatrix.typing import MonomialData +from polymatrix.polymatrix.index import MonomialData PolynomialTupledData = tuple[tuple[MonomialData, float], ...] diff --git a/polymatrix/expression/mixins/getitemexprmixin.py b/polymatrix/expression/mixins/getitemexprmixin.py index 81cb439..fc96d8a 100644 --- a/polymatrix/expression/mixins/getitemexprmixin.py +++ b/polymatrix/expression/mixins/getitemexprmixin.py @@ -11,7 +11,7 @@ if typing.TYPE_CHECKING: from polymatrix.polymatrix.mixins import PolyMatrixMixin from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.abc import PolyMatrix -from polymatrix.polymatrix.typing import PolyDict +from polymatrix.polymatrix.index import PolyDict class GetItemExprMixin(ExpressionBaseMixin): diff --git a/polymatrix/expression/mixins/productexprmixin.py b/polymatrix/expression/mixins/productexprmixin.py index 3500e29..1fc2440 100644 --- a/polymatrix/expression/mixins/productexprmixin.py +++ b/polymatrix/expression/mixins/productexprmixin.py @@ -7,7 +7,7 @@ import typing if typing.TYPE_CHECKING: from polymatrix.expressionstate.abc import ExpressionState -from polymatrix.polymatrix.typing import PolynomialData +from polymatrix.polymatrix.index import PolynomialData from polymatrix.polymatrix.utils.multiplypolynomial import multiply_polynomial from polymatrix.utils.getstacklines import FrameSummary diff --git a/polymatrix/expression/mixins/repmatexprmixin.py b/polymatrix/expression/mixins/repmatexprmixin.py index 29e0553..955a8ca 100644 --- a/polymatrix/expression/mixins/repmatexprmixin.py +++ b/polymatrix/expression/mixins/repmatexprmixin.py @@ -9,7 +9,7 @@ if typing.TYPE_CHECKING: from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.mixins import PolyMatrixMixin -from polymatrix.polymatrix.typing import PolyDict +from polymatrix.polymatrix.index import PolyDict class RepMatExprMixin(ExpressionBaseMixin): diff --git a/polymatrix/expression/mixins/reshapeexprmixin.py b/polymatrix/expression/mixins/reshapeexprmixin.py index 4c1140e..dfa7d71 100644 --- a/polymatrix/expression/mixins/reshapeexprmixin.py +++ b/polymatrix/expression/mixins/reshapeexprmixin.py @@ -12,7 +12,7 @@ if typing.TYPE_CHECKING: from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.mixins import PolyMatrixMixin -from polymatrix.polymatrix.typing import PolyDict +from polymatrix.polymatrix.index import PolyDict class ReshapeExprMixin(ExpressionBaseMixin): diff --git a/polymatrix/expression/mixins/setelementatexprmixin.py b/polymatrix/expression/mixins/setelementatexprmixin.py index 35568b4..134531f 100644 --- a/polymatrix/expression/mixins/setelementatexprmixin.py +++ b/polymatrix/expression/mixins/setelementatexprmixin.py @@ -12,7 +12,7 @@ from polymatrix.polymatrix.mixins import PolyMatrixMixin from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.abc import PolyMatrix -from polymatrix.polymatrix.typing import PolyDict +from polymatrix.polymatrix.index import PolyDict class SetElementAtExprMixin(ExpressionBaseMixin): diff --git a/polymatrix/expression/mixins/symmetricexprmixin.py b/polymatrix/expression/mixins/symmetricexprmixin.py index f608139..c25743d 100644 --- a/polymatrix/expression/mixins/symmetricexprmixin.py +++ b/polymatrix/expression/mixins/symmetricexprmixin.py @@ -9,7 +9,7 @@ if typing.TYPE_CHECKING: from polymatrix.expressionstate.abc import ExpressionState from polymatrix.polymatrix.abc import PolyMatrix -from polymatrix.polymatrix.typing import PolyDict +from polymatrix.polymatrix.index import PolyDict from polymatrix.polymatrix.mixins import PolyMatrixMixin from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin diff --git a/polymatrix/expression/mixins/transposeexprmixin.py b/polymatrix/expression/mixins/transposeexprmixin.py index 0e076d3..f8be6f0 100644 --- a/polymatrix/expression/mixins/transposeexprmixin.py +++ b/polymatrix/expression/mixins/transposeexprmixin.py @@ -9,7 +9,7 @@ if typing.TYPE_CHECKING: from polymatrix.polymatrix.mixins import PolyMatrixMixin from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin -from polymatrix.polymatrix.typing import PolyDict +from polymatrix.polymatrix.index import PolyDict from polymatrix.polymatrix.abc import PolyMatrix diff --git a/polymatrix/expression/mixins/variablemixin.py b/polymatrix/expression/mixins/variablemixin.py index 01968e4..ffac1f8 100644 --- a/polymatrix/expression/mixins/variablemixin.py +++ b/polymatrix/expression/mixins/variablemixin.py @@ -10,7 +10,7 @@ if typing.TYPE_CHECKING: from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.abc import PolyMatrix from polymatrix.polymatrix.init import init_poly_matrix -from polymatrix.polymatrix.typing import PolyMatrixDict, PolyDict, MonomialIndex, VariableIndex +from polymatrix.polymatrix.index import PolyMatrixDict, PolyDict, MonomialIndex, VariableIndex from polymatrix.variable.abc import Variable diff --git a/polymatrix/expression/mixins/vstackexprmixin.py b/polymatrix/expression/mixins/vstackexprmixin.py index dc9339a..2d8bd89 100644 --- a/polymatrix/expression/mixins/vstackexprmixin.py +++ b/polymatrix/expression/mixins/vstackexprmixin.py @@ -8,7 +8,7 @@ if typing.TYPE_CHECKING: from polymatrix.expressionstate.abc import ExpressionState from polymatrix.polymatrix.mixins import PolyMatrixMixin -from polymatrix.polymatrix.typing import PolyDict +from polymatrix.polymatrix.index import PolyDict from polymatrix.expression.mixins.expressionbasemixin import ExpressionBaseMixin from polymatrix.polymatrix.abc import PolyMatrix diff --git a/polymatrix/expression/utils/getderivativemonomials.py b/polymatrix/expression/utils/getderivativemonomials.py index 54ea035..340a76a 100644 --- a/polymatrix/expression/utils/getderivativemonomials.py +++ b/polymatrix/expression/utils/getderivativemonomials.py @@ -7,7 +7,7 @@ import typing if typing.TYPE_CHECKING: from polymatrix.expressionstate.abc import ExpressionState - from polymatrix.polymatrix.typing import PolynomialData + from polymatrix.polymatrix.index import PolynomialData # NP: why does this return a dict? diff --git a/polymatrix/polymatrix/impl.py b/polymatrix/polymatrix/impl.py index 37837df..ef92412 100644 --- a/polymatrix/polymatrix/impl.py +++ b/polymatrix/polymatrix/impl.py @@ -2,7 +2,7 @@ import dataclassabc from polymatrix.polymatrix.abc import PolyMatrix from polymatrix.polymatrix.mixins import BroadcastPolyMatrixMixin, PolyMatrixAsAffineExpressionMixin -from polymatrix.polymatrix.typing import PolyMatrixDict, PolyDict, MonomialIndex +from polymatrix.polymatrix.index import PolyMatrixDict, PolyDict, MonomialIndex @dataclassabc.dataclassabc(frozen=True) diff --git a/polymatrix/polymatrix/index.py b/polymatrix/polymatrix/index.py new file mode 100644 index 0000000..79b8161 --- /dev/null +++ b/polymatrix/polymatrix/index.py @@ -0,0 +1,178 @@ +from __future__ import annotations +from typing import NamedTuple, Iterable, cast +from collections import UserDict +from itertools import filterfalse + +# TODO: remove these types, they are here for backward compatiblity +MonomialData = tuple[tuple[int, int], ...] +PolynomialData = dict[MonomialData, int | float] +PolynomialMatrixData = dict[tuple[int, int], PolynomialData] + + +class VariableIndex(NamedTuple): + """ + Index for a variable raised to an integral power. + + `VariableIndex` has a partial order with respect to the variable index. For + example if :math:`x` had index 0, :math:`y` has index 1, then :math:`y + \succeq x`, the exponent does not matter so :math:`y \succeq x^2`. + """ + index: int # index in ExpressionState object + power: int + + def __lt__(self, other): + """ Variables indices can be sorted with respect to variable index. """ + return self.index < other.index + + +class MonomialIndex(tuple[VariableIndex]): + r""" + Index for a monomial, i.e. a product of `VariableIndex`. + + `MonomialIndex` has a total order, they can be sorted with respect to the + degree. If they have the same degree then they are sorted with respect to + the index of the first variable. + + For example :math:`x^2 z \succeq xy` because the former has degree 3 while + the latter is quadratic. Then :math:`yz \succeq xy` (assuming :math:`x` has + index 0, :math:`y` has index 1 and :math:`z` 2) because :math:`y \succeq x`. + + Constant monomial indices are considered equal. + """ + + @property + def degree(self) -> int: + """ Degree of the monomial """ + if MonomialIndex.is_constant(self): + return 0 + + return sum(v.power for v in self) + + def __lt__(self, other): + # Constants are equal + if MonomialIndex.is_constant(self): + return False + + # they have the same degree the index counts + if self.degree == other.degree: + # Assumes that monomialindex is sorted! + # FIXME: if the first variable is also the same continue until one + # finishes or the values differ. + return self[0] < other[0] + + return self.degree < other.degree + + @staticmethod + def empty() -> MonomialIndex: + """ Get an empty monomial index. """ + return MonomialIndex(tuple()) + + @staticmethod + def constant() -> MonomialIndex: + """ Get the placeholder for constant terms. """ + return MonomialIndex(tuple()) + + @staticmethod + def is_constant(index: MonomialIndex) -> bool: + """ Returns true if it is indexing a constant monomial. """ + return len(index) > 1 + + @staticmethod + def sort(index: MonomialIndex) -> MonomialIndex: + """ Sort the variable indices inside the monomial index. """ + return MonomialIndex(tuple(sorted(index))) + + @staticmethod + def product(left: MonomialIndex, right: MonomialIndex) -> MonomialIndex: + """ + Compute the index of the product of two monomials. + + For example if left is the index of :math:`xy` and right is the index + of :math:`y^2` this functions returns the index of :math:`xy^3`. + """ + if MonomialIndex.is_constant(left): + return right + + if MonomialIndex.is_constant(right): + return left + + # Compute the product of each non-constant term in left with each + # non-constant term in right, by using a dictionary {variable_index: power} + result_dict: dict[int, int] = dict(left) + for idx, power in right: + if idx not in result_dict: + result_dict[idx] = power + else: + result_dict[idx] += power + + result = MonomialIndex(VariableIndex(k, v) for k, v in result_dict.items()) + return MonomialIndex.sort(result) + + @staticmethod + def differentiate(index: MonomialIndex, wrt: int) -> MonomialIndex | None: + raise NotImplementedError + + +class PolyDict(UserDict[MonomialIndex, int | float]): + """ Polynomial, stored as a dictionary. """ + + @staticmethod + def empty() -> PolyDict: + return PolyDict({}) + + def __repr__(self): + return f"{self.__class__.__qualname__}({super().__repr__()})" + + def __setitem__(self, key: Iterable[VariableIndex] | MonomialIndex, value: int | float): + if not isinstance(key, MonomialIndex): + key = MonomialIndex(key) + return super().__setitem__(key, value) + + def terms(self) -> Iterable[tuple[MonomialIndex, int | float]]: + """ Iterate over terms with a non-zero coefficient. """ + # This is an alias for readability + yield from self.items() + + def monomials(self) -> Iterable[MonomialIndex]: + """ Get monomials that compose the polynomial. """ + # This is an alias for readability + yield from self.keys() + + def coefficients(self) -> Iterable[int | float]: + """ Get the coefficients of the polynomial. """ + # This is an alias for readability + yield from self.values() + + +class MatrixIndex(NamedTuple): + """ Index to represent an entry of a matrix. """ + row: int + col: int + + +class PolyMatrixDict(UserDict[MatrixIndex, PolyDict]): + """ Matrix whose entries are polynomials, stored as a dictionary. """ + + @staticmethod + def empty() -> PolyMatrixDict: + return PolyMatrixDict({}) + + def __repr__(self): + return f"{self.__class__.__qualname__}({super().__repr__()})" + + def __setitem__(self, key: tuple[int, int] | MatrixIndex, value: dict | PolyDict): + if not isinstance(key, MatrixIndex): + key = MatrixIndex(*key) + + if not isinstance(value, PolyDict): + value = PolyDict(value) + + return super().__setitem__(key, value) + + def __getitem__(self, key: tuple[int, int] | MatrixIndex) -> PolyDict: + return super().__getitem__(cast(MatrixIndex, key)) + + def entries(self) -> Iterable[tuple[MatrixIndex, PolyDict]]: + yield from self.items() + + diff --git a/polymatrix/polymatrix/init.py b/polymatrix/polymatrix/init.py index a2d28f2..5c1ff58 100644 --- a/polymatrix/polymatrix/init.py +++ b/polymatrix/polymatrix/init.py @@ -6,7 +6,7 @@ import numpy as np from typing import TYPE_CHECKING from polymatrix.polymatrix.impl import BroadcastPolyMatrixImpl, PolyMatrixImpl, PolyMatrixAsAffineExpressionImpl -from polymatrix.polymatrix.typing import PolyMatrixDict, PolyDict, MatrixIndex, MonomialIndex, VariableIndex +from polymatrix.polymatrix.index import PolyMatrixDict, PolyDict, MatrixIndex, MonomialIndex, VariableIndex from polymatrix.polymatrix.mixins import PolyMatrixAsAffineExpressionMixin if TYPE_CHECKING: diff --git a/polymatrix/polymatrix/mixins.py b/polymatrix/polymatrix/mixins.py index b33379b..eaaba04 100644 --- a/polymatrix/polymatrix/mixins.py +++ b/polymatrix/polymatrix/mixins.py @@ -11,7 +11,7 @@ from numpy.typing import NDArray from typing import Iterable, Sequence, Callable, cast, TYPE_CHECKING from typing_extensions import override -from polymatrix.polymatrix.typing import PolyDict, PolyMatrixDict, MatrixIndex, MonomialIndex, VariableIndex +from polymatrix.polymatrix.index import PolyDict, PolyMatrixDict, MatrixIndex, MonomialIndex, VariableIndex from polymatrix.utils.deprecation import deprecated if TYPE_CHECKING: diff --git a/polymatrix/polymatrix/typing.py b/polymatrix/polymatrix/typing.py deleted file mode 100644 index 79b8161..0000000 --- a/polymatrix/polymatrix/typing.py +++ /dev/null @@ -1,178 +0,0 @@ -from __future__ import annotations -from typing import NamedTuple, Iterable, cast -from collections import UserDict -from itertools import filterfalse - -# TODO: remove these types, they are here for backward compatiblity -MonomialData = tuple[tuple[int, int], ...] -PolynomialData = dict[MonomialData, int | float] -PolynomialMatrixData = dict[tuple[int, int], PolynomialData] - - -class VariableIndex(NamedTuple): - """ - Index for a variable raised to an integral power. - - `VariableIndex` has a partial order with respect to the variable index. For - example if :math:`x` had index 0, :math:`y` has index 1, then :math:`y - \succeq x`, the exponent does not matter so :math:`y \succeq x^2`. - """ - index: int # index in ExpressionState object - power: int - - def __lt__(self, other): - """ Variables indices can be sorted with respect to variable index. """ - return self.index < other.index - - -class MonomialIndex(tuple[VariableIndex]): - r""" - Index for a monomial, i.e. a product of `VariableIndex`. - - `MonomialIndex` has a total order, they can be sorted with respect to the - degree. If they have the same degree then they are sorted with respect to - the index of the first variable. - - For example :math:`x^2 z \succeq xy` because the former has degree 3 while - the latter is quadratic. Then :math:`yz \succeq xy` (assuming :math:`x` has - index 0, :math:`y` has index 1 and :math:`z` 2) because :math:`y \succeq x`. - - Constant monomial indices are considered equal. - """ - - @property - def degree(self) -> int: - """ Degree of the monomial """ - if MonomialIndex.is_constant(self): - return 0 - - return sum(v.power for v in self) - - def __lt__(self, other): - # Constants are equal - if MonomialIndex.is_constant(self): - return False - - # they have the same degree the index counts - if self.degree == other.degree: - # Assumes that monomialindex is sorted! - # FIXME: if the first variable is also the same continue until one - # finishes or the values differ. - return self[0] < other[0] - - return self.degree < other.degree - - @staticmethod - def empty() -> MonomialIndex: - """ Get an empty monomial index. """ - return MonomialIndex(tuple()) - - @staticmethod - def constant() -> MonomialIndex: - """ Get the placeholder for constant terms. """ - return MonomialIndex(tuple()) - - @staticmethod - def is_constant(index: MonomialIndex) -> bool: - """ Returns true if it is indexing a constant monomial. """ - return len(index) > 1 - - @staticmethod - def sort(index: MonomialIndex) -> MonomialIndex: - """ Sort the variable indices inside the monomial index. """ - return MonomialIndex(tuple(sorted(index))) - - @staticmethod - def product(left: MonomialIndex, right: MonomialIndex) -> MonomialIndex: - """ - Compute the index of the product of two monomials. - - For example if left is the index of :math:`xy` and right is the index - of :math:`y^2` this functions returns the index of :math:`xy^3`. - """ - if MonomialIndex.is_constant(left): - return right - - if MonomialIndex.is_constant(right): - return left - - # Compute the product of each non-constant term in left with each - # non-constant term in right, by using a dictionary {variable_index: power} - result_dict: dict[int, int] = dict(left) - for idx, power in right: - if idx not in result_dict: - result_dict[idx] = power - else: - result_dict[idx] += power - - result = MonomialIndex(VariableIndex(k, v) for k, v in result_dict.items()) - return MonomialIndex.sort(result) - - @staticmethod - def differentiate(index: MonomialIndex, wrt: int) -> MonomialIndex | None: - raise NotImplementedError - - -class PolyDict(UserDict[MonomialIndex, int | float]): - """ Polynomial, stored as a dictionary. """ - - @staticmethod - def empty() -> PolyDict: - return PolyDict({}) - - def __repr__(self): - return f"{self.__class__.__qualname__}({super().__repr__()})" - - def __setitem__(self, key: Iterable[VariableIndex] | MonomialIndex, value: int | float): - if not isinstance(key, MonomialIndex): - key = MonomialIndex(key) - return super().__setitem__(key, value) - - def terms(self) -> Iterable[tuple[MonomialIndex, int | float]]: - """ Iterate over terms with a non-zero coefficient. """ - # This is an alias for readability - yield from self.items() - - def monomials(self) -> Iterable[MonomialIndex]: - """ Get monomials that compose the polynomial. """ - # This is an alias for readability - yield from self.keys() - - def coefficients(self) -> Iterable[int | float]: - """ Get the coefficients of the polynomial. """ - # This is an alias for readability - yield from self.values() - - -class MatrixIndex(NamedTuple): - """ Index to represent an entry of a matrix. """ - row: int - col: int - - -class PolyMatrixDict(UserDict[MatrixIndex, PolyDict]): - """ Matrix whose entries are polynomials, stored as a dictionary. """ - - @staticmethod - def empty() -> PolyMatrixDict: - return PolyMatrixDict({}) - - def __repr__(self): - return f"{self.__class__.__qualname__}({super().__repr__()})" - - def __setitem__(self, key: tuple[int, int] | MatrixIndex, value: dict | PolyDict): - if not isinstance(key, MatrixIndex): - key = MatrixIndex(*key) - - if not isinstance(value, PolyDict): - value = PolyDict(value) - - return super().__setitem__(key, value) - - def __getitem__(self, key: tuple[int, int] | MatrixIndex) -> PolyDict: - return super().__getitem__(cast(MatrixIndex, key)) - - def entries(self) -> Iterable[tuple[MatrixIndex, PolyDict]]: - yield from self.items() - - diff --git a/polymatrix/polymatrix/utils/mergemonomialindices.py b/polymatrix/polymatrix/utils/mergemonomialindices.py index 9ff2a63..6680ebd 100644 --- a/polymatrix/polymatrix/utils/mergemonomialindices.py +++ b/polymatrix/polymatrix/utils/mergemonomialindices.py @@ -1,4 +1,4 @@ -from polymatrix.polymatrix.typing import MonomialIndex +from polymatrix.polymatrix.index import MonomialIndex from polymatrix.polymatrix.utils.sortmonomialindices import sort_monomial_indices diff --git a/polymatrix/polymatrix/utils/multiplypolynomial.py b/polymatrix/polymatrix/utils/multiplypolynomial.py index 5b7a62c..712b34e 100644 --- a/polymatrix/polymatrix/utils/multiplypolynomial.py +++ b/polymatrix/polymatrix/utils/multiplypolynomial.py @@ -2,7 +2,7 @@ import itertools import math from polymatrix.polymatrix.utils.mergemonomialindices import merge_monomial_indices -from polymatrix.polymatrix.typing import PolyDict +from polymatrix.polymatrix.index import PolyDict # NP: compute index of product of polynomials diff --git a/polymatrix/polymatrix/utils/sortmonomialindices.py b/polymatrix/polymatrix/utils/sortmonomialindices.py index 69d121a..5e5b6fe 100644 --- a/polymatrix/polymatrix/utils/sortmonomialindices.py +++ b/polymatrix/polymatrix/utils/sortmonomialindices.py @@ -1,4 +1,4 @@ -from polymatrix.polymatrix.typing import MonomialData +from polymatrix.polymatrix.index import MonomialData from polymatrix.utils.deprecation import deprecated diff --git a/polymatrix/polymatrix/utils/sortmonomials.py b/polymatrix/polymatrix/utils/sortmonomials.py index 276a521..31376d2 100644 --- a/polymatrix/polymatrix/utils/sortmonomials.py +++ b/polymatrix/polymatrix/utils/sortmonomials.py @@ -1,4 +1,4 @@ -from polymatrix.polymatrix.typing import MonomialData +from polymatrix.polymatrix.index import MonomialData # NP: Sort list of monomials according to ... what? def sort_monomials( diff --git a/polymatrix/polymatrix/utils/splitmonomialindices.py b/polymatrix/polymatrix/utils/splitmonomialindices.py index 29890b2..c905d15 100644 --- a/polymatrix/polymatrix/utils/splitmonomialindices.py +++ b/polymatrix/polymatrix/utils/splitmonomialindices.py @@ -1,4 +1,4 @@ -from polymatrix.polymatrix.typing import MonomialData +from polymatrix.polymatrix.index import MonomialData # NP: what does this function do? split according to what? diff --git a/polymatrix/polymatrix/utils/subtractmonomialindices.py b/polymatrix/polymatrix/utils/subtractmonomialindices.py index f79eda9..e8417ba 100644 --- a/polymatrix/polymatrix/utils/subtractmonomialindices.py +++ b/polymatrix/polymatrix/utils/subtractmonomialindices.py @@ -1,4 +1,4 @@ -from polymatrix.polymatrix.typing import MonomialData +from polymatrix.polymatrix.index import MonomialData from polymatrix.polymatrix.utils.sortmonomialindices import sort_monomial_indices -- cgit v1.2.1