img012 (53)

16

W zadaniach obliczeniowych związanych z modelowaniem systemów fizycznych, jak też w zadaniach symulacji komputerowej układów będących przedmiotem zainteresowania różnych dziedzin techniki występują układy równań liniowych złożone z bardzo dużej liczby równań. Przykładem może tu być zadanie analizy liniowej sieci elektronicznej będącej modelem małosygnałowym sieci elektrycznej układu scalonego. Analiza stanu ustalonego przy pobudzeniu sinusoidalnym z wykorzystaniem transformacji Fouriera (analiza AC) wymaga często rozwiązania układu kilkuset równań liniowych z taką samą liczbą niewiadomych. Wśród elektronicznych układów scalonych można łatwo podać przykłady, w których model obwodowy układu zawiera kilkaset węzłów. W przypadku analizy z wykorzystaniem na przykład metody potencjałów węzłowych układu zlinearyzowanego w otoczeniu punktu pracy otrzymuje się dla sieci o 200 węzłach niezależnych układ 200 równań liniowych (o współczynnikach zespolonych). Jeżeli dla otrzymania rozwiązania wykorzystywana jest na przykład metoda eliminacji Gaussa lub metoda dekompozycji LU należące do najwydajniejszych obliczeniowo, to dokładna liczba niezbędnych do wykonania działań mnożenia i dzielenia (na liczbach zespolonych) wynosi 2 706 600 [6, 7, 8]. Jeżeli każda operacja wymaga 5us, to czas niezbędny dla wykonania jedynie mnożeń i dzieleń wynosi w przybliżeniu 14s. Gdy układ równań węzłowych ma być rozwiązywany wielokrotnie dla różnych wartości elementów macierzy admitancji węzłowych i różnych wartości elementów wektora węzłowych wydajności prądowych (różne wartości pobudzeń) co ma miejsce na przykład przy realizacji zadania optymalizacji układu, to czas obliczeń może być nadmiernie długi, pomimo wykorzystania najwydajniejszych obliczeniowo algorytmów [6].

Oprócz problemów związanych z czasem obliczeń trudności może sprawić zapamiętywanie dużych macierzy współczynników. Nawet przy współcześnie wykorzystywanych komputerach układy równań, które występują w obliczeniach (nie tylko w elektronice) są tak duże, że istotne znaczenie ma taka modyfikacja algorytmów rozwiązywania układów równań liniowych, aby pomijane były w trakcie ich realizacji niemające wpływu na wynik działania z udziałem elementów zerowych, jak też przechowywane byłyby w pamięci jedynie elementy niezerowe macierzy współczynników.

Należy tu nadmienić, że na przykład macierze admitancji węzłowych liniowych sieci elektronicznych otrzymywanych w wyniku linearyzacji modeli obwodowych układów scalonych wokół ustalonych punktów pracy są macierzami rzadkimi. To znaczy zawierają bardzo mało elementów niezerowych. Dla przykładu macierz admitancji węzłowych typowego układu elektronicznego o 100 węzłach zawiera około 5% elementów niezerowych. Dla dużych pod względem rozmiaru układów równań liniowych, występujących w opisie układów i systemów w innych dziedzinach, otrzymuje się podobne oszacowania.

Macierze o dużych rozmiarach zawierające małą liczbę elementów niezerowych (na przykład do 5%) określane są w literaturze jako macierze rzadkie (rozrzedzone), a metody rozwiązywania zagadnień obliczeniowych uwzględniające rzadkość macierzy noszą nazwę metod macierzy rzadkich [6, 7], Stosowane algorytmy rozwiązywania układów równań liniowych uzupełniane są w przypadku wykorzystywania ich w analizie dużych układów i systemów tak, aby wyeliminować zbędne działania z udziałem elementów zerowych i tak, aby zapamiętywać jedynie elementy niezerowe macierzy współczynników. Takie uzupeł-