選択多項式

2022-06-01

• AMRG 演算を一般化したらそうなった.
  • 暗号文から要素を選択するのでそう名付けた

線形変換は置換を表す?

• ex. $L:[x_1,x_2,x_3]\mapsto [x_3,x_2,x_1]$ は置換にすると

$$\tau =\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right),U=\left(\begin{array}{ccc}0& 0& 1\\ 0& 1& 0\\ 1& 0& 0\end{array}\right),L(x)=\mathrm{LinTrans}(U,x)$$

• では $L:[x_1,x_2,x_3]\mapsto [x_1+x_2,x_2+x_3,x_3+x_1]$ は?

$$U=\left(\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\\ 1& 0& 1\end{array}\right),L(x)=\mathrm{LinTrans}(U,x)$$

• 内積は $x=[x_1,x_2,x_3],y=[y_1,y_2,y_3]$ に対し, $[{\sum }_i{x}_i\cdot y_i,0,0]$
• 置換では表現できない

演算を多項式表現する

定義(選択多項式)

暗号文の組 $X:=X_1,X_2\cdots =\{x_{1,1},x_{1,2},\cdots \},\{x_{2,1},\cdots \},\cdots$ に対し, 演算をした結果は多変数多項式のベクトル $\mathbb{R}[X{]}^N$ で表される.

• Add: $P,Q\in \mathbb{R}[X{]}^N,R=P\oplus Q$
• Mult: $P,Q\in \mathbb{R}[X{]}^N,R=P\odot Q$
• Rotl: $P\in \mathbb{R}[X{]}^N,R=P\ll k$

命題

選択多項式 $P\in \mathbb{R}[X]$ は1つ以上の選択多項式 $P_i\in \mathbb{R}[X]$ の線形結合に分解出来る

定義(自明な分解)

選択多項式 $P\in \mathbb{R}[X]$ は単位選択多項式(=1つだけの非零要素からなる1変数1次の選択多項式) $U\in \mathbb{R}[X]$ の線形結合に出来る.

例: $[x_1\cdot x_2,x_1]=([x_1,0]\odot [x_2,0])\oplus [0,x_1]$

分解と演算コスト

• ex. $[x_1+x_2+x_3,0,0]$ の分解を考える.

自明な分解

$$\begin{array}{rl}& =[x_1,0,0]\oplus [x_2,0,0]\oplus [x_3,0,0]\\ & =get\_index(x,1)\oplus get\_index(x,2)\oplus get\_index(x,3)\end{array}$$

ops: 2 add, 3 mult, 6rots

最適な分解

$$\begin{array}{rl}& =([x_1,x_2,x_3]\oplus [x_2,x_3,x_1]\oplus [x_3,x_1,x_2])\odot [1,0,0]\\ & =(x\oplus (x\ll 1)\oplus (x\ll 2))\odot [1,0,0]\end{array}$$

ops: 2 add, 1 mult, 3rots

最適な分解の構成の仕方について(WIP)

• 多項式が与えられた時に最適な分解を探索するのは困難そう
  • 定式化をしてソルバで解くことは恐らく出来る
• 自明な分解をしてからコストの低い結合をする?
• 前ページの例のように0が含まれていると厄介

命題

置換 $\tau$ に対して置換行列 $T$ が決まるように, 多変多項式である選択多項式行列 $\mu \in \mathbb{R}[\mathcal{X}{]}^N$ に対しても置換マスク行列 $M\in {\mathbb{R}}^{N\times N},C\in {\mathbb{R}}^N,M\cdot v+C$ がある

• 関係ないが, グレブナー基底 ?

  • www.math.kobe-u.ac.jp/publications/rlm9.pdf

• 例えば置換マスク行列の足し合わせとかは同じ要素を足すとかあるので要素はuint(=インデックス) or 0(=使わない)ではなく多項式だと良い? 定数倍や定数演算も表せるので

  • ex. [x_1, x_2] |-> [3x_1 + x_2]
    • それって 線形作用素 では?
      • 有界線形作用素 - わかりたい日記

• ループを伴う演算を置換マスク行列 で表した後に最適な演算(=最も演算コストが低いinstructions)に分解

  • これが難しそう, 置換の分解の拡張になりそう
    • rotl は連続巡回置換 (l l+1, ... n, 1, ... l-1) ってこと?
      • 回転量が最小になるような置換の分解の仕方は一意ではない気がする
      • Cyclic permutation - Wikipedia これの連続になってる版に関する知見がほしい
        • On the Permutations Generated by Cyclic Shift
    • 逆変換は逆向きの書き換え規則を作ってeggにやらせるのが丸いか

とりあえずソルバを使って最適解を求めてみる

