Determinante einer verallgemeinerten Vandermonde-Matrix

Die Moore-Matrix ähnelt der Vandermonde-Matrix, hat jedoch eine leicht modifizierte Definition. http://en.wikipedia.org/wiki/Moore_matrix

Was ist die Komplexität der Berechnung der Determinante einer gegebenen vollen Rang-Moore-Matrix modulo einer ganzen Zahl? $n \times n$

Kann die Moore-Determinante mit FFT-Techniken von auf für einige reduziert werden? ? $O(n^{3})$ $O(n\log^{a}n)$ $a \in \mathbb{R}_{+} \cup \{0\}$

Ist die Komplexität von Moore det modulo eine ganze Zahl und Vandermonde det gleich? Die Komplexität der Vandermonde-Determinante ist (Seite 644 im Handbuch der Theoretischen Informatik: Algorithmen und Komplexität Von Jan Leeuwen) $O(n\log^{2}n)$

Beitrag ähnlich dem aktuellen: Determinant modulo m

cc.complexity-theory algebraic-complexity T ....
quelle

Kann die Moore-Determinante sogar in O (n ^ 3) -Zeit (auf einem ganzzahligen RAM) berechnet werden?

Jeffs

@ Jɛ ﬀ E Deshalb habe ich modulo random .

N \in N

$N \in \mathbb{N}$

T ....

Übrigens, und ich bin nur neugierig, gibt es bekannte Anwendungen, die von einem solchen "superschnellen" Algorithmus profitieren würden?

Juan Bermejo Vega

@J ffE, wissen Sie zufällig, ob die Berechnung einer doppelten modularen Exponentiation über in BPP für triviales ? Weil es ein Problem ist, die Koeffizienten der Matrix zu berechnen.

ε

$\varepsilon$

N

$N$

N

$N$

Juan Bermejo Vega

Antworten:

Im Allgemeinen gibt es einen theoretischen Zeitalgorithmus zum der LU-Zerlegung einer beliebigen Matrix unter Verwendung des Coppersmith-Winograd-Algorithmus , der dann offensichtlich die Determinante ergibt (Hinzufügen der -Zeit). Es gibt jedoch ein Problem, dass der Coppersmith-Winograd-Algorithmus in der Praxis nicht als verwendbar angesehen wird. Afaik, die Leute benutzen meistens den Zeit-Strassen-Algorithmus. Verwendet Boost UBLASs lu_factorize dies nicht? $O(n^{2.376})$ $O(n)$ $O(n^{2.807})$

In Ihrem Fall sollte die Moore-Matrix erhebliche Optimierungen zulassen, da grundsätzlich jede Gaußsche Eliminierungsprozedur wie die LU-Zerlegung abstrakt durchgeführt werden kann. In der Tat finden Sie eine nette -Formel zur Berechnung der Moore-Determinante , auf die in Wikipedia verwiesen wird. Dies beweist man vermutlich, indem man einfach die LU-Zerlegung im Allgemeinen berechnet . $O(n)$

Jeff Burdges
quelle

Hallo Jeff, auf welche Referenz beziehen Sie sich für die O (n ^ 2) -Formel? Ich denke, Vandermonde det kann in O (nlogn) berechnet werden, aber ich kann keine Referenz finden. Sollte Moore det also auch in O (nlogn) sein?

T ....

Ja, ich hätte offensichtlich O (n) sagen sollen, wirklich O (n log n) für großes n.

Jeff Burdges

Hallo Jeff: Hast du eine Referenz?

T ....

@ JeffBurdges: Wenn die Laufzeit O (n log n) "für großes n" ist, dann ist die Laufzeit per Definition O (n log n), nicht O (n).

Jeffs

Ich sehe keine -Formel, auf die Wikipedia verweist. Bestenfalls sieht es aus wie .

O (n)

$O(n)$

Θ (n^{2})

$\Theta(n^2)$

Peter Taylor

Es ist wichtig, dass in der von Ihnen angegebenen Definition die Matrix in einem endlichen Feld lebt, z. B. wobei eine Primzahl ist. Auf diese Weise können Sie den Satz von Euler verwenden , um die Doppelexponentiale zu berechnen , die in der Matrix in der Zeit . Andernfalls scheint es schwierig zu sein, die Matrixkoeffizienten zu berechnen, ohne zu faktorisieren . $\mathbb{Z}_m$ $m$ $a^{q^e}\mod m$ $O(\log (mn) \; M(\log m))$

a^{q^{i}} \equiv a^{q^{i} (\mod φ (m))} (\mod m)

$a^{q^i}\equiv a^{q^i\pmod{\varphi(m)}}\pmod m$

m

$m$

Wenn eine Primzahl ist oder effizient faktorisiert werden kann, wird die Komplexität im ungünstigsten Fall von der Anzahl der Schritte dominiert, die Sie für die Matrixmultiplikation benötigen . Zum Beispiel würde der Smith-Normalform-Ansatz, den ich im Partnerbeitrag erwähnt habe, die Determinante in der Zeit berechnen, wenn Sie "slow" verwenden. Multiplikationsalgorithmen . kann als 2.373 gewählt werden. $m$ $O(n^\omega)$ $O\left( n^\omega \; \log^2m\; \log (mn) \right)$ $^*$ $\omega$

