Determinant modulo m

18

Jakie są znane skuteczne algorytmy do obliczania wyznacznikiem macierzy współczynników całkowitą o Zm , pierścień reszt modulo m . Liczba m może nie być liczbą pierwszą, lecz złożoną (więc obliczenia są wykonywane w pierścieniu, a nie w polu).

O ile mi wiadomo (czytaj poniżej), większość algorytmów jest modyfikacjami eliminacji Gaussa. Pytanie dotyczy wydajności obliczeniowej tych procedur.

Jeśli zdarzyło się, że istnieje jakieś inne podejście, jestem również ciekawy.

Z góry dziękuję.

Aktualizacja:

Pozwól, że wyjaśnię źródło tego pytania. Załóżmy, że m jest liczbą pierwszą. Więc Zm jest polem. W tym przypadku możemy wykonać wszystkie obliczenia przy użyciu liczb mniejszych niż m , więc mamy pewną górną granicę dla wszystkich operacji na liczbach: dodawanie, mnożenie i inwersja --- wszystkie potrzebne operacje, aby uruchomić eliminację Gaussa.

Z drugiej strony nie możemy wykonać inwersję dla niektórych numerów w przypadku m nie na sile. Potrzebujemy więc kilku sztuczek, aby obliczyć wyznacznik.

A teraz jestem ciekawy, jakie są znane sztuczki do wykonania tej pracy i czy można je znaleźć w książkach.

Walerij Sokołow
źródło
3
Co rozumiesz przez `` wydajny ''? Problemem jest to wyraźnie w . P.
David
2
Czy jest stałą stałą? Jak to jest podane? m
Michael Blondin
2
Co rozumiesz przez „mały”? Czy mogą być napisane jednoosobowo?
Michael Blondin
5
Nadal nie rozumiem pytania. Wyznacznik macierzy liczb całkowitych można obliczyć w czasie wielomianowym, więc możesz po prostu wziąć tę wartość modulo . Nie trzeba wykonywać podziałów w Z m ani znajdować faktoryzacji m . mZmm
David
2
@ValeriySokolov: To jest podstawowa algebra liniowa. Na przykład sprawdź problem 11.5.3 złożoności obliczeniowej autorstwa Christosa H. Papadimitriou.
Tsuyoshi Ito

Odpowiedzi:

15

Jeśli znasz faktoryzacji można obliczyć modulo każdy p e ja i oddzielnie, a następnie połączyć wyniki przy użyciu chińskiego remaindering. Jeśli e i = 1 , to obliczenie modułu p e i i jest łatwe, ponieważ jest to pole. W przypadku większych e i można użyć podnoszenia Hensel. m=p1e1pnenpieiei=1pieiei

Markus Bläser
źródło
Dziękuję Ci! To jest coś, czego szukałem. Czy jest to powszechna praktyka dla determinant? (referencje są mile widziane).
Valeriy Sokolov
6
Są to standardowe techniki z algebry komputerowej. Zajrzyj do Modern Computer Algebra autorstwa von zur Gathen i Gerharda lub innej książki o algebrze komputerowej. Aby zobaczyć konkretny problem, zobacz także następujący artykuł autorstwa Pan, Yu & Stewart comet.lehman.cuny.edu/vpan/pdf/pan146.pdf
Markus Bläser
17

Istnieje algorytm kombinatoryczny Mahajana i Vinaya, który działa na pierścieniach komutacyjnych: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html

Sasho Nikolov
źródło
Dziękuję za odpowiedź z linkiem do bardzo interesującego artykułu.
Walerij Sokołow
Uważam również, że istnieją bardziej wydajne algorytmy, ponieważ autorzy tego artykułu rozwiązali bardziej ogólny problem (dla każdego pierścienia przemiennego).
Valeriy Sokolov
przez „są” masz na myśli „znane” czy „istnieją” (ale jeszcze ich nie znaleziono)? to rozsądne przypuszczenie, ale jestem nieco sceptyczny, że struktura pierścienia liczb całkowitych modulo małej liczby złożonej może ci bardzo pomóc. jeśli się mylę, uważam to za interesujące.
Sasho Nikolov
1
@ValeriySokolov, aby być uczciwym, ponieważ odpowiedź odpowiada na twoje pytanie, możesz rozważyć jego zaakceptowanie (lub jeśli chcesz poczekać na ewentualnie lepsze odpowiedzi, które nie byłyby nieuzasadnione)
Suresh Venkat
@SashoNikolov Odkryłem, że Wolfram Mathematica jakoś to oblicza. W „Uwagach implementacyjnych” mówią: Det stosuje metody modułowe i redukcję wierszy, konstruując wynik przy użyciu twierdzenia o chińskiej reszcie. Chciałbym wiedzieć, co dokładnie robią, ale szybkie wyszukiwanie nic mi nie dało. Jeśli chodzi o „mały kompozyt ”, oznacza to tylko, że chcę uznać złożoność dodawania i mnożenia w tym pierścieniu za O ( 1 ) . To znaczy wszystkie czynniki takie jak O ( log m ) są uważane za O ( 1 ) . mO(1)O(logm)O(1)
Walerij Sokołow
11

Aby rozwiązać ten problem istnieje szybki algorytm deterministyczny na podstawie Smith normalnych form , których najgorszym przypadku złożoność jest górna ograniczona przez koszt mnożenia macierzy-w ciągu liczb całkowitych modulo . Dla dowolnej macierzy A algorytm generuje swoją normalną postać Smitha, z której można łatwo obliczyć det ( A ) .mAdet(A)

Mówiąc konkretniej, zdefiniuj , aby dwie macierze n × n o współczynnikach wziętych z Z m można było pomnożyć za pomocą podstawowych operacji arytmetycznych O ( n ω ) na Z m (dodawanie liczb całkowitych, mnożenie, potęgowanie itp.). Następnie,ωn×nZmO(nω)Zm

Biorąc pod uwagę macierz , istnieje algorytm deterministyczny, który oblicza det ( A ) przy użyciu O ( n ω ) podstawowych operacji arytmetycznych na Z m [1] .AZmn×ndet(A)O(nω)Zm

Kiedy napisano to w 1996 r., Nie było asymptotycznie szybszej alternatywy (w artykule wspomniano o wcześniejszym istnieniu algorytmów o tym samym wiązaniu, ale nie wiem, które z nich, czy są one probabilistyczne).

Aktualizacja (17 lipca 2013 r.): Miłą zaletą tego algorytmu jest to, że działa on w czasie wielomianowym dla dowolnego złożonego nie znając faktoryzacji liczby pierwszorzędowej m ! Jest to dobre, ponieważ nie istnieją znane wydajne (klasyczne) algorytmy faktoringu (oczywiście, jeśli masz komputer kwantowy, możesz zastosować algorytm Shora ). Jeśli zrobić mają wtedy algorytm faktoryzacji Markus zasugerował wydaje sposób prostsze do wykonania.mm

Uwagi: w artykule złożoność „podstawowych operacji arytmetycznych” wynosi jeśli używasz standardowej arytmetyki liczb całkowitych, ale możesz osiągnąć O ( M ( log m ) log log m ) za pomocą szybszych technik. M ( t ) ogranicza koszt pomnożenia dwóch liczb całkowitych t- bitowych. Obecny rekord dla ω wynosi 2,3727 .O(log2m)O(M(logm)loglogm)M(t)tω

Juan Bermejo Vega
źródło
nie jest co zwykle oznacza ω ? θω
Sasho Nikolov
Może nie znam najczęstszego zapisu tego.
Juan Bermejo Vega
Myślę, że masz rację, zmienię to na „główny nurt”
Juan Bermejo Vega