Skuteczny sposób na wyznaczenie wartości n! x n! macierz w Maple

Question

Mam dużą matrycę, n! x n !, dla którego muszę wziąć wyznacznik. Dla każdego permutacji n skojarzyć

• wektorze o długości 2n (to proste obliczeniowo)
• wielomianem zmiennych 2n (produkt czynników liniowych obliczane rekurencyjnie n)

Macierz jest macierzą oceny wielomianów w wektorach (uważanych za punkty). Tak więc sigma, wpis tau macierzy (indeksowany przez permutacje) jest wielomianem dla sigmy ocenianej na wektorze dla tau.

Przykład: Do n=3 jeśli wielomian i TH (x1 - 4)(x3 - 5)(x4 - 4)(x6 - 1) i punkt j TH (2,2,1,3,5,2), to wówczas wpis (i,j) Th matrycy będzie (2 - 4)(1 - 5)(3 - 4)(2 - 1) = -8. Tutaj n=3, więc punkty są w R^(3!) = R^6, a wielomiany mają zmienne 3!=6.

Moim celem jest ustalenie, czy macierz nie jest nieskupiona.

---

Moje podejście w tej chwili jest tak:

• funkcja point zajmuje permutacji i wyprowadza wektorze
• funkcja poly zajmuje permutacji i wyjść wielomian
• funkcję nextPerm daje następna permutacja w porządku leksykograficznym

skróconego pseudokod mojego kodu jest taka:

B := []; 
P := []; 
w := [1,2,...,n]; 
while w <> NULL do 
    B := B append poly(w); 
    P := P append point(w); 
    w := nextPerm(w); 
od; 

// BUILD A MATRIX IN MAPLE 
M := Matrix(n!, (i,j) -> eval(B[i],P[j])); 

// COMPUTE DETERMINANT IN MAPLE 
det := LinearAlgebra[Determinant](M); 

// TELL ME IF IT'S NONSINGULAR 
if det = 0 then return false; 
else return true; fi; 

pracuję w Maple za pomocą wbudowanego w funkcji LinearAlgebra[Determinant], ale wszystko inne jest zwyczaj zbudowany funkcja, która wykorzystuje funkcje Maple niskim poziomie (na przykład seq, convert i cat).

Mój problem polega na tym, że trwa to zbyt długo, co oznacza, że ​​mogę przejść do n=7 z cierpliwością, ale uzyskanie n=8 trwa kilka dni. Idealnie, chcę móc dostać się do n=10.

Czy ktoś ma pomysł, w jaki sposób mogę poprawić czas? Jestem otwarty na pracę w innym języku, np. Matlab lub C, ale wolałby znaleźć sposób na przyspieszenie tego w Maple.

Zdaję sobie sprawę, że może być trudno odpowiedzieć bez wszystkich szczegółów, ale kod każdej funkcji, np. point i poly, jest już zoptymalizowany, więc prawdziwym pytaniem jest tutaj, czy istnieje szybszy sposób na określenie determinanty przez zbudowanie macierzy w locie lub coś w tym stylu.

---

UPDATE: Oto dwa pomysły, które mam bawił się, że nie działają:

1. można przechowywać wielomianów (ponieważ potrwać do obliczenia, nie wiem chce przerobić, że jeśli mogę pomóc go) do wektora o długości n! i obliczyć punkty w locie i podłącz te wartości do wzoru permutacji dla wyznacznika:

   

   Problem polega na tym, że jest to O(N!) w rozmiarze macierzy, więc dla mojego przypadku będzie to O((n!)!). Kiedy n=10, (n!)! = 3,628,800! jest o wiele za duży, aby nawet rozważyć wykonanie.

2. Obliczyć wyznacznik przy użyciu dekompozycji LU. Na szczęście główna przekątna mojej matrycy jest niezerowa, więc jest to wykonalne. Ponieważ jest to O(N^3) w rozmiarze macierzy, która staje się O((n!)^3), która jest o wiele bliższa do wykonania. Problem polega jednak na tym, że wymaga on ode mnie przechowywania całej matrycy, co poważnie obciąża pamięć, nie martwiąc się czasem wykonywania. Więc to też nie działa, przynajmniej nie bez odrobiny sprytu. Jakieś pomysły?

Answer 1

Nie wiem, czy mam po problemu; czy to (lub redukuje do) następujące?

mieć dwa wektory liczby n, wywołują je x i c, wówczas element matrycy jest produktem na k z (x_k+c_k), przy czym każdy wiersz/kolumna odpowiada różne uporządkowania o x i c?

Jeśli tak, to uważa, matryca będzie pojedynczej, kiedy nie są powtórzone wartości obu x lub c, ponieważ matryca następnie są powtarzane wiersze/kolumny. Spróbuj kilka Monte Carlo na mniejszą n o odmiennych wartościach x i c aby sprawdzić, czy sprawa jest w ogóle nieosobliwe - to całkiem prawdopodobne, jeśli to prawda do 6, to będzie prawdziwe dla 10.

jeśli chodzi o brute-force idzie, metoda:

1. jest non-rozrusznik
2. będzie działać znacznie szybciej (powinno być kilka sekund n=7), chociaż zamiast LU może chcesz spróbować SVD , która zrobi o wiele lepszą robotę, dając ci znać, jak dobrze zachowuje się twoja matryca.

Answer 2

Nie jest dla mnie jasne, czy problemem jest przestrzeń lub czas. Oczywiście obie wymiany w tę iz powrotem. Jeśli chcesz wiedzieć tylko, czy wyznacznik jest pozytywny, czy nie, zdecydowanie powinieneś wybrać dekompozycję LU. Powodem jest to, że jeśli A = LU z L dolną trójkątne U górnej trójkątny, następnie

det(A) = det(L) det(U) = l_11 * ... * l_nn * u_11 * ... * u_nn 

więc tylko trzeba ustalić, czy któryś z głównych przekątnych wpisów L lub U jest 0.

Aby uprościć dalej, użyj algorytmu Doolittle, gdzie l_ii = 1. Jeśli w jakimś momencie algorytm się zepsuje, macierz jest pojedyncza, więc możesz przestać. Oto sedno:

for k := 1, 2, ..., n do { 
    for j := k, k+1, ..., n do { 
    u_kj := a_kj - sum_{s=1...k-1} l_ks u_sj; 
    } 
    for i = k+1, k+2, ..., n do { 
    l_ik := (a_ik - sum_{s=1...k-1} l_is u_sk)/u_kk; 
    } 
} 

Kluczem jest to, że można obliczyć i th wiersz U i kolumnę i lecia L w tym samym czasie, trzeba tylko wiedzieć poprzedniego wiersza/kolumny do przodu . W ten sposób przetwarzasz równolegle tyle ile możesz i przechowujesz tak mało, jak potrzebujesz. Ponieważ w razie potrzeby można obliczyć pozycje a_ij, konieczne jest zapisanie dwóch wektorów o długości n podczas generowania dwóch kolejnych wektorów o długości n (wiersze U, kolumny L). Algorytm zajmuje czas n^2. Być może uda ci się znaleźć kilka dodatkowych sztuczek, ale to zależy od twojego czasu/czasu.