In Moore gegen Vandermonde kommt es zu einer Verlangsamung, da Sie die Koeffizienten der Matrix doppelt potenzieren müssen. Wenn Sie faktorisieren können, ist diese Verlangsamung auf nur polylogarithmisch . Wenn nicht, erhalten Sie mit dem vorgestellten Algorithmus eine Cook-Reduktion auf Double-Modular-Exponentiation für . $m$ $m$ $\mathbb{Z}_m$

Hinweis *: Mit schnelleren Algorithmen für die Ganzzahlmultiplikation können Sie durch ersetzen . $\log^2 m$ $M(\log m \log\log m)$

Update : über die Möglichkeit, . $O(n\log^a n)$

Ich habe keine eindeutige Antwort darauf, aber ich habe einige Informationen gefunden, die Ihre Suche möglicherweise verschärfen.

Algorithmen für strukturierte Matrizen, die Größen wie Determinanten in der Zeit berechnen, werden in der Literatur als "superschnell" bezeichnet. Alle bekannten "superschnellen" Algorithmen für strukturierte Matrizen (Vandermonde, Toeplitz, Hankel) scheinen auf einer gemeinsamen Eigenschaft dieser Matrizen zu beruhen, die als niedriger "Verschiebungsrang" bekannt ist. Konferenz über das erste Kapitel dieses Buches (Open-Access-Seiten) oder in diesem Artikel [ACM] , [PDF] . $O(n\log^a n)$

Nach dem, was ich gelesen habe, bei gegebener Moore-Matrix , wenn Sie die Matrizen , so finden konnten, dass die neue Matrix (oder alternativ ) hat die folgende Struktur $m\times n$ $M$ $A$ $B$ $L(M)=AM-MB$ $L(M)=M- AMB$

L (M) = \sum_{k = 1}^{r} g_{k} h_{k}^{T}

$L(M) = \sum_{k=1}^r g_k h_k^T$

Wenn der Rang klein ist (entweder konstant oder durch begrenzt ), können Sie vorhandene Techniken anwenden (siehe Kapitel 5 des Buches, open- Zugriffsseiten), um zu triangulieren und daher mit berechnen . Oben bezeichnen die , Vektoren. Wenn Sie das obige Buch nicht finden, um das Ganze zu lesen, enthält dieser Artikel auch viele Informationen zu diesen Methoden. $r>0$ $o(\text{min} \;\{m,n\})$ $M$ $\det{M}$ $O(n\log^2 n)$ $g_k$ $h_k$

Leider konnte ich keine Struktur mit niedrigem Verschiebungsrang für die Moore-Matrix finden (Vandermonde hat). Die Hauptkomplikation scheint sich hier aus der "nichtlinearen" Natur des Doppelexponentials zu ergeben. Wenn es hilft, werden die Fälle für Vandermonde, Cauchy, Toeplitz, Hankel in dem Buch herausgearbeitet.

Juan Bermejo Vega
quelle

Ich kann meine Matrix in einem Feld von char . Die Größe der Alphabete für meine beabsichtigte Anwendung ist jedoch groß. So ist von Form für einige groß genug .

3

$3$

m

$m$

3^{k}

$3^{k}$

k

$k$

T ....

Das ist in Ordnung, da Sie die Totientenfunktion von berechnen können :)

3^{k}

$3^k$

Juan Bermejo Vega

Nun, das vereinfacht die Komplexität nicht, würde ich sagen, da das Feld sehr sehr groß ist.

T ....

Dies vereinfacht die Probleme, die ich bei der Doppelexponentiation erwähne. Da , können Sie den Satz von Euler verwenden, um doppelt zu : Berechnen Sie zuerst , dann . Sie können dies in der Zeit . Unter Verwendung des Schulmultiplikationsalgorithmus ist , und Sie würden endgültige "Netto" -Kosten von das ist effizient.

φ (3^{k}) = 3^{k} - 3^{k - 1}

$\varphi(3^k)=3^k-3^{k-1}$

a^{q^{i}} \mod m

$a^{q^i}\mod m$

b = q^{i} \mod φ (3^{k})

$b=q^i\mod \varphi(3^k)$

a^{b} \mod 3^{k}

$a^b\mod 3^k$

O (\log (n 3^{k}) M (k \log 3))

$O(\log(n3^k)M(k \log3))$

M (n) = n^{2}

$M(n)=n^2$

O (n^{ω} k^{2} l o g^{2} 3 (\log n + k \log 3))

$O(n^\omega k^2 log^2 3 (\log n + k\log 3))$

Juan Bermejo Vega

Können wir durch ersetzen ? Das ist die Kostenersparnis, auf die ich neugierig bin (möglicherweise aufgrund der Matrixstruktur möglich). Mit ich nichts für meinen Zweck.

ω

$\omega$

1 + ϵ

$1 + \epsilon$

ω \geq 2

$\omega \ge 2$

T ....