Załóżmy, że mam kwadrat matrixM. Załóżmy, że chciałbym uzyskać invert macierz M.Szybkie odwracanie macierzy bez pakietu
Próbuję użyć klasy frakcji mpq w obrębie gmpy2 jako członków mojej macierzy M. Jeśli nie znasz tych frakcji, są one funkcjonalnie podobne do wbudowanego pakietu Pythona fractions. Jedynym problemem jest to, że nie ma pakietów, które odwrócą moją macierz, chyba że wyjmę je z frakcji. Wymagam liczb i odpowiedzi w formie ułamka. Więc będę musiał napisać własną funkcję do odwrócenia M.
Istnieją znane algorytmy, które można zaprogramować, takie jak gaussian elimination. Jednak wydajność jest problem, więc moje pytanie jest w następujący sposób:
Czy istnieje algorytmicznie szybki algorytm, który mógłbym użyć do obliczenia odwrotności macierzy M?
Każdy rozsądny szybki algorytm, aby to zrobić, będzie miał możliwość implementacji w C jako rozszerzenie. Innym podejściem byłoby pomnożenie ich przez ich GCD, lub tylko na podstawie ich mianowników, w celu uzyskania liczb całkowitych i użycia pakietów z rozszerzeniami C i znacznie więcej czasu na optymalizację. To jest 'O (n)', więc jeśli algorytm do odwrócenia jest lepszy niż 'O (n)', nie zaszkodzi złożoności czasu. – Artyer
Czy spojrzałeś na sympy? Działa wspaniale z GMpy2 i macierzami: http://docs.sympy.org/dev/modules/matrices/matrices.html#linear-algebra – denfromufa
Tak, ale inwersja sympy jest wolniejsza niż kodowanie gaussowskie ręcznie. Mogę udostępnić mój kod do gaussowskiej eliminacji za pomocą testów porównawczych. –