• 目的関数: 多項式ベクトルのコストだと思ったけど多項式から一意に決まらない -> 各演算に対応した単位行列?の分解に対してのコスト
  • 疎行列の分解に対応している?
  • マスク行列が重み, 定数項がバイアスと見ればperceptronの活性化関数ない版に見える気もする, 気のせいかも

問題

多変数多項式ベクトル $V\in \mathbb{R}[X{]}^N$ が与えられた時に演算コストが最小になるような多変数多項式ベクトルの和の分解 ${\sum }_{i=0}^c{W}_i,W_i\in \mathbb{R}[X{]}^N$ を計算したい.

2022-05-30

• 関連研究探し, 「vector of multivariate polynomial decomposition」とかで調べても全然出てこない. 多変数多項式を並べるということをしないらしい.
• もう少し抽象化できれば数学のテーマとしてあるんだろうか? 全くわからない
• https://www.jstage.jst.go.jp/article/sicetr1965/30/5/30_5_519/_pdf
  • 制御理論 の論文だが, 多変数多項式の行列で要素同士の共通因数みたいな話が出てきた. 少し近いかも しれない

まずは多項式が線形な場合のみ考える?.

• 線形作用素に対するスペクトル分解というのがあるらしい

  • www.math.s.chiba-u.ac.jp/~nagisa/lecture04/fa4.pdf

• 2022-06-10

  • やはり, 計算グラフの最適化の方が近いか

定式化

$[N]:=\{0,\cdots N-1\}$, $\text{same}$
選択多項式 $P$ の分解 $\{P_0,P_1,\cdots ,P_{K-1}\}$ は

$$\begin{array}{rlrlrlr}& \underset{P_i\in P}{\mathrm{minimize}}& & \Phi (P_i)+K\ast {}^{\forall }i.\#[{}^{\forall }j,P_i^j=0]\ast c_{\text{add}}& & & \\ & \text{s.t}& & \sum _k^K{P}_k^j=P^j& & & {}^{\forall }j\in [N]\\ & & & \underset{P_i\in P}{\bigwedge }{C}_{\text{all\_same}}(P_i)⊻C_{\text{diag\_same}}(P_i)⊻C_{\text{single\_nonzero}}(P_i)⊻C_{\text{all\_zero}}(P_i)& & & {}^{\forall }i\in [K]\end{array}$$

ただし,

$$\Phi (p)=\{\begin{array}{ll}0& (\text{same}(P_i)=[N])\\ c_{\text{rot}}& (\text{same}(P_i)=\text{diag}({}^{\exists }u))\\ c_{\text{mask}}+c_{\text{rot}}& (|\text{same}(P_i)|=1)\end{array}$$

制約,

$$C_{\text{all\_same}}(p)={}^{\forall }j,p^j=1$$ $$C_{\text{diag\_same}}(p)={}^{\exists !}u,\{\begin{array}{l}{}^{\forall }j\in \text{diag}(u),p^j\ne 0\\ {}^{\forall }\bar{j}\notin \text{diag}(u),p^{\bar{j}}=0\end{array}$$ $$C_{\text{single\_nonzero}}(p)=\{\begin{array}{l}{}^{\exists !}j,P_j\ne 0\\ {}^{\forall }\bar{j}\in [N]\backslash \{j\},p^{\bar{j}}=0\end{array}$$

ソルバ実装

現状, 回転に対応していない, ベクトルから多項式にする.

• Q: E-graphによる自明な分解から結合は可能? todo

a0 a1   b0 b1   a0 a1   b0 b3   
a2 a3 . b2 b3 = a3 a2 . b2 b1 + 

get_index

get_index(A: vec, i: uint) 
<=> A * mask({i}) << i

例: get_index(A, 1)

$$T_{\mathrm{get},1}=\left(\begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right),get\_index(A,1)=T_{\mathrm{get},1}\cdot A=[v_2,0,0,0]$$

set_index

set_index(A: vec, i: usize, v: uint)
<=> (A * mask(inv({i})) + ((all(v) * mask({i})) >> i)

naive

rep i d
	rep j d
		rep k d
			c[i][j] += a[i][k] * b[k][j]
c

into dot-product

fn matmul (a b) =
	(rep i d
		(rep j d
			c[i][j] = a[Li] . b[Cj]
		)
	)

col

• 行列としてみたとき, $k$ 列目を先頭 $d$ 個に並べる

# cのk列目(=[d * i + k])を先頭d個(=[i])に並べる
fn col(v k) =
	(rep + i d
		rotl(v[d * i + k], (d * i + k - i))
	)

置換行列

• 値が不要な所は0

$${\tau }_{\mathrm{col},\mathrm{k}}=\left(\begin{array}{cccccc}1& 2& 3& \cdots & d+1& \cdots \\ k& d+k& 2d+k& \cdots & 0& \cdots \end{array}\right),$$

ex. col(A, 1)

$${\tau }_{\mathrm{col},1}=\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 4& \ast & \ast \end{array}\right),T_{\mathrm{col},1}=\left(\begin{array}{cccc}0& 0& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 0\end{array}\right)$$

が定まり,

$$A:=\left[\begin{array}{cccc}{v}_1& v_2& v_3& v_4\end{array}\right]$$ $$\mathrm{col}(A,1)=T_{\mathrm{col},1}\cdot A=\left[\begin{array}{cccc}{v}_2& v_4& 0& 0\end{array}\right]$$

line

• 行列の $k$ 行目を取得して先頭 $d$ 個に並べる

line(A, k)
<=>
A * mask({ kd, ..., kd + d }) << kd

$${\tau }_{\mathrm{line},k}=\left(\begin{array}{cccccc}0& \cdots & dk& \cdots & (d+1)\ast k& \cdots \\ 0& \cdots & 1& \cdots & 0& \cdots \end{array}\right),$$ $${\tau }_{\mathrm{line},1}=\left(\begin{array}{cccc}1& 2& 3& 4\\ 0& 0& 1& 2\end{array}\right),T_{\mathrm{line},1}=\left(\begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 0& 0\\ 1& 0& 0& 0\\ 0& 1& 0& 0\end{array}\right)$$

内積

fn dp (va vb) =
	(rep + i n
		(get_index va i) * (get_index vb i)
	)

$$(A,B)=\sum _{i=0}^N{T}_{\mathrm{get},i}\cdot A\odot T_{\mathrm{get},i}\cdot B$$

行列積

fn matmul (a b) =
	let r = (const 0)
	(rep %i then d
		(rep %j then d
			let a_line_i = rotl(a .* mask(d * i, d * (i + 1)), d * i)
	        let b_col_j = col_vec(b, j)
			// r[i * d + j] = <a_i | b_j>
	        set_index(r, i * d + j, dp(a_line_i, b_col_j))
		)
	)

• verified

$$\begin{array}{rl}r& :=0\\ \mathrm{matmul}(A,B)& =\sum _{i=0}^d\sum _{j=0}^{d}set\_index(\mathbf{r},id+j,(\mathrm{line}(A,i),\mathrm{col}(B,j)))\\ & =\sum _{i=0}^d\sum _{j=0}^{d}set\_index(\mathbf{r},id+j,\sum _k^N(T_{\mathrm{get},k}\circ T_{\mathrm{line},i})\cdot A\odot (T_{\mathrm{get},k}\circ T_{\mathrm{col},j})\cdot B)\end{array}$$

• ここで $(i,j)\mapsto id+j$ は単射より
  • $\sum set\_index(r,i,f(i))$ <=> $\sum \mathrm{rotl}(f(i),id+j)$
    • 単射なのでマスクして回転する必要が無い位の意味

$$\begin{array}{rl}(A\cdot B{)}_{i,j}& =\sum _k^N(T_{\mathrm{get},k}\circ T_{\mathrm{line},i})(A)\odot (T_{\mathrm{get},k}\circ T_{\mathrm{col},j})(B)\end{array}$$ $$A\cdot B=\sum _{k=1}^{d-1}(\sigma \circ {\varphi }^k)(A)\odot (\tau \circ {\psi }^k)(B)$$ $$\begin{array}{rl}A\cdot B& =\sum _{k=1}^{d-1}(m_{i,j\to i,i+j}\circ m_{i,j\to i,j+k})(A)\odot (m_{i,j\to i+j,j}\circ m_{i+k,j})(B)\\ & =\end{array}$$

get_index(k) = $(k\to 0)$
line(k) = $(kd+i\to i)$
col(k) = $(id+k\to i)$

具体例: $d=2$

写像で表す.

a = [1, 2, 3, 4], b = [5, 6, 7, 8]

naive

# (kd + i → i) . (id + k → i)
dp := line(i) . col(j) = [*, *, 0, 0]

# (0..d +→ 0)
dp_sum = sum_{d} dp << i = [*, *, 0, 0]
dp_sum_mask = dp_sum * mask(id + j) = [*, 0, 0, 0]

# (0 → id + j)
dp_sum_mask_rot = dp_sum_mask >> (id + j) = [0, *, 0, 0]
matmul(a, b)[id + j] = dp_sum_mask_rot

->lintrans

# (kd + i → i) . (id + k → i) devided by k
dp := line(i) . col(j) = [*, *, 0, 0]
dp_k=0 :=