Softvérové balíky pre riešenie veľkých lineárnych systémov - História úprav

Juraj: /* Simulačný softvér */

2010-08-01T19:53:55Z

Simulačný softvér

Juraj: /* Záver */

2010-08-01T19:53:22Z

Záver

Juraj na 19:52, 1. august 2010

2010-08-01T19:52:41Z

Juraj: Zamyká „Softvérové balíky pre riešenie veľkých lineárnych systémov“ ([edit=sysop] (na neurčito) [move=sysop] (na neurčito))

2010-07-30T20:20:49Z

Zamyká „Softvérové balíky pre riešenie veľkých lineárnych systémov“ ([edit=sysop] (na neurčito) [move=sysop] (na neurčito))

Repto na 21:49, 30. máj 2010

2010-05-30T21:49:53Z

Repto na 21:16, 30. máj 2010

2010-05-30T21:16:40Z

Repto: Vytvorená stránka „ '''Softvérové balíky pre riešenie veľkých lineárnych systémov''' Riešenie sústav lineárnych rovníc je základom riešenia mnohých problémov vo vedecký…“

2010-05-30T21:13:54Z

Vytvorená stránka „ '''Softvérové balíky pre riešenie veľkých lineárnych systémov''' Riešenie sústav lineárnych rovníc je základom riešenia mnohých problémov vo vedecký…“

Nová stránka

'''Softvérové balíky pre riešenie veľkých lineárnych systémov'''

Riešenie sústav lineárnych rovníc je základom riešenia mnohých problémov vo vedeckých výpočtoch. V mnohých prípadoch sú riešené sústavy veľmi veľké a matica sústavy je riedka. V mnohých aplikáciách je matica symetrická, ako je to napríklad pri použití metódy konečných prvkov. Za posledné desaťročia bolo navrhnutých množstvo nových algoritmov a taktiež programových balíkov pre riešenie symetrických riedkych matíc , ktoré implementujú tieto algoritmy. V tejto časti sú uvedené niektoré balíky obsahujúce priame riešiče riedkych lineárnych systémov.

Priame riešiče riedkych systémov pracujú v niekoľkých fázach. Presné rozdelenie do jednotlivých fáz závisí od použitého algoritmu a softvéru, všeobecné rozdelenie je nasledovné:

# Usporiadanie na základe štruktúry.
# Analýza štruktúry matice na základe, ktorej sa zavedú potrebné  dátové štruktúry pre efektívny rozklad matice
# Rozklad matice
# Fáza riešenia, kde sa vykoná eliminácia a potom následne spätná substitúcia.

Fáza rozkladu matice je obvykle časovo najnáročnejšia. Naopak fáza riešenia je všeobecne omnoho rýchlejšia.

Algoritmy rozkladu matíc

Rozklad môže vykonaný rôznymi spôsobmi, čo závisí od prístupu k jednotlivým prvkom systému. Existujú tri základné typy algoritmov : left-looking, right-looking a multifrontal.

Pri right-looking prístupe sa v každom kroku vypočítajú riadky a stĺpce a a tieto zmeny sa hneď aplikujú. Pri left-looking algoritme sa vypočítané zmeny neaplikujú hneď. Predtým ako je eliminovaný stĺpec ''k'' , všetky zmeny z predchádzajúcich stĺpcov ''k'' matice L sa použijú spolu so stĺpcom ''k'' matice A. Pri multifrontálnom algoritme sa zmeny akumulujú, a potom sa aplikujú prostredníctvom tzv. eliminačného stromu.

Niektoré knižnice pre priame riešenie riedkych systémov

'''PARDISO '''umožňuje paralelné a sériové riešenie nesymetrických a symetrických riedkych systémov na multiprocesorovom systéme so zdieľanou pamäťou .Využíva sa tu left-looking a right-looking verzia Choleského rozkladu.

'''SPOOLES''' je knižnica pre riešenie riedkych reálnych a komplexných sústav rovníc . Je dostupná v paralelnej aj sériovej verzii. Používa sa tu verzia Gaussovej eliminačnej metódy s Croutovou redukciou .

