Algoritmy pro výpočet Smithova normálního tvaru /
V této bakalářské práci se věnujeme algoritmům pro výpočet Smithova normálního tvaru celočíselných matic, který nalézá uplatnění například při řešení soustav celočíselných rovnic nebo při počítání simpliciálních homologií. Protože v průběhu výpočtu Smithova normálního tvaru můžeme už pro malé matice...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Čeština |
| Vydáno: |
2015
|
| Témata: | |
| On-line přístup: | http://is.muni.cz/th/408420/prif_b/ |
| Shrnutí: | V této bakalářské práci se věnujeme algoritmům pro výpočet Smithova normálního tvaru celočíselných matic, který nalézá uplatnění například při řešení soustav celočíselných rovnic nebo při počítání simpliciálních homologií. Protože v průběhu výpočtu Smithova normálního tvaru můžeme už pro malé matice narazit na problémy s bitovou délkou mezivýsledků, uvádíme zde algoritmus, pro nějž odvozujeme odhad na mezivýsledky. Tento algoritmus modifikujeme tak, abychom mohli s využitím Čínské zbytkové věty garantovat dostatečně malou bitovou délku mezivýsledků. Modifikace algoritmu navíc umožní jistou míru paralelizace výpočtu. In this thesis we study algorithms for computing the Smith normal form of integer matrices which can be used to solve systems of linear Diophantine equations or in the process of computing simplicial homology groups. In the computation of the Smith normal form, even for small matrices, one can easily run into problems with the bit length of intermediate results. For that reason we introduce a refined algorithm and present bounds on its intermediate results. This algorithm is then modified using the Chinese reminder theorem to provide reasonably small bounds on the bit length of intermediate results. This modifications also allows a certain level of parallelization. |
|---|---|
| Popis jednotky: | Vedoucí práce: Lukáš Vokřínek |
| Fyzický popis: | 36 listů |