Kompleksitas kekuatan matriks komputasi

Saya tertarik dalam menghitung $n$ 'th kekuatan dari matriks . Misalkan kita memiliki algoritma untuk perkalian matriks yang berjalan dalam waktu . Kemudian, orang dapat dengan mudah menghitung dalam waktu. Apakah mungkin untuk menyelesaikan masalah ini dalam kompleksitas waktu yang lebih rendah? $n\times n$ $A$ $\mathcal{O}(M(n))$ $A^n$ $\mathcal{O}(M(n)\log(n))$

Entri matriks dapat, secara umum, berasal dari semiring tetapi Anda dapat mengambil struktur tambahan jika itu membantu.

Catatan: Saya mengerti bahwa dalam komputasi umum dalam waktu akan memberikan algoritma untuk eksponensial. Tetapi, sejumlah masalah menarik berkurang ke kasus khusus dari matriks eksponensial di mana m = , dan saya tidak dapat membuktikan hal yang sama tentang masalah yang lebih sederhana ini. $A^m$ $o(M(n)\log(m))$ $o(\log m)$ $\mathcal O(n)$

algorithms complexity-theory time-complexity computer-algebra Shitikanth
sumber

apa saja entri dari matriks? Bilangan bulat?

Kaveh

Entri dapat, secara umum, berasal dari semiring tetapi Anda dapat mengambil struktur tambahan jika itu membantu.

Shitikanth

Saya tidak bisa mendapatkan pengurangan dari multiplasi menjadi kuadrat dari metode yang diusulkan di atas (yaitu menggunakan

). Namun, menggunakan

berfungsi. Namun, ini hanya memberikan

(A \pm B)^{2}

$(A\pm B)^2$

{(\begin{array}{cc} 0 & A \\ B & 0 \end{array})}^{2}

$\left( \begin{array}{cc} 0 & A \\ B & 0 \end{array} \right)^2$

Ω (M (n))

$\Omega(M(n))$ pada komputasi

A^{n}

$A^n$

Shitikanth

Jawaban:

Jika matriks dapat didiagonalisasi maka pengambilan daya ke- dapat dilakukan dalam waktu $n$ di mana adalah waktu untuk diagonalize .

HAI (D (n) + n catatan n)

$O(D(n)+ n\log n)$

D (n)

$D(n)$

A

$A$

Untuk melengkapi detailnya, jika dengan diagonal , maka $A=P^{-1}DP$ $D$

{SEBUAH}^{n} = (P^{- 1} D P)^{n} = P^{- 1} D^{n} P

$A^n = (P^{-1}DP)^n = P^{-1}D^nP$

dan dapat dihitung dengan hanya mengambil setiap elemen diagonal (masing-masing nilai eigen ) ke kekuatan ke- . $D^n$ $A$ $n$

Ran G.
sumber

Bahkan jika matriks dapat didiagonalisasi, algoritma yang paling dikenal untuk komposisi eigend mengambil

waktu. Dengan menggunakan algoritma Coppersmith-Winograd, kami sudah memiliki algoritma

untuk komputasi

O (n^{3})

$O(n^3)$

O (n^{2.3727} \log (m))

$O(n^{2.3727}\log(m))$

A^{m}

$A^m$

Shitikanth

(1) Batas waktu yang Anda kutip bukan oleh Coppersmith-Winograd (seperti yang mungkin Anda ketahui). (2) Semua algoritma dari bentuk itu hanya berfungsi untuk cincin; mereka tidak berfungsi untuk semiring umum (seperti yang Anda izinkan dalam pertanyaan Anda).

Ryan Williams

Satu jalan keluar yang baik adalah Singular Value Decomposition SVD . Diberikan matriks nyata dari peringkat penuh , SVD membaginya menjadi mana adalah matriks diagonal, dalam waktu . Dengan sifat-sifat SVD, , sehingga hanya matriks diagonal yang perlu di-eksponensial, dan ini dapat dilakukan dalam $n\times n$ $A$ $A=U\Sigma U^T$ $\Sigma$ $O(n^3)$ $A^m = U \Sigma^m U^T$ $O(n\log m)$ waktu. Melakukan perkalian akhir membutuhkan , jadi kami memiliki semua operasi . $U \times \Sigma^m \times U^T$ $O(n^{2.3727})$ $O(n^3 + n \log m)$

Perbarui setelah komentar Intinya adalah bahwa begitu SVD ditemukan, daya apa pun hanya membutuhkan waktu untuk dihitung dengan algoritma CW Anda sendiri. Tapi ini bukan pertanyaan Anda. Jika benar-benar ada algoritma , itu akan segera dikonversi menjadi algoritma untuk bilangan bulat. Saya curiga tidak ada yang seperti itu. $O(n^{2.3727}+n \log m)$ $o(M(n)\log(m))$ $o(\log n)$

PKG
sumber

Karena algoritma Coppersmith-Winograd menemukan produk dari dua matriks dalam waktu

, kami sudah memiliki algoritma

untuk menghitung

. Saya tertarik mengetahui apakah ini dapat diperbaiki tanpa memerlukan algoritma multiplikasi matriks yang lebih baik, terutama untuk

O (n^{2.3727})

$O(n^{2.3727})$

O (n^{2.3727} \log (m))

$O(n^{2.3727}\log(m))$

A^{m}

$A^m$

m = O (n)

$m=O(n)$

Shitikanth

A = U Σ U^{⊤}

$A = U \Sigma U^\top$

V \neq U^{⊤}

$V \ne U^\top$

n

$n$

m

$m$

n = 1

$n=1$

O (M (1) \log m

$O(M(1)\log m$

A^{m}

$A^m$

@Shitikanth lihat ccrwest.org/gordon/jalg.pdf untuk survei algoritma eksponensial cepat. Secara umum, tidak mungkin untuk menggunakan lebih sedikit dari multiplikasi

\log m

$\log m$

Joe

Ini tidak jelas dari pertanyaan Anda, seperti yang dinyatakan.

PKG