'''TAUCS''' je navrhnutá pre symetrické kladne definitné systémy . Používa sa tu left-looking a multifrontálne verzie LU rozkladu a Choleského rozkladu.

'''UMFPACK '''<nowiki>je knižnica pre riešenie nesymetrických systémov. Využíva nesymetrický multifrontálny LU rozklad [14]. </nowiki>

== Simulačný softvér ==
Existuje viacero softvérov, ktoré používajú metódu konečných prvkov. Pomocou tejto metódy sa transformuje systém parciálnych diferenciálnych rovníc, ktoré popisujú danú úlohu na systém lineárnych rovníc . Táto metóda sa používa v mnohých odvetviach : napr. pri návrhu strojov, rôznych súčiastok, atď.

Pri metóde konečných prvkov sa väčšinou dostávame k veľkému systému lineárnych rovníc . Pre jeho riešenie simulačné softvéry používajú niektoré z uvedených moderných metód . Je známych viacero softvérov ktoré pracujú s metódou konečných prvkov napr. ANSYS, COMSOL, FEMM, ELMER Multiphysics a mnoho ďalších. Pre riešenie vzniknutých veľkých sústav lineárnych rovníc používajú rôzne moderné metódy riešenia. V tab. 1 sú uvedené metódy používané v niektorých simulačných programoch.

'''Tab. č. 1 Metódy používané v simulačných softvéroch '''

{| style="border-spacing:0;"
| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''FEMM'''</center>
| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''ANSYS'''</center>
| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''COMSOL'''</center>
| style="border:0.0361in double #000000;padding:0.0729in;"| <center>'''Elmer Multiphysics'''</center>

|-
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>CG</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>iteračné gradientné metódy </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>knižnica UMFPACK</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>knižnica UMFPACK</center>

|-
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>BCG</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>AMG</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>GMRES</center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>AMG a GMG</center>

|-
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center> </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center> </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center> </center>
| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>iteračné gradientné metódy </center>

|}
'''Ukážkový príklad analýzy vo FEMM'''

FEMM je softvérový balík pre riešenie nízkofrekvenčných elektromagnetických úloh v 2D. Pre <nowiki>riešenie vzniknutého systému lineárnych rovníc podľa typu riešeného problému používa buď metódu konjugovaných gradientov s prepodmienením alebo metódu bikonjugovaných gradientov [15].</nowiki>

Na (obr.4) je 2D model asynchrónneho motora, pre ktorý hľadáme rozloženie potenciálu.

Obr. 4 Model asynchrónneho motora vo FEMM

Daná úloha má [[Image:Untitled%201_html_49f63057.png]] stupňov voľnosti, teda sa rieši maticová rovnica s maticou systému o rozmeroch [[Image:Untitled%201_html_m3ca83b85.png]].

[[Image:Untitled%201_html_d245593.png]]Obr. 5 Rozloženie poľa asynchrónneho motora

Na (obr. 5) je vyriešené rozloženie potenciálu pre daný asynchrónny motor. Riešenie danej úlohy metódou bikonjugovaných gradientov prostredníctvom softvéru FEMM trvalo 3 minúty. Riešenie bolo realizované na počítači s procesorom AMD Turion X2 Dual-Core 2.20 GHz a s operačnou pamäťou 4 GB.

@@ Riadok 39: / Riadok 39: @@
 Pri metóde konečných prvkov sa väčšinou dostávame k&nbsp;veľkému systému lineárnych rovníc . Pre jeho riešenie simulačné softvéry používajú niektoré z&nbsp;uvedených moderných metód . Je známych viacero softvérov ktoré pracujú s&nbsp;metódou konečných prvkov napr. ANSYS, COMSOL, FEMM, ELMER Multiphysics a&nbsp;mnoho ďalších. Pre riešenie vzniknutých veľkých sústav lineárnych rovníc používajú rôzne moderné metódy riešenia. V&nbsp;tab. 1 sú uvedené metódy používané v&nbsp;niektorých simulačných programoch.
 {| class="wikitable"
-|+
+|+Tab. č. 1 Metódy používané v&nbsp;simulačných softvéroch
 |-
 !FEMM
@@ Riadok 79: / Riadok 77: @@
 Na (obr. 5) je vyriešené rozloženie potenciálu pre daný asynchrónny motor. Riešenie danej úlohy metódou bikonjugovaných gradientov prostredníctvom softvéru FEMM trvalo 3 minúty. Riešenie bolo realizované na počítači s&nbsp;procesorom AMD Turion X2 Dual-Core 2.20 GHz a&nbsp;s&nbsp;operačnou pamäťou 4 GB.
 =Záver=

@@ Riadok 83: / Riadok 83: @@
 =Záver=
 Cieľom mojej práce bolo oboznámiť sa s riešením sústav veľkých lineárnych rovníc a opísať a porovnať niektoré z existujúcich algoritmov. V práci som sa zameral na opis niektorých existujúcich algoritmov pre riešenie sústav lineárnych rovníc.
 V práci sú opísané niektoré klasické algoritmy pre riešenie sústav lineárnych rovníc. Cramerovo pravidlo a riešenie pomocou inverznej matice sú vhodné len pre veľmi malé sústavy. Gaussova eliminačná metóda taktiež pre veľké matice nie je príliš vhodná, pretože je potrebné veľké množstvo operácií pre riešenie veľkých sústav. Takisto pri eliminácii môžu vzniknúť chyby. Preto sa skôr používajú jej modifikácie.  Klasické iteračné metódy: Jacobiho a Gauss – Seidelova sú vhodné pre väčšie matice a  riedke matice. Keďže množstvo nulových prvkov v riedkych maticiach znižuje počet potrebných operácií a výpočtovú náročnosť, sú tieto metódy vhodné aj pre veľké riedke sústavy lineárnych rovníc.
 Ďalšia časť sa zaoberá priamymi metódami pre riešenie veľkých sústav.  Sú tu opísané dva algoritmy rozkladu pre zjednodušenie veľkých matíc: LU rozklad a Choleského rozklad. Je viacero metód, ako možno rozložiť maticu do podoby niektorého z rozkladov. Na týchto rozkladoch sú založené niektoré moderné priame metódy. V tejto práci sú opísané len základné algoritmy, ako možno tieto rozklady uskutočniť.
 Hlavná časť práce je venovaná moderným iteračným metódam riešenia veľkých sústav. Pozornosť sa tu venuje tzv. gradientným metódam a multigridovým metódam. Pri gradientných metódach sa zostrojí postupnosť vektorov , ktorá konverguje k riešeniu sústavy. Metóda konjugovaných gradientov je vhodná len pre symetrické kladne definitné matice, naopak metóda bikonjugovaných gradientov a GMRES sa používajú pre nesymetrické systémy. Je tu vypracovaný aj ukážkový príklad riešenia sústavy malých rozmerov prostredníctvom metódy konjugovaných gradientov.  Ďalej sa táto časť zaoberá multigridovými metódami. Geometrické multigridové metódy vyžadujú informáciu o hierarchii daného systému, naopak algebraické multigridové metódy nepotrebujú túto hierarchiu poznať. Algebraické sú vhodnejšie pre úlohy s neregulárnou štruktúrou.  Pre objasnenie metódy geometrického multigridu sme vypracovali ukážkový príklad  riešenia jednoduchej úlohy.
 =Použitá literatúra=

@@ Riadok 5: / Riadok 5: @@
 __TOC__
 = =
 Riešenie sústav lineárnych rovníc je základom riešenia mnohých problémov vo vedeckých výpočtoch. V&nbsp;mnohých prípadoch sú riešené sústavy veľmi veľké a&nbsp;matica sústavy je riedka. V&nbsp;mnohých aplikáciách je matica symetrická, ako je to napríklad pri použití metódy konečných prvkov. Za posledné desaťročia bolo navrhnutých množstvo nových algoritmov a&nbsp;taktiež programových balíkov pre riešenie symetrických riedkych matíc , ktoré implementujú tieto algoritmy. V&nbsp;tejto časti sú uvedené niektoré balíky obsahujúce priame riešiče riedkych lineárnych systémov.
 Priame riešiče riedkych systémov pracujú v&nbsp;niekoľkých fázach. Presné rozdelenie do jednotlivých fáz závisí od použitého algoritmu a&nbsp;softvéru, všeobecné rozdelenie je nasledovné:
@@ Riadok 22: / Riadok 15: @@
 Fáza rozkladu matice je obvykle časovo najnáročnejšia. Naopak fáza riešenia je všeobecne omnoho rýchlejšia.
 '''Algoritmy rozkladu matíc'''
@@ Riadok 49: / Riadok 41: @@
 '''Tab. č. 1 Metódy používané v&nbsp;simulačných softvéroch '''
+{| class="wikitable"
+|+
-{| style="border-spacing:0;"
+|-
-| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''FEMM'''</center>
+!FEMM
-| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''ANSYS'''</center>
+!ANSYS
-| style="border-top:0.0361in double #000000;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>'''COMSOL'''</center>
+!COMSOL
-| style="border:0.0361in double #000000;padding:0.0729in;"| <center>'''Elmer Multiphysics'''</center>
+!ELMER MULTIPHYSICS
 |-
-| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>CG</center>
+|CG
-| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>iteračné gradientné metódy </center>
+|iteračné gradientné metódy
-| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>knižnica UMFPACK</center>
+|knižnica UMFPACK
-| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>knižnica UMFPACK</center>
+|knižnica UMFPACK
 |-
-| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>BCG</center>
+|BCG
-| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>AMG</center>
+|AMG
-| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>GMRES</center>
+|GMRES
-| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>AMG a GMG</center>
+|AMG  a GMG
 |-
-| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>&nbsp;</center>
-| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>&nbsp;</center>
-| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:none;padding:0.0729in;"| <center>&nbsp;</center>
-| style="border-top:none;border-bottom:0.0361in double #000000;border-left:0.0361in double #000000;border-right:0.0361in double #000000;padding:0.0729in;"| <center>iteračné gradientné metódy </center>
+|iteračné gradientné metódy
 |}
 '''Ukážkový príklad analýzy vo FEMM'''
@@ Riadok 84: / Riadok 72: @@
-Obr. 4 Model asynchrónneho motora vo FEMM
+[[Image:Model asynchrónneho motora vo FEMM.png|center|framed|Obr. 4 Model asynchrónneho motora vo FEMM]]
-[[Image:Untitled%201_html_d245593.png]]Obr. 5 Rozloženie poľa asynchrónneho motora
+[[Image:Untitled%201_html_d245593.png|center|framed|Obr. 5 Rozloženie poľa asynchrónneho motora]]
 Na (obr. 5) je vyriešené rozloženie potenciálu pre daný asynchrónny motor. Riešenie danej úlohy metódou bikonjugovaných gradientov prostredníctvom softvéru FEMM trvalo 3 minúty. Riešenie bolo realizované na počítači s&nbsp;procesorom AMD Turion X2 Dual-Core 2.20 GHz a&nbsp;s&nbsp;operačnou pamäťou 4 GB.

← Staršia verzia		Verzia zo dňa a času 21:49, 30. máj 2010
Riadok 24:		Riadok 24:


−	Algoritmy rozkladu matíc	+	'''Algoritmy rozkladu matíc'''

	Rozklad môže vykonaný rôznymi spôsobmi, čo závisí od prístupu k jednotlivým prvkom systému. Existujú tri základné typy algoritmov : left-looking, right-looking a multifrontal.		Rozklad môže vykonaný rôznymi spôsobmi, čo závisí od prístupu k jednotlivým prvkom systému. Existujú tri základné typy algoritmov : left-looking, right-looking a multifrontal.

@@ Riadok 1: / Riadok 1: @@
+[[Kategória:Študentské práce]]
+[[Kategória:Ročníkové práce]]
@@ Riadok 89: / Riadok 93: @@
 Na (obr. 5) je vyriešené rozloženie potenciálu pre daný asynchrónny motor. Riešenie danej úlohy metódou bikonjugovaných gradientov prostredníctvom softvéru FEMM trvalo 3 minúty. Riešenie bolo realizované na počítači s&nbsp;procesorom AMD Turion X2 Dual-Core 2.20 GHz a&nbsp;s&nbsp;operačnou pamäťou 4 GB.

← Staršia verzia	Verzia zo dňa a času 20:20, 30. júl 2010
(Žiaden rozdiel)