Wojskowa Akademia Techniczna

im. Jarosława Dąbrowskiego





Obliczenia rozproszone i równoległe.



Temat sprawozdania: Obliczanie macierzy

odwrotnej.





ProwadzÄ…cy: mgr Adam Misztak

Wykonał: st. szer. pchor. Piotr Jakubowski

Grupa: I8C1S1

1 Pojęcie macierzy



Macierz odwrotna jest to element odwrotny w pierścieniu macierzy kwadratowych.

Uogólnieniem pojęcia macierzy odwrotnej jest tzw. uogólniona macierz odwrotna.



2 Przykład wyznaczania macierzy z definicji.





1

Z definicji. A -1 =

( A )T

det A



gdzie Ä€ – macierz dopeÅ‚nieÅ„ algebraicznych o wyznaczniku detA ï‚Ä… 0

3. Przykład



2

5

7 ïƒÄ…





A = 6 3

4 

5  2  



ïƒ

3





RozwiÄ…zanie:



2

5

7

2 5

det(A) = 6

3

4 6 3 = -18 + 100 – 84 – 105 + 16 +90, czyli det(A) = -1 ï‚Ä… 0, 5

 2  3 5 2

więc A-1 istnieje.



Teraz obliczamy dopełnienia algebraiczne wszystkich wyrazów macierzy A: 3

4

6

4

d11 = (-1)1+1 ïƒ

= -9 + 8 = -1, d

= -(-18-20) = 38



12 = (-1)1+2 ïƒ

2

 3

5

 3

6

3

d13 = (-1)1+3 ïƒ

= -12 - 15 = -27,

5

 2

5

7

2

7

d21 = (-1)2+1 ïƒ

= -(-15 + 14) = 1, d

= - 6 - 35 = -41,



22 = (-1)2+2 ïƒ

2

 3

5

 3

2

5

d23 = (-1)2+3 ïƒ

= -( - 4 - 25) = 29,

5

 2

5

7

2

7

d31 = (-1)3+1 ïƒ

= 20 - 21 = -1, d32 = (-1)3+2 ïƒ

= - (8 – 42) = -34,

3

4

6

4

2

5

d33 = (-1)3+3 ïƒ

= 6 - 30) = -24,

6

3





1 38

 27ïƒÄ…





1

Tworzymy macierz dopełnieo

D =  1  41 29  Zatem A-1 = 1

ïƒ DT =



det( )

A

1  34

 24



ïƒ



 

 1

1

1 ïƒÄ…

1

1

1 ïƒÄ…











= (-1) ïƒ

38

41

34 .

 38

 41  34 , czyli ostatecznie A-1 





 27

 29 24

27

29

 24



ïƒ



ïƒ





4. Zadanie laboratoryjne.



W zadaniu zakÅ‚adam, że macierz odwrotnÄ… da siÄ™ wyznaczyć oraz pomijam sprawdzenie detA ï‚Ä… 0



 Graf obliczający wyznacznik macierzy dopełnień oraz proces odwracania macierzy Utworzony harmonogram dla:

p=1

p – procesor





Warunki:





 oszacowad teoretyczną złożonośd obliczeniową problemu, jako funkcję rozmiaru zadania algorytmu sekwencyjnego.





Algorytm sekwencyjnym dla macierzy n x n, gdzie n=3, wykonujÄ™:

–

24 operacje mnożenia

–

14 operacji odejmowania lub dodawania

–

9 operacji dzielenia



Należy wykonad 2*n^2+2n operacji mnożenia, n^2+n+2 operacji dodawania lub odejmowania oraz n^2 operacji dzielenia.



Złożonośd dla n=3 można wyrazid wzorem:



5*n^2+2, więc jest rzędu O(n^2)



Jednak dla większych n złożonośd ta będzie inna, gdyż zmienia się sposób liczenia wyznacznika dla podmacierzy, złożonośd opisuje wzór:



2*n^4-4*n^3+3^2+5n-3.





5. Złożoność dla m procesorów.



Funkcja zależności złożoności od liczby procesorów i wielkości zadania jest następująca:



[45/p]+3





dla n=3



(2*n^4-4*n^3+3^2+5n)/p-3 ,gdzie:



[ ] - sufit z liczby

p – liczba procesorów

n – rozmiar macierzy



Poniżej harmonogramy dla wielu procesorów:

P=2





Dla p = 3





Dla p = 6





6. Procesory połączone są w sieci każdy – z - każdym , opóźnienia przesyłu danych między procesorami są równe 2 oraz opóźnienia przesyłu danych wewnątrz każdego procesora są równe 1.





Dla p = 3





Dla p = 6





Dla p = 9





7. procesory jednorodne i niejednorodne(każdy kolejny jest dwukrotnie szybszy od poprzedniego)

Dla

p = 2 procesory jednorodne 2 (liczba procesorów mniejsza od rozmiaru zadania) p=2 procesory niejednorodne:





Dla p = 18





Dla p=18 procesory niejednorodne:





8. Działania niejednorodne i jednorodne.



Dla p=2 dla działao jednorodnych,

Dla p =2, czas dodawania=1, czas odejmowania=1, dzielenia=3, mnożenia=2





Dla p=18 dla działao jednorodnych,

Dla p=18 czas dodawania=1, czas odejmowania=1, dzielenia=3, mnożenia=2





9 Podsumowanie



Zadanie wykonaÅ‚em zgodnie z wytycznym. RozwiÄ…zaÅ‚em zadanie na podstawie definicji odwracania macierzy. W rozwiÄ…zaniu zaÅ‚ożyÅ‚em, że detA ï‚Ä… 0 i zadanie jest możliwe do rozwiÄ…zania. Zadanie uważam, za trudne ponieważ jest wiele możliwoÅ›ci jego rozwiÄ…zania.

Przy macierzy 4*4 lub 6*6 tych założeo oraz zmiennych trzeba byłoby więcej, a co za tym idzie sposób rozwiązania musiałby byd trochę inny. Efektywnośd zadania spada przy zastosowaniu większej ilości procesorów ponieważ procesory są bezczynne, gdyż czekają na wykonanie czynności przez procesory aktywne. Zdecydowanie najlepszy wynik czasowy to 3

jednostki przy 18 procesorach niejednorodnych. Potwierdza to wspomniany fakt, że 18 jest liczbą procesorów powyżej której czas już się nie zmniejszy. Jednak taki przebieg został

wykonany ogromnym nakładem sprzętowym, gdyż każdy procesor był dwukrotnie szybszy od poprzedniego. Najwolniej rozwiązało się zadanie przy użyciu opróżnieo przesyłu danych między procesorami oraz poprzez procesor. Im większy czas opróżnienia tym dłuższy czas wykonania zadania, nawet przy procesorach niejednorodnych gdy ustawiłem w działaniach operacji (czasy operacji takie jak: dodawanie, odejmowanie, dzielenie i mnożenie) nie działały szybciej od tych bez opóźnieo.