Einstein toplamlarını en uygun şekilde derlemek

Question

Einstein toplamı; numpy, torch, tensorflow, vb. Gibi tensör kitaplıklarında yolunu bulan tensör işlemlerini ifade etmenin uygun bir yoludur.

Esnekliği, üç matrisin çarpımını göstermemizi sağlar, $X$, $Y$, $Z$ boyutların $(a,b)$, $(b,c)$, $(c,d)$ gibi

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

Bununla birlikte, yukarıdaki gibi bir şey derlenir

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_]

Bu yerel, matrislerin boyutunda ikinci dereceden

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

Yalnızca kübik olur.

Performans için daha akıllı bir uygulama hayal edebileceğimiz kabaca üç optimizasyon düzeyi vardır einsum.

1. Bir tensörü ayrıştırın $(x_1, \ldots, x_n)$ tensör çiftlerinin einsumuna $x_1, x_2$, $e(x_1, x_2), x_3$, vb. hesaplama süresini optimize etmek için.

2. Bu çiftleri mantıklı bir şekilde seçmek (bu klasik bir dinamik programlama problemidir) ve uygun aracı tensörleri oluşturmak için ilişkiselliğe (uygun olduğu yerde) güvenin.

3. Spesifik tensör hesaplaması için Strassen benzeri formülleri keşfedin

3 açıkça erişilemez görünürken, 1 ve 2 tam olarak makul derecede basit bir algoritma ile ulaşılabilir gibi görünüyor. Bu tür algoritmalar genel einstein toplamaları için biliniyor mu? Çalışıldılar mı?

Answer 1

Optimal kasılma sırasını bulmanın genel problemi NP-zordur [1]. Kısaltma sırasını yaklaşık olarak optimize etme ve ilgili referansları içeren yeni bir makale [2] 'dir.

[1] Chi-Chung, Lam, P. Sadayappan ve Rephael Wenger. "Paralel yürütme için indirgeme ile çok boyutlu döngü sınıfının optimize edilmesi hakkında." Paralel İşlem Mektupları 7.02 (1997): 157-168.

[2] Schindler, Frank ve Adam Jermyn. "Tensör ağı daralma sıralaması için algoritmalar." Makine Öğrenimi: Bilim ve Teknoloji (2020).