tytuł:
|
Odwracanie dużych macierzy |
wariant tytułu: |
Inverting large matrices
|
autor: |
Vialko Iryna |
recenzent: |
Zgliczyński Piotr , Gniadek Paweł
|
promotor: |
Zgliczyński Piotr
|
data obrony
: |
2021-10-14 |
język: |
polski |
abstrakt w j. polskim: |
Niniejsza praca dotyczy odwracania dużych macierzy. Celem pracy jest sformułowanie wydajnego algorytmu odwracania, odpowiedniego przede wszystkim dla gęstych macierzy mających duży rzadki blok. Problem jest rozważony na przykładzie metody na obliczanie przekątnej macierzy odwrotnej.Pierwszym krokiem w dążeniu do sformułowania wydajnego algorytmu odwracania jest wprowadzenie pojęcia wybranego odwracania macierzy oraz formuły Takahashiego do obliczania wybranych wyrazów macierzy odwrotnej, przydatnych szczególnie dla rzadkich bloków w macierzach gęstych. Dalej, w celu osiągnięcia najlepszej wydajności dla gęstej części macierzy, zastosowano rozkład blokowy oparty na uzupełnieniu Schura. Na koniec połączono blokowy algorytm odwracania z formułą Takahashiego w algorytmie wyznaczania przekątnej macierzy odwrotnej.Praca również zawiera implementację sekwencyjnej metody Takahashiego na obliczanie przekątnej macierzy odwrotnej oraz wstęp do opisu równoległej metody Takahashiego. |
abstrakt w j. angielskim: |
This thesis concerns the inverting large matrices. The aim of the thesis is the formulation of a high-performance inversion algorightm suitable for any dense matrix presenting a large, sparse block. The problem is considered on the example of the method for computing the diagonal of the inverse matrix.The first step in formulating an efficient inversion algorithm is introducing the concept of the selected inversion and the Takahashi's formula for computing the selected inverse, which are especially useful for sparse blocks in dense matrices. Further, a block decomposition based on the Schur complement is used to achieve the best performance for the dense part of the matrix. Finally, the block inversion algorithm and the Takahashi's formula are combined in the algorithm for computing the diagonal of the inverse matrix.The thesis also includes the implementation of the sequential Takahashi's method for computing the diagonal of the inverse matrix and an introduction to the description of the parallel Takahashi's method. |
słowa kluczowe w j. polskim: |
odwracanie macierzy, macierz odwracalna, macierz odwrotna, rozkład LU, metoda eliminacji Gaussa, macierz rzadka, wybrane odwracanie macierzy, rozkład LDU, formuła Takahashiego, rozkład blokowy, uzupełnienie Schura, sekwencyjna metoda Takahashiego, równoległa metoda Takahashiego |
słowa kluczowe w j. angielskim: |
inverting matrices, invertible matrix, inverse matrix, LU factorization, Gaussian elimination, sparse matrix, selected inversion, LDU factorization, Takahashi’s formula, block decomposition, Schur complement, Sequential Takahashi’s method, parallel Takahashi’s method |
wydział: instytut / zakład / katedra: |
Wydział Matematyki i Informatyki |
typ: |
praca licencjacka |