Szukam biblioteki, która wykonuje operacje macierzowe na dużych macierzach rzadkich bez poświęcania stabilności numerycznej. Macierze będą miały wartości 1000+ na 1000+, a wartości macierzy będą zawierać się w przedziale od 0 do 1000. Będę wykonywać algorytm rachunku indeksu, więc będę generował (rzadkie) wektory rzędowe macierzy szeregowo. Gdy rozwijam każdy rząd, będę musiał przetestować liniową niezależność. Po wypełnieniu mojej macierzy pożądaną liczbą wektorów liniowo niezależnych będę musiał przekształcić macierz w postać zredukowanego rzędu rzędów.
Problem polega na tym, że moja implementacja wykorzystuje eliminację Gaussa do określenia liniowej niezależności (zapewnienie formy rzutu wiersza po znalezieniu wszystkich wektorów wiersza). Biorąc jednak pod uwagę gęstość i rozmiar matrycy, oznacza to, że wpisy w każdym nowym rzędzie stają się wykładniczo większe w miarę upływu czasu, ponieważ w celu wykonania anulowania należy znaleźć lcm wiodących wpisów. Znalezienie zredukowanej formy matrycy dodatkowo zaostrza problem.
Moje pytanie brzmi zatem: czy istnieje algorytm, a może jeszcze implementacja, która może przetestować liniową niezależność i rozwiązać formę zredukowanego rzutu rzędu, przy zachowaniu możliwie najmniejszych wpisów? Wydajny test liniowej niezależności jest szczególnie ważny, ponieważ w algorytmie rachunku indeksu jest on przeprowadzany zdecydowanie najbardziej.
źródło