Matrix

このセクションでは二次二値変数多項式に対応する行列クラスについて説明します。

二次二値多項式の行列表現

二次二値変数多項式の行列表現を次のように上三角行列で定義します。

バイナリ二次多項式

\[ \begin{align}\begin{aligned}f &= \sum_{i < j}{Q_{i,j} q_i q_j} + \sum_{i}{Q_{i,i} q_i} \quad \left(q_i \in \left\{ 0, 1\right\} \right)\\ &= q^{\mathrm{T}} Q q\end{aligned}\end{align} \]
\[\begin{split}Q = \left(\begin{array}{ccccc} Q_{0,0} \\ & \ddots & & \LARGE Q_{i,j} \\ & & Q_{i,i} \\ & \huge 0 & & \ddots \\ & & & & \end{array}\right)\end{split}\]

イジング二次多項式

\[ \begin{align}\begin{aligned}f &= \sum_{i < j}{J_{i,j} s_i s_j} + \sum_{i}{h_i s_i} \quad \left(s_i \in \left\{ -1, +1\right\} \right)\\ &= s^{\mathrm{T}} J s - \mathrm{Tr}J + s^{\mathrm{T}} \cdot \operatorname{diag} J\end{aligned}\end{align} \]
\[\begin{split}J = \left(\begin{array}{ccccc} h_{0} \\ & \ddots & & \LARGE J_{i,j} \\ & & h_{i} \\ & \huge 0 & & \ddots \\ & & & & \end{array}\right)\end{split}\]

上記 \(Q\)\(J\) を表す行列クラスとして下記が提供されています。

BinaryMatrixIsingMatrix はそれぞれ変数がバイナリ変数 \(\left\{0, 1\right\}\) とイジング変数 \(\left\{-1, 1\right\}\) の行列を表します。

Note

BinaryIntMatrixIsingIntMatrix は行列要素を整数値に制限したい場合に使用します。計算途中においても整数に限定されるため意図しない結果になることがあります。そのため通常は実数値を扱える BinaryMatrixIsingMatrix を推奨します。

行列クラスの構築

行列クラスは次のように size を指定すると、size \(\times\) size の零行列として構築されます (以後 BinaryMatrix を例にしていますがイジング含め他の行列クラスでも同様です)。

from amplify import BinaryMatrix

m = BinaryMatrix(3)
>>> m
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

対角項と非対角項は二次多項式において、それぞれ二次の係数と一次の係数に対応します。

コンストラクタ引数に同じ行列クラスのオブジェクトを与えるとコピーされます。

from amplify import BinaryMatrix

m1 = BinaryMatrix(3)
m2 = BinaryMatrix(m1)
>>> m2
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

リスト与えて初期値として行列クラスを構築することも出来ます。行列要素は、上三角部分か全要素を row major で与えます。

一次元リストの場合は行列サイズを指定する必要があります。

from amplify import BinaryMatrix
import numpy as np

m1 = BinaryMatrix(3, [1.0, 2.0, 3.0, 4.0, 5.0, 6.0])
m2 = BinaryMatrix(3, [1.0, 2.0, 3.0, 0.0, 4.0, 5.0, 0.0, 0.0, 6.0])
>>> m1
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m2
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]

二次元リストを与える場合は行列サイズが自動的に決定されます。

from amplify import BinaryMatrix
import numpy as np

m1 = BinaryMatrix([[1.0, 2.0, 3.0], [4.0, 5.0], [6.0]])
m2 = BinaryMatrix([[1.0, 2.0, 3.0], [0.0, 4.0, 5.0], [0.0, 0.0, 6.0]])
>>> m1
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m2
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]

行列の演算子

行列オブジェクトに対する操作で最も重要なのが要素アクセスです。次のような二次二値多項式に対応する行列を作成します。

\[f = q_0 q_1 - q_1 q_2 - 2 q_0 + q_2\]
from amplify import BinaryMatrix

m = BinaryMatrix(3)
m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
>>> m
[[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]]

m[i, j] 要素の値が \(q_i q_j\) の係数に対応しています。上三角行列なので \(i \le j\) となることに注意してください。行列の下三角部分にはアクセスできません。

その他、行列オブジェクト同士や定数との間に、等価・加法・減法・乗法・除法に対応する演算子が定義されています。それぞれの複合代入演算も可能です。

from amplify import BinaryMatrix

m1 = BinaryMatrix(3)

m1[0, 1] = 1
m1[1, 2] = -1
m1[0, 0] = -2
m1[2, 2] = 1

