3 files changed, 72 insertions, 0 deletions
diff --git a/mdpoly/sos/__init__.py b/mdpoly/sos/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/mdpoly/sos/__init__.py
diff --git a/mdpoly/sos/problem.py b/mdpoly/sos/problem.py
new file mode 100644
index 0000000..2787355
--- /dev/null
+++ b/mdpoly/sos/problem.py
@@ -0,0 +1,33 @@
+from __future__ import annotations
+from typing import TYPE_CHECKING
+
+from typing import List
+from dataclasses import dataclass
+
+from ..abc import Var, Rel
+from ..expressions import Expression
+
+if TYPE_CHECKING:
+    pass
+
+
+class OptVar(Var):
+    """ Leaf to represent an optimization variable. """
+
+
+@dataclass(frozen=True)
+class Problem:
+    """ Optimization problem. """
+    objective: Expression
+    variables: List[OptVar]
+    constraints: List[Rel]
+
+
+@dataclass(frozen=True)
+class SOSProblem(Problem):
+    ...
+
+
+@dataclass(frozen=True)
+class SOSCertProblem(Problem):
+    ...
diff --git a/mdpoly/sos/representations.py b/mdpoly/sos/representations.py
new file mode 100644
index 0000000..9261b82
--- /dev/null
+++ b/mdpoly/sos/representations.py
@@ -0,0 +1,39 @@
+from __future__ import annotations
+from typing import TYPE_CHECKING
+
+from typing import Iterable
+import cvxopt
+
+from ..abc import Repr
+
+if TYPE_CHECKING:
+    from ..index import MatrixIndex, PolyIndex, Number, Shape
+
+
+class CVXOptSparseMatrixRepr(Repr):
+    data: cvxopt.spmatrix
+
+    def __init__(self, shape: Shape):
+        self.data = cvxopt.spmatrix(0, size=shape)
+
+    def at(self, entry: MatrixIndex, term: PolyIndex) -> Number:
+        """ Access polynomial coefficient. """
+        return self.data[entry.row, entry.col]
+
+    def set(self, entry: MatrixIndex, term: PolyIndex, value: Number) -> None:
+        """ Set value of polynomial coefficient. """
+        raise NotImplementedError
+
+    def set_zero(self, entry: MatrixIndex, term: PolyIndex) -> None:
+        """ Set a coefficient to zero (delete it). """
+        raise NotImplementedError
+
+    def entries(self) -> Iterable[MatrixIndex]:
+        """ Return indices to non-zero entries of the matrix. """
+        raise NotImplementedError
+
+    def terms(self, entry: MatrixIndex) -> Iterable[PolyIndex]:
+        """ Return indices to non-zero terms in the polynomial at the given
+        matrix entry. """
+        raise NotImplementedError
+