Determinante modulo m

Was die bekannten effiziente Algorithmen zur Berechnung einer Determinante einer Matrix mit ganzzahligen Koeffizienten sind , modulo der Ring aus den Resten . Die Zahl möglicherweise keine Primzahl, sondern zusammengesetzt (Berechnungen werden also im Ring und nicht in einem Feld ausgeführt). $\mathbb{Z}_m$ $m$ $m$

Soweit ich weiß (siehe unten), handelt es sich bei den meisten Algorithmen um Modifikationen der Gaußschen Elimination. Die Frage ist nach der Recheneffizienz dieser Verfahren.

Wenn es einen anderen Ansatz gibt, bin ich auch neugierig.

Danke im Voraus.

Aktualisieren:

Lassen Sie mich die Quelle dieser Frage erläutern. Angenommen, ist eine Primzahl. Also ist ein Feld. In diesem Fall können wir alle Berechnungen mit Zahlen unter . Wir haben also eine schöne Obergrenze für alle Operationen mit Zahlen: Addition, Multiplikation und Inversion - alle erforderlichen Operationen, um die Gaußsche Elimination auszuführen. $m$ $\mathbb{Z}_m$ $m$

Andererseits können wir für einige Zahlen keine Inversion durchführen, falls keine Primzahl ist. Wir brauchen also einige Tricks, um die Determinante zu berechnen. $m$

Und jetzt bin ich gespannt, welche Tricks es gibt und ob solche in Büchern und Papieren zu finden sind.

ds.algorithms reference-request linear-algebra comp-number-theory Valeriy Sokolov
quelle

Was meinen Sie mit "effizient"? Das Problem ist eindeutig in

P

$P$

David

Ist

eine feste Konstante? Wie ist es gegeben?

m

$m$

Michael Blondin

Was meinst du mit klein? Könnten sie unärgerlich geschrieben sein?

Michael Blondin

Ich verstehe die Frage immer noch nicht. Die Determinante einer Ganzzahlmatrix kann in Polynomzeit berechnet werden, Sie können also einfach diesen Wert modulo

. Es ist nicht erforderlich, Divisionen in

durchzuführen oder die Faktorisierung von

m

$m$

Z_{m}

$Z_m$

m

$m$

David

@ValeriySokolov: Das ist die grundlegende lineare Algebra. Schauen Sie sich zum Beispiel Problem 11.5.3 von Computational Complexity von Christos H. Papadimitriou an.

Tsuyoshi Ito

Antworten:

Wenn Sie die Faktorisierung von , können Sie modulo jedes separat berechnen und dann die Ergebnisse mit chinesischem Rest kombinieren. Wenn , dann berechne modulo $m = p_1^{e_1} \cdots p_n^{e_n}$ $p_i^{e_i}$ $e_i = 1$ $p_i^{e_i}$ ist einfach, da dies ein Bereich ist. Für größere können Sie das Hensel-Heben verwenden. $e_i$

Markus Bläser
quelle

Vielen Dank! Es ist wie etwas, was ich gesucht habe. Ist dies eine gängige Praxis für Determinanten? (Referenzen sind willkommen).

Valeriy Sokolov

Dies sind Standardtechniken aus der Computeralgebra. Schauen Sie sich die Moderne Computeralgebra von von zur Gathen und Gerhard oder ein anderes Buch zur Computeralgebra an. Für Ihr spezielles Problem siehe auch das folgende Papier von Pan, Yu & Stewart comet.lehman.cuny.edu/vpan/pdf/pan146.pdf

Markus Bläser

Es gibt einen kombinatorischen Algorithmus von Mahajan und Vinay, der über kommutative Ringe arbeitet: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html

Sasho Nikolov
quelle

Vielen Dank für Ihre Antwort mit Link zu einem sehr interessanten Artikel.

Valeriy Sokolov

Ich glaube auch, dass es effizientere Algorithmen gibt, da die Autoren dieses Artikels allgemeinere Probleme (für jeden kommutativen Ring) gelöst haben.

Valeriy Sokolov

mit "es gibt" meinst du "bekannt" oder "existieren" (wurden aber noch nicht gefunden)? es ist eine vernünftige Vermutung, aber ich bin ein wenig skeptisch, dass die Struktur des Ringes von Intigern modulo einer kleinen zusammengesetzten Zahl Ihnen all das helfen kann. Wenn ich mich irre, finde ich das interessant.

Sasho Nikolov

@ValeriySokolov um fair zu sein, da die Antwort Ihre Frage beantwortet, könnten Sie in Betracht ziehen, sie zu akzeptieren (oder wenn Sie auf möglicherweise bessere Antworten warten möchten, die nicht unvernünftig wären)

Suresh Venkat

m

$m$

O (1)

$O(1)$

O (\log m)

$O(\log m)$

O (1)

$O(1)$

$m$ $A$ $\text{det}(A)$

$\omega$ $n \times n$ $\mathbb{Z}_m$ $O(n^{\omega})$ $\mathbb{Z}_m$ multipliziert werden können (ganzzahlige Addition, Multiplikation, Exponentiation usw.). Dann,

$A\in \mathbb{Z}_m^{n \times n}$ $\text{det}(A)$ $O(n^{\omega})$ $\mathbb{Z}_m$ [1] .

Als dies 1996 geschrieben wurde, gab es keine asymptotisch schnellere Alternative (der Aufsatz erwähnt die frühere Existenz von Algorithmen mit derselben Schranke, aber ich weiß nicht, welche oder ob sie probabilistisch sind).

$m$ $m$

$O(\log^2 m)$ $O(M(\log m)\log \log m)$ $M(t)$ $t$ $\omega$

Juan Bermejo Vega
quelle

θ

$\theta$

ω

$\omega$

Vielleicht kenne ich die gebräuchlichste Schreibweise dafür nicht.

Juan Bermejo Vega

Ich denke, Sie haben Recht, ich werde es in "Mainstream" ändern

Juan Bermejo Vega