m2 = BinaryMatrix(m1)
>>> m1 == m2
True
>>> m1 == [[-2, 1, 0], [0, 0, -1], [0, 0, 1]]
True
>>> m1 + m2
[[-4, 2, 0],
 [0, 0, -2],
 [0, 0, 2]]
>>> m1 - m2
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
>>> m1 * 2
[[-4, 2, 0],
 [0, 0, -2],
 [0, 0, 2]]
>>> m1 / 2
[[-1, 0.5, 0],
 [0, 0, -0.5],
 [0, 0, 0.5]]

行列クラスのメソッド

行列の評価

行列オブジェクトを二次二値多項式と解釈しベクトルを用いて下記の式に従い評価します。

バイナリ二次多項式

\[f = q^{\mathrm{T}} Q q\]

イジング二次多項式

\[f = s^{\mathrm{T}} J s - \mathrm{Tr}J + s^{\mathrm{T}} \cdot \operatorname{diag} J\]

リストや numpy.ndarray をベクトルとして扱えます。

from amplify import BinaryMatrix
import numpy

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
>>> m
[[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]]
>>> m.evaluate([1, 0, 1])
-1.0

サイズの変更

行列オブジェクトのサイズの拡大縮小を行います。拡大時には拡大要素が \(0\) 要素で埋められ、縮小時には切り捨てられます。

from amplify import BinaryMatrix

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
>>> m
[[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]]
m.resize(6)
>>> m
[[-2, 1, 0, 0, 0, 0],
 [0, 0, -1, 0, 0, 0],
 [0, 0, 1, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0]]

Note

このメソッドは破壊的です

行列のサイズ

行列オブジェクトのサイズを取得します。

from amplify import BinaryMatrix

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
>>> m.size()
3

バイナリ行列への変換

イジング行列からバイナリ行列へ変換します。変換後のバイナリ行列と定数項のタプルで返却されます。

from amplify import IsingMatrix

m = IsingMatrix(3)

m[0, 0] = -0.75
m[0, 1] = 0.25
m[1, 2] = -0.25
m[2, 2] = 0.25
>>> m.to_BinaryMatrix()
([[-2, 1, 0],
 [0, 0, -1],
 [0, 0, 1]], 0.5)

イジング行列への変換

バイナリ行列からイジング行列へ変換します。変換後のイジング行列と定数項のタプルで返却されます。

from amplify import BinaryMatrix

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
>>> m.to_IsingMatrix()
([[-0.75, 0.25, 0],
 [0, 0, -0.25],
 [0, 0, 0.25]], -0.5)

二次多項式への変換

行列オブジェクトから対応する多項式クラスへ変換します。

from amplify import BinaryMatrix

m = BinaryMatrix(3)

m[0, 0] = -2
m[0, 1] = 1
m[1, 2] = -1
m[2, 2] = 1
>>> m.to_Poly()
q_0 q_1 - q_1 q_2 - 2.000000 q_0 + q_2

変換元の行列クラスと変換先の多項式クラスの対応関係は次の通りです。

行列クラス

多項式クラス

BinaryMatrix

BinaryPoly

IsingMatrix

IsingPoly

BinaryIntMatrix

BinaryIntPoly

IsingIntPoly

IsingIntPoly

NumPy 連携

NumPy 行列と行列クラスとの相互変換を行うことが可能です。

numpy.ndarray から行列クラスを構築します。

from amplify import BinaryMatrix
import numpy as np

a1 = np.array([1.0, 2.0, 3.0, 4.0, 5.0, 6.0])
m1 = BinaryMatrix(3, a1)
a2 = np.array([1.0, 2.0, 3.0, 0.0, 4.0, 5.0, 0.0, 0.0, 6.0])
m2 = BinaryMatrix(3, a2)
a3 = np.array([[1.0, 2.0, 3.0], [0.0, 4.0, 5.0], [0.0, 0.0, 6.0]])
m3 = BinaryMatrix(a3)
>>> m1
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m2
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m3
[[1, 2, 3],
 [0, 4, 5],
 [0, 0, 6]]
>>> m1 == a3
True
>>> m2 == a3
True
>>> m3 == a3
True

行列クラスから numpy.ndarray に変換します。

from amplify import BinaryMatrix
import numpy as np

a1 = np.array([[1.0, 2.0, 3.0], [0.0, 4.0, 5.0], [0.0, 0.0, 6.0]])
m1 = BinaryMatrix(a)
a2 = m1.to_numpy()
>>> a2
[[1. 2. 3.]
 [0. 4. 5.]
 [0. 0. 6.]]
>>> type(a2).__name__
ndarray