Dla stałej n rozważmy macierze Toeplitza n przez n z wpisami, które są albo 0 albo 1. Celem jest znalezienie maksymalnego wyznacznika we wszystkich takich macierzach Toeplitz.
Zadanie
Dla każdego n
z 1 w górę wyprowadzaj maksymalną determinantę dla wszystkich n na n macierzy Toeplitza z wpisami, które są albo 0 albo 1. Powinno być jedno wyjście, na n
które powinien mieć maksymalną determinantę, a także przykładową macierz, która ją osiąga.
Wynik
Twój wynik jest najwyższy w n
twoim kodzie w ciągu 2 minut na moim komputerze. Aby to trochę wyjaśnić, Twój kod może działać łącznie przez 2 minuty, nie jest to 2 minuty na n
.
Łamacz krawatów
Jeśli dwa zgłoszenia otrzymają ten sam n
wynik, zwycięskim wejściem będzie ten, który osiągnie najwyższy n
w najkrótszym czasie na mojej maszynie. Jeśli dwa najlepsze zgłoszenia są równe również w tym kryterium, zwycięzcą będzie odpowiedź przesłana jako pierwsza.
Języki i biblioteki
Możesz korzystać z dowolnego darmowego języka i bibliotek, które ci się podobają. Muszę być w stanie uruchomić Twój kod, więc proszę podać pełne wyjaśnienie, jak uruchomić / skompilować kod w systemie Linux, jeśli to w ogóle możliwe.
Moja maszyna Czasy zostaną uruchomione na moim komputerze. Jest to standardowa instalacja ubuntu na ośmiordzeniowym procesorze AMD FX-8350. Oznacza to również, że muszę być w stanie uruchomić Twój kod.
Małe odpowiedzi
Dla n = 1..10 wyniki powinny wynosić 1,1,2,3,5,9,32,56,125,315
Ta sekwencja nie znajduje się w OEIS, więc zwycięski wpis może również zaproponować tam nowy wpis.
Dotychczasowe wpisy
n=10
n=11
autor: Vioz w Pythonn=9
autor: Tyilo w Cn=12
autor: Legendre in J.n=10
autor: Tensibai w R.n=14
autor: SteelRaven w C ++n=14
autor: RetoKoradi w C ++
n = 1..10
: ghostbin.com/paste/axkpaOdpowiedzi:
C ++ z pthreads
To osiąga n = 14 w niecałą minutę na moim komputerze. Ale ponieważ jest to tylko 2-rdzeniowy laptop, mam nadzieję, że 8-rdzeniowa maszyna testowa może ukończyć n = 15 w niecałe 2 minuty. Na moim komputerze zajmuje to około 4:20 minut.
Naprawdę miałem nadzieję wymyślić coś bardziej wydajnego. Tam dostał się sposób bardziej efektywnie obliczyć zdeterminowanej macierzy binarnej. Chciałem wymyślić jakieś dynamiczne podejście programistyczne, które uwzględnia warunki +1 i -1 w obliczaniu wyznacznika. Ale do tej pory po prostu nie doszło do siebie.
Ponieważ nagroda wkrótce wygaśnie, wdrożyłem standardowe podejście brutalnej siły:
Testowałem to na Mac OS, ale wcześniej użyłem podobnego kodu na Ubuntu, więc mam nadzieję, że to się skompiluje i uruchomi bez żadnych problemów:
.cpp
rozszerzeniem, npoptim.cpp
.gcc -Ofast optim.cpp -lpthread -lstdc++
.time ./a.out 14 8
. Pierwszy argument to maksimumn
. 14 powinno zakończyć się w mniej niż 2 minuty, ale byłoby wspaniale, gdybyś mógł spróbować również 15. Drugi argument to liczba wątków. Korzystanie z tej samej wartości co liczba rdzeni maszyny jest zwykle dobrym początkiem, ale wypróbowanie niektórych odmian może potencjalnie poprawić czasy.Daj mi znać, jeśli masz problemy z budowaniem lub uruchomieniem kodu.
źródło
jot
Aktualizacja: Ulepszony kod do wyszukiwania ponad połowy wartości. Teraz oblicza
n=12
wygodnie w ciągu 120 sekund (z 217 do 60 sekund).Trzeba będzie najnowsza wersja J zainstalowany.
Uruchom to i zabij, gdy miną dwie minuty. Moje wyniki (MBP 2014 - 16 GB pamięci RAM):
Całkowity czas pracy = 61,83s.
Dla żartu
Samo to zajęło około 210 sekund.
źródło
n = 12
wymaga około 18 GiB pamięci.n=13
. Możesz zmienić13
w przedostatnim wierszu, aby obliczyć, co chcesz.)Python 2
To bardzo proste rozwiązanie i prawdopodobnie nie wygra konkursu. Ale hej, to działa!
Dam szybki przegląd tego, co się właściwie dzieje.
n
. Na przykład, kiedyn=2
wygeneruje to tablicę o długości 2 n + 1 , gdzie każdy wiersz ma długość 2n-1. To będzie wyglądać następująco:[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
.n
razy i odcinam pierwszen
elementy, aby wygenerować odpowiednią macierz, i używamscipy
do obliczenia wyznacznika, wszystko z zachowaniem wartości maksymalnej. Na koniec po prostu drukuję maksimum, przyrostn
o 1 i kontynuuję, aż upłynie 10 minut.Aby to uruchomić, musisz zainstalować scipy .
Edycja 1: Zmieniono sposób budowania początkowych wierszy za pomocą itertools.product, dzięki Sp3000!
Edycja 2: Usunięto przechowywanie możliwych rzędów początkowych dla minimalnej poprawy prędkości.
Edycja 3: Zmieniono na
scipy
mieć większą kontrolę nad sposobemdet
działania.Oto kilka przykładowych danych wyjściowych na moim komputerze domowym (i7-4510U, 8 GB pamięci RAM):
źródło
C ++
Bruteforce z wykorzystaniem OpenMP do równoległości i prostej optymalizacji w celu uniknięcia oceny wyznacznika dla transponowanych matryc.
źródło
do
Połącz z:
Biegnij z:
Może wyprowadzić maksymalną determinantę dla
n = 1..10
w ciągu ~ 115 sekund na moim komputerze.Program pobiera wyznacznik każdej możliwej binarnej macierzy Toeplitza wielkości
n
, jednak każdy wyznacznik macierzy wielkości5x5
lub mniejszej będzie buforowany przy użyciu zapamiętywania.Na początku błędnie założyłem, że każda submatrix macierzy Toeplitz będzie również macierzą Toeplitz, więc musiałem tylko zapamiętać
2^(2n-1)
wartości zamiast2^(n^2)
dla każdejn
. Zrobiłem program, zanim zdałem sobie sprawę z mojego błędu, więc to zgłoszenie jest tylko naprawą tego programu.źródło
O(n!)
złożoność, więc lepiej użyć innego algorytmu.O(n^3)
, jak sądzę, choć mogą być wykonane szybciej ciekawych algorytmów. Wierzę, że większość wbudowanych tu wbudowanych generalnie używa wariantu dekompozycji do wykonania wyznaczników.O(n^2)
algorytmu, jeśli aktualizuję swoją odpowiedź.O(n^2)
. Ale myślę, że wąskim gardłem problemu jest wyszukiwanie wśródO(4^n)
wielu 0-1n
wedługn
macierzy.R
Musisz zainstalować R i pakiety wymienione w
install.packages("package_name")
Ta wersja nie miała mniej niż 2 minuty na moim komputerze (muszę spróbować z równoległą modyfikacją)
Wywołanie i wyjście:
Benchmark na mojej maszynie:
Aby uzyskać informacje, dla zakresu 1:11 potrzeba 285 sekund.
źródło
PARI / GP, n = 11
To brutalna siła, ale wykorzystująca
det(A^T) = det(A)
. Zamieszczam go tylko po to, aby pokazać, jak łatwo można pominąć transpozycję. Najniższy bitb1
zawiera lewą górną komórkę, a pozostałe bity zawierają resztę górnego rzędu.b2
zawiera resztę lewej kolumny. Po prostu egzekwujemyb2 <= (b1>>1)
.Jeśli chodzi o obliczanie wyznaczników Toeplitza w
O(n^2)
czasie: w moich ograniczonych badaniach ciągle napotykałem wymóg, aby wszyscy główni główni nieletni byli niezerowi, aby algorytmy działały, co jest główną przeszkodą w tym zadaniu. Daj mi wskazówki, jeśli wiesz o tym więcej niż ja.źródło
e_{k+1}
Ma 4-krotność liczby składników jake_k
. W dokumencie jest wiele pominięć. Odwracalna matryca ma rozkład LU, jeśli wszystkie wiodące nieletnie są niezerowe. (Zwróć uwagę na mianowniki, np.a_0
- domyślnie gwarantuje się, że są niezerowe). Wyjątkowość wynika z tego, że L jest jednostką trójkątną. Autor nie wspomniał także o stabilności numerycznej. W przypadku, gdy łącze stanie się niedostępne, artykuł brzmi „O obliczaniu determinantów matematycznych Toeplitza” Hsuan-Chu Li (2011).