行列積から線形変換による方法への書き換え

algorithm

2022-09-11, 2022-10-27

; 1 2
; 3 4
(let a (input 4)
; 5 6
; 7 8
(let b (input 4)
(let c (const 0)
(rep i 2
  (rep j 2
    (#= c i,j (rep + 2 (* (# a i,k) (# b k,j))))
  )
)
)))

$$\begin{array}{rl}c& =\sum _{i=0}^d\sum _{j=0}^d\left(\sum _{k=0}^d{a}_{i,k}\cdot b_{k,j}\right)\cdot m_{i,j}\\ c& =\sum _{k=0}^d\sum _{i=0}^d\sum _{j=0}^d\left(\sum _{k=0}^d{a}_{i,k}\cdot b_{k,j}\right)\cdot m_{i,j}\\ & =\sum _{k=0}^d\left(\sum _{i=0}^d{a}_{0+k+i}\cdot b_{k+i}+\sum _{i=0}^d{a}_{1+k+i}\cdot b_{1+k+i}\right)\end{array}$$

todo 写像で書く書き方で書く

$i$ 行, $j$ 列に分ける

li\cj→
↓    5|7  6|8
1    x----o (k=0)
-    |    |
2    | o--|-x (k=1)
     | |  | |
3    o----x |
-      |    |
4      x----o

• diagonal でくっつける $M_u={\sum }_k(k,k+u\mathrm{mod}d)$

rep d in 2
  let m_d = fold (+) i 2
    let j = (i + d) % 2
    let line = a[i:*]
    let col = b[*:j]
    line * col

$M_0=(0,0)+(1,1)$

[ 1|  |  |  ]*[ 5|  |  |  ]  [  | 2|  |  ]*[  | 8|  |  ]
[  | 4|  |  ]*[  | 7|  |  ]  [ 3|  |  |  ]*[ 6|  |  |  ]
=
[ 5|  |  |  ][  |16|  |  ]
[  |28|  |  ][18|  |  |  ]

$M_1=(0,1)+(1,0)$

[  | 2|  |  ]*[  | 7|  |  ] [ 1|  |  |  ]*[ 6|  |  |  ]
[ 3|  |  |  ]*[ 5|  |  |  ] [  | 4|  |  ]*[  | 8|  |  ]
=
[  |14|  |  ] [ 6|  |  |  ]
[15|  |  |  ] [  |32|  |  ]

• slotに対応する所にシフトする
  • Lシフト量: $-\iota (n)+{\mathcal{D}}_u^d$

$\mathcal{D}$: diagonal flatten vector
ex.
${\mathcal{D}}_0^2$ = [0 1; 1 0]
${\mathcal{D}}_1^2$ = [1 0; 0 1]
${\mathcal{D}}_0^3$ = [0 1 2; 2 0 1; 1 2 0]
${\mathcal{D}}_1^3$ = [2 0 1; 1 2 0; 0 1 2]

rep d in 2
  let m_d = fold (+) i 2
    let j = (i + d) % 2
    let line = a[i:*]
    let col = b[*:j]
    line * col

$M_0^{\prime }=M_0\ll (0,0,-1,-3)$

[ 5|  |  |  ] [  |16|  |  ]
[  |28|  |  ] [18|  |  |  ]
<<(0, -1, -1, 0) => <<(0, -1, -2, -3) = <<(0, 0, -1, -3)
[5 |  |  |  ] [  |16|  |  ]
[  |  |28|  ] [  |  |  |18]

$M_1^{\prime }=M_1\ll (1,-1,-2,-2)$

[  |14|  |  ] [ 6|  |  |  ]
[15|  |  |  ] [  |32|  |  ]
<<(-1, 0, 0, -1) => <<(0, -1, -2, -3) = <<(1, -1, -2, -2)
[14|  |  |  ] [  | 6|  |  ]
[  |  |15|  ] [  |  |  |32]

• $M_0^{\prime }+M_1^{\prime }$

[19|22|43|50]

rep u in 2
  rep i in 2
    let j = (i + u) % 2
    # d=0: (0, 0), (1, 1)
    # d=1: (0, 1), (1, 0)
    let line = a[i:*]
    let col = b[*:j]
    c[i][j] = fold (+) k 2
      line[k] * col[k]

function join_with_u(a, b, d)
    c = zeros(d^2)
    map(u -> begin
            map(i -> begin
                    # (i, j) is orthogonally
                    j = (i + u) % d
                    al = line(a, i + 1, d)
                    bc = col(b, j + 1, d)
                    ij = pos(i + 1, j + 1, d) - 1
                    println("u = $u, ($i, $j) =$ij")
                    c[ij+1] = sum(al .* bc)
                end, 0:d-1)
        end, 0:d-1)
    c
end

とりあえずvalidなSIMDプログラムが書けた

• todo j が k に依存しているので k のループを内側に持ってこれず, 要素積を $d^3$ してしまっている