Mengompilasi jumlah einstein secara optimal

Question

Penjumlahan Einstein adalah cara mudah untuk mengekspresikan operasi tensor yang telah ditemukan di library tensor seperti numpy, torch, tensorflow, dll.

Fleksibilitasnya memungkinkan kita merepresentasikan produk dari tiga matriks, $X$, $Y$, $Z$ dari dimensi $(a,b)$, $(b,c)$, $(c,d)$ sebagai

X.Y.Z = einsum('ab,bc,cd->ad',X,Y,Z)

Namun, di atas mengkompilasi sesuatu seperti

for a_ in range(a):
  for d_ in range(d):
     res[a_,d_] = 0
     for b_ in range(b):
        for c_ in range(c):
           res[a_,d_] += X[a_,b_] * Y[b_,c_] * Z[c_, d_]

Native ini adalah kuadrat dalam ukuran matriks saat melakukan

einsum('ac,cd->ad',einsum('ab,bc'->'ac', X, Y), Z)

Akan menjadi kubik.

Ada kira-kira tiga tingkat pengoptimalan yang dapat kita bayangkan sebagai implementasi yang lebih cerdas einsumuntuk dilakukan.

1. Menguraikan einsum tensor $(x_1, \ldots, x_n)$ menjadi einsum pasangan tensor $x_1, x_2$, $e(x_1, x_2), x_3$, dll untuk mengoptimalkan waktu komputasi.

2. Andalkan asosiatif (jika memungkinkan) untuk memilih pasangan tersebut dengan bijaksana (ini adalah masalah pemrograman dinamis klasik) dan buat tensor perantara yang sesuai.

3. Temukan rumus mirip Strassen untuk komputasi tensor tertentu

Meskipun 3 tampak jelas di luar jangkauan, 1 dan 2 sepertinya bisa dicapai dengan algoritme yang cukup mudah. Apakah algoritme semacam itu dikenal untuk penjumlahan einstein generik? Apakah mereka telah dipelajari?

Answer 1

Tampaknya masalah umum untuk menemukan urutan kontraksi yang optimal adalah NP-hard [1]. Makalah terbaru tentang tentang mengoptimalkan urutan kontraksi, dan berisi referensi yang relevan, adalah [2].

[1] Chi-Chung, Lam, P. Sadayappan, dan Rephael Wenger. "Tentang mengoptimalkan class loop multi-dimensi dengan pengurangan untuk eksekusi paralel." Parallel Processing Letters 7.02 (1997): 157-168.

[2] Schindler, Frank, dan Adam Jermyn. "Algoritma untuk pengurutan kontraksi jaringan tensor." Pembelajaran Mesin: Sains dan Teknologi (2020).