Perkalian dan eksponensial rantai matriks

Jika saya memiliki dua matriks dan B , masing-masing berdimensi 1000 × 2 dan 2 × 1000 , dan ingin menghitung ( A B ) 5000 , lebih efisien untuk terlebih dahulu menulis ulang ekspresi sebagai A ( B A ) 4999 B dan baru kemudian mengevaluasi secara numerik, karena A B adalah dimensi 1000 × 1000 tetapi B A adalah dimensi 2 × 2 .$A$$B$$1000\times2$$2\times1000$$(AB)^{5000}$$A(BA)^{4999}B$$AB$$1000\times1000$$BA$$2\times2$

Saya ingin menyelesaikan versi umum masalah ini. Apakah ada algoritma yang cukup efisien (bukan kekerasan) untuk mengoptimalkan ekspresi yang mengandung:

• Variabel matriks bebas dari dimensi yang diketahui
• Produk dari subekspresi sewenang-wenang
• Subekspresi sewenang-wenang dinaikkan menjadi kekuatan alami

... sehingga dibutuhkan paling sedikit pekerjaan untuk mengevaluasi secara numerik, setelah mengganti variabel matriks bebas dengan nilai matriks konkret?

Masalah penggandaan rantai matriks adalah kasus khusus dari masalah saya.

Edit:

Ini adalah jawaban sementara. Tampaknya secara intuitif benar bagi saya, tetapi saya tidak punya bukti bahwa itu benar. Jika ternyata benar, saya masih tertarik pada buktinya. (Jika itu tidak benar, tentu saja, tolong perbaiki saya.)

Untuk setiap produk yang dinaikkan menjadi daya, katakanlah, , pertimbangkan setiap permutasi siklik faktor-faktor:$(A_1 A_2 \ldots A_k)^n$

• $(A_1 A_2 \ldots A_k)^n$
• $A_1 (A_2 \ldots A_k A_1)^{n-1} A_2 \ldots A_k$
• $A_1 A_2 (A_3 \ldots A_k A_1 A_2)^{n-1} A_3 \ldots A_k$
• ...
• $A_1 A_2 \ldots A_{k-1} (A_k A_1 A_2 \ldots A_{k-1})^{n-1} A_k$

... secara rekursif. Setiap daya dihitung menggunakan eksponensial dengan mengkuadratkan (jelas), dan semua produk lain dihitung menggunakan urutan optimal yang dikembalikan oleh algoritma penggandaan rantai matriks.

Edit:

Gagasan yang diuraikan dalam edit saya sebelumnya masih agak tidak optimal. Eksponen dengan algoritma kuadrat sebenarnya mengevaluasi ekspresi dari bentuk atau A n K , di mana K belum tentu merupakan matriks identitas. Tapi algoritma saya tidak mempertimbangkan kemungkinan menggunakan eksponensial dengan mengkuadratkan algoritma dengan K tidak sama dengan matriks identitas.$K A^n$$A^n K$$K$$K$

Penafian: Metode berikut ini belum terbukti secara optimal. Bukti informal disediakan.

Masalahnya berkurang untuk menemukan pemesanan yang paling efisien ketika mempertimbangkan kuadrat produk.

$(ABC)^{50}$$(ABC)^2$$ABCABC$$ABC$

$ABCABC$

$A(B(CA))BC$$A(B(CA))^{49}BC$

$(A_1 A_2 \cdots A_n)^m$$(A_1 A_2 \cdots A_n)^2$
$(A_1 A_2 \cdots A_n)^2$
$G$$A_1 \cdot A_2 \cdot G^{m-1} \cdot A_n$

$(AB)^n$$A$$B$$X \times Y$$Y \times X$$A$$B$

$X \times Y$
$Y \times X$
$Y \times Y$
$X \times X$

$X < Y$$Y ≤ X$

$X < Y$
$AB$$X \times X$$A$$B$$(AB)^n$

$Y ≤ X$
$BA$$Y \times Y$$A$$B$$A(BA)^{n-1}B$

$ABAB$

Menggunakan lebih banyak matriks, argumennya serupa. Mungkin bukti induktif mungkin? Gagasan umum adalah bahwa memecahkan MCM untuk kuadrat akan menemukan ukuran optimal untuk operasi dengan semua matriks yang terlibat dipertimbangkan.

Studi kasus:

julia> a=rand(1000,2);
julia> b=rand(2,1000);
julia> c=rand(1000,100);
julia> d=rand(100,1000);
julia> e=rand(1000,1000);

julia> @time (a*b*c*d*e)^30;
  0.395549 seconds (26 allocations: 77.058 MB, 1.58% gc time)

# Here I use an MCM solver to find out the optimal ordering for the square problem
julia> Using MatrixChainMultiply
julia> matrixchainmultiply("SOLVE_SQUARED", a,b,c,d,e,a,b,c,d,e)
Operation: SOLVE_SQUARED(A...) = begin  # none, line 1:
    A[1] * (((((A[2] * A[3]) * (A[4] * (A[5] * A[6]))) * (A[7] * A[8])) * A[9]) * A[10])
  end
Cost: 6800800

# Use the ordering found, note that exponentiation is applied to the group of 5 elements
julia> @time a*(((((b*c)*(d*(e*a)))^29*(b*c))*d)*e);
  0.009990 seconds (21 allocations: 7.684 MB)

# I also tried using the MCM for solving the problem directly
julia> @time matrixchainmultiply([30 instances of a,b,c,d,e]);
  0.094490 seconds (4.02 k allocations: 9.073 MB)

$A_1$$A_n$$A_i$$A_j$$O (n^3)$