Macierz rzadka

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Macierz rzadka otrzymana podczas rozwiązywania układu równań różniczkowych metodą elementów skończonych w zagadnieniu dwuwymiarowym. Czarne kropki reprezentują położenie niezerowych elementów macierzy równania.

Macierz rzadkamacierz, w której większość elementów ma wartość zero.

Nauka – autonomiczna część kultury służąca wyjaśnieniu funkcjonowania świata, w którym żyje człowiek. Nauka jest budowana i rozwijana wyłącznie za pomocą tzw. metody naukowej lub metod naukowych nazywanych też paradygmatami nauki poprzez działalność badawczą prowadzącą do publikowania wyników naukowych dociekań. Proces publikowania i wielokrotne powtarzanie badań w celu weryfikacji ich wyników prowadzi do powstania wiedzy naukowej. Zarówno ta wiedza jak i sposoby jej gromadzenia określane są razem jako nauka.Struktura danych (ang. data structure) - sposób uporządkowania informacji w komputerze. Na strukturach danych operują algorytmy.

Macierze rzadkie z reguły odpowiadają układom, w których istnieje bardzo dużo stopni swobody, z których każdy wiąże się bezpośrednio z niewielką liczbą innych stopni swobody (tzw. luźny związek, ang. loose coupling). Przykładem takiego układu jest zestaw tysięcy kulek ułożonych w linii i połączonych sprężynami w ten sposób, że pierwsza i ostatnia kulka są unieruchomione, a każda kulka wewnętrzna połączona jest z dwiema sąsiednimi kulkami sprężyną. Układ ten stanowi model drgań struny i opisywany jest macierzą rzadką, w której w każdym wierszu i kolumnie znajdują się co najwyżej trzy elementy niezerowe. Gdyby w tym modelu założyć, że każda kulka połączona jest sprężynami ze wszystkimi innymi kulkami, otrzymalibyśmy model reprezentowany przez macierz gęstą.

Pamięć operacyjna (ang. internal memory, primary storage) – pamięć adresowana i dostępna bezpośrednio przez procesor, a nie przez urządzenia wejścia-wyjścia procesora. W pamięci tej mogą być umieszczane rozkazy (kody operacji) procesora (program) dostępne bezpośrednio przez procesor i stąd nazwa pamięć operacyjna. W Polsce często pamięć ta jest utożsamiana z pamięcią RAM, choć jest to zawężenie pojęcia, pamięcią operacyjną jest też pamięć nieulotna (ROM, EPROM i inne jej odmiany) dostępna bezpośrednio przez procesor, a dawniej używano pamięci o dostępie cyklicznym.Liczba stopni swobody, df (ang. degrees of freedom) – liczba niezależnych wyników obserwacji pomniejszona o liczbę związków, które łączą te wyniki ze sobą.

Macierze rzadkie są wykorzystywane (i badane) w teorii grafów oraz dyscyplinach pochodnych, np. w teorii sieci. Ogromne macierze rzadkie często pojawiają się w badaniach naukowych i inżynierskich podczas rozwiązywania równań różniczkowych cząstkowych. Dlatego macierze rzadkie stanowią jeden z głównych obszarów zainteresowań metod numerycznych.

Metody numeryczne – metody rozwiązywania problemów matematycznych za pomocą operacji na liczbach. Otrzymywane tą drogą wyniki są na ogół przybliżone, jednak dokładność obliczeń może być z góry określona i dobiera się ją zależnie od potrzeb.Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

Do przechowywania i operacji na macierzach rzadkich w komputerach stosuje się specjalne algorytmy i struktury danych, które optymalnie wykorzystują strukturę macierzy rzadkich. Dlatego algorytmy opracowane dla macierzy rzadkich są zwykle wielokrotnie szybsze od analogicznych algorytmów dla macierzach gęstych. Dzięki zastosowaniu specjalnych struktur danych, przechowywanie i operacje na macierzach rzadkich wiążą się ze znacznie mniejszym zużyciem pamięci operacyjnej niż w przypadku macierzy gęstych o tych samych rozmiarach. Macierze rzadkie spotykane w zastosowaniach praktycznych często mają tak wielki stopień (tj. rozmiar), że jakiekolwiek operacje na nich za pomocą standardowych algorytmów byłyby zupełnie niemożliwe.

Układ równań liniowych – koniunkcja pewnej liczby (być może nieskończonej) równań liniowych, czyli równań pierwszego rzędu.Inżynieria – działalność polegająca na projektowaniu, konstrukcji, modyfikacji i utrzymaniu efektywnych kosztowo rozwiązań dla praktycznych problemów, z wykorzystaniem wiedzy naukowej oraz technicznej. Działalność ta wymaga rozwiązywania problemów różnej natury oraz skali. Bardziej ogólnie, inżynieria zajmuje się też rozwojem technologii.

Nie istnieje ścisłe kryterium pozwalające odróżniać macierze rzadkie od gęstych. W praktyce określenie jakiejś macierzy jako rzadkiej oznacza, że opłaca się operować na niej za pomocą algorytmów przeznaczonych dla macierzy rzadkich. Zgodnie z tym kryterium zakwalifikowanie macierzy jako macierzy rzadkiej może zależeć od problemu, w którym macierz ta występuje. Np. rozkład LU niezdegenerowanej macierzy o niewielkiej liczbie niezerowych elementów rozmieszczonych na losowych miejscach najczęściej daje w wyniku gęste macierze i dlatego w tym zagadnieniu macierz nie będzie uznana za rzadką. Jednak ta sama macierz w zagadnieniu znalezienia rozwiązania układu równań liniowych najprawdopodobniej zostanie uznana za rzadką.

Macierz – w matematyce układ liczb, symboli lub wyrażeń zapisanych w postaci prostokątnej tablicy. Choć słowo „macierz” oznacza najczęściej macierz dwuwskaźnikową, to możliwe jest rozpatrywanie macierzy wielowskaźnikowych (zob. notacja wielowskaźnikowa). Macierze jednowskaźnikowe nazywa się często wektorami wierszowymi lub kolumnowymi, co wynika z zastosowań macierzy w algebrze liniowej. W informatyce macierze modeluje się zwykle za pomocą (najczęściej dwuwymiarowych) tablic.

Zobacz też[ | edytuj kod]

  • metoda macierzy rzadkich




  • Reklama