1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
r""" A Library to represent multivariate polynomials
Overview
========
TODO
Terminology
===========
Herein we will describe the terminology used to talk about polynomials, both in
their mathematical sense as well as their representation in code. Most terms
should already be well known to the reader, and the purpose ir rather to remove
any ambiguities.
Variable, Monomial, Term, Entry, and Coefficient
------------------------------------------------
From a mathematical perspective this library describes objects from
:math:`\mathbb{R}^{n\times m} [x_1, x_2, \ldots, x_k]`, where
:math:`\mathbb{R}^{n\times m}` is the set of matrices with real entries and
:math:`x_i` are called *variables*. The simplest concrete example is
:math:`\mathbb{R}[x]`, the set of scalar univariate polynomials for example
.. math::
p(x) = x^2 + 2x + 3 \in \mathbb{R}[x].
A scalar multivariate polynomial could be for example:
.. math::
p(x, y) = x^2 + 2 xy^4 + y + 5 \in \mathbb{R}[x, y].
A *monomial* is a product powers of variables, in the example above
:math:`xy^4` or :math:`x^2`. Note that :math:`1` is also a monomial, the
constant monomial, since it is a product of variables to the zeroth power. In
front of a monomial there is a scalar *coefficient* and we call *term* a
monomial with its coefficient. In code we index a polynomial term using
:py:class:`mdpoly.index.PolyIndex`.
To provide an example of the most general case consider :math:`P(x, y) \in
\mathbb{R}^{2 \times 3} [x, y]`, a matrix of polynomials:
.. math::
P(x, y) = \begin{bmatrix}
3 x^2 + y & y + 1 & 0 \\
y^5 + 8 xy & x + y & 2 y^3 \\
\end{bmatrix}
\in \mathbb{R}^{2 \times 3}[x, y].
Since we are dealing with matrices, we say that at the *entry* with row 1 and
column 1 there is a polymial `x^2 + y`. It is important to note that in
mathematics it is customary to start indices at 1, whereas in software
programming at 0. We will index rows and columns starting at 0 in
:py:class:`mdpoly.index.MatrixIndex`.
Expression
----------
Within the code, we will often call something like :math:`x^2 + 1` and
*expression* (for example :py:class:`mdpoly.abc.Expr` or
:py:class:`mdpoly.expressions.poly.PolyExpr`) instead of polynomial.
Expressions are more general and can include any mathematical operation. Of
course in the end and expression should result in a polynomial.
Decision Variables, Program
---------------------------
This package also contains a module :py:mod:`mdpoly.sos` for sum-of-square
polynomials, which involves mathematical programming (optimization). Now,
because of this fact we have to resolve the following ambiguity: consider the
polynomial
.. math::
p = a^2 x + b x^2 + y \in \mathbb{R}[x, y, a, b].
TODO: difference between variables and decision / optimization variables.
Parameters
----------
From the field of parametric programming we borrow the term *parameter* to mean
a constant that is specified at a later time. Think of physical / design
constants that are subject to change (or are computed by another process) and
should not be hard-coded, but rather only given names.
However, unlike in the discipline parametric programming we may not leave the
parameter unspecified before solving the optimization problem (yet). This is
because the theory of parametric semi-definite programming is still very, very
far from developed (compared to say, parametric LPs).
Representation
--------------
TODO: data structure(s) that represent the polynomial
"""
# internal classes imported with underscore because
# they should not be exposed to the end users
from .index import (Shape as _Shape)
from .expressions import (WithOps as _WithOps)
from .leaves import (PolyConst as _PolyConst, PolyVar as _PolyVar, PolyParam as _PolyParam,
MatConst as _MatConst, MatVar as _MatVar, MatParam as _MatParam)
from .state import State as _State
from typing import Self, Iterable, Type, TypeVar
from dataclasses import dataclass
# ┏━╸╻ ╻┏━┓┏━┓┏━┓╺┳╸ ┏━┓┏━┓ ╻┏━┓
# ┣╸ ┏╋┛┣━┛┃ ┃┣┳┛ ┃ ┣━┫┗━┓╺━╸┃┗━┓
# ┗━╸╹ ╹╹ ┗━┛╹┗╸ ╹ ╹ ╹┗━┛ ╹┗━┛
Shape = _Shape
State = _State
# ╻ ╻┏━┓┏━┓┏━┓┏━┓┏━╸┏━┓┏━┓
# ┃╻┃┣┳┛┣━┫┣━┛┣━┛┣╸ ┣┳┛┗━┓
# ┗┻┛╹┗╸╹ ╹╹ ╹ ┗━╸╹┗╸┗━┛
WithExtT = TypeVar("WithExtT", bound=_WithOps)
# FIXME: move out of this file
class FromHelpers:
@classmethod
def from_names(cls, comma_separated_names: str, strip: bool =True) -> Iterable[Self]:
""" Generate scalar variables from comma separated list of names """
names: Iterable = comma_separated_names.split(",")
if strip:
names = map(str.strip, names)
yield from map(cls, names)
@classmethod
def from_extension(cls, name, ext: Type[WithExtT]) -> WithExtT:
return ext(expr=cls(name).expr)
@dataclass
class Constant(_WithOps, FromHelpers):
""" Constant values """
def __init__(self, *args, expr=None, **kwargs):
# FIXME: make less ugly
if not expr:
_WithOps.__init__(self, expr=_PolyConst(*args, **kwargs))
else:
_WithOps.__init__(self, expr=expr)
@dataclass
class Variable(_WithOps, FromHelpers):
""" Polynomial Variable """
def __init__(self, *args, expr=None, **kwargs):
if not expr:
_WithOps.__init__(self, expr=_PolyVar(*args, **kwargs))
else:
_WithOps.__init__(self, expr=expr)
@dataclass
class Parameter(_WithOps, FromHelpers):
""" Parameter that can be substituted """
def __init__(self, *args, expr=None, **kwargs):
if not expr:
_WithOps.__init__(self, expr=_PolyParam(*args, **kwargs))
else:
_WithOps.__init__(self, expr=expr)
def __hash__(self):
return hash((self.__class__.__qualname__, hash(self.unwrap())))
class MatrixConstant(_WithOps):
""" Matrix constant """
class MatrixVariable(_WithOps):
""" Matrix Polynomial Variable """
class MatrixParameter(_WithOps):
""" Matrix Parameter """
|
