Tady bude oficiální zadání práce.
2
České vysoké učení technické v Praze Fakulta elektrotechnická
Bakalářská práce
Generátor řídkých matic
Tomáš Bílek
Vedoucí práce: Ing. Ivan Šimeček, Ph.D.
Studijní program: Elektrotechnika a informatika strukturovaný bakalářský Obor: Výpočetní technika červen 2009
iv
Poděkování: Děkuji panu Ing. Ivanu Šimečkovi, Ph.D., mj. vedoucímu mé bakalářské práce, za výborné vedení a cenné rady při tvorbě generátoru řídkých matic, nejenom v oblasti návrhu, ale i v části implementační.
v
vi
Prohlášení: Prohlašuji, že jsem svou bakalářskou práci vypracoval samostatně a použil jsem pouze podklady, které uvádím v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č.121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon). V Praze dne 11. 6. 2009 ………………………….
vii
viii
Abstract: Tomáš Bílek, The generator of sparse matrix. This work contains analysis and implementation of the generator of sparse matrix with simple graphics interface. The generator will generate random and band sparse matrix. The output of this work will be this document and application. Even this document will be attached with a CD of source codes, runnable application in environment JRE v. 6 and others materials, which will be published.
Abstrakt: Tomáš Bílek, Generátor řídkých matic. Tato práce se zaměřuje na analýzu a implementaci generátoru řídkých matic s jednoduchým grafickým rozhraním. Generátor bude zaměřen na generování náhodných a pásových řídkých matic. Výsledkem práce bude tento dokument a program. Zároveň k tomuto dokumentu bude přiložené CD se zdrojovými kódy, spustitelnou aplikací v prostředí JRE v. 6 a dalšími materiály, které zde budou uvedené.
ix
x
Obsah
1
Úvod ........................................................................................................... 1 1.1
Popis problému ..................................................................................... 1
1.2
Definice matice ..................................................................................... 2
1.3
Druhy matic .......................................................................................... 3
1.3.1
Řádková matice .............................................................................. 3
1.3.2
Sloupcová matice ............................................................................ 3
1.3.3
Čtvercová matice ............................................................................ 3
1.3.4
Diagonální matice ........................................................................... 3
1.3.5
Jednotková matice .......................................................................... 4
1.3.6
Symetrická matice .......................................................................... 4
1.3.7
Horní trojúhelníková matice ............................................................ 4
1.3.8
Dolní trojúhelníková matice ............................................................ 4
1.3.9
Pásová matice ................................................................................. 5
1.3.10 2
3
Řídká matice ............................................................................... 5
Reprezentace řídkých matic v paměti (souboru) ........................................... 7 2.1
Compressed Row Storage (CRS) ........................................................... 8
2.2
Compressed Column Storage (CCS) .................................................... 10
2.3
Compressed Diagonal Storage ............................................................. 11
2.4
Old Yale sparse matrix formát ............................................................. 12
2.5
New Yale sparse matrix formát............................................................ 13
Analýza a návrh implementace .................................................................. 15 3.1
Analýza prostředí ................................................................................ 15
3.2
Průběh činnosti programu .................................................................... 16
3.3
Komponenty systému .......................................................................... 18 xi
4
3.3.1
Komponenta Matrix Generator ...................................................... 20
3.3.2
Komponenta Matix Saver .............................................................. 22
3.3.3
Komponenta GUI .......................................................................... 22
3.3.4
Komponenta Main Controller ........................................................ 23
Popis implementace ................................................................................... 25 4.1
Struktura systému ................................................................................ 25
4.1.1
Komponenta Matix Generator ........................................................ 25
4.1.2
Komponenta Matrix Saver ............................................................. 37
4.1.3
Komponenta Main Controller ........................................................ 40
4.1.4
Komponenta GUI .......................................................................... 40
5
Ukázka výstupu generátoru řídkých matic .................................................. 45
6
Závěr ......................................................................................................... 47
7
Seznam použité literatury ........................................................................... 49
Příloha A: Obsah přiloženého DVD .................................................................. 51 Příloha B: Uživatelský manuál ......................................................................... 53
xii
Seznam obrázků
Obrázek 1 Obecný zápis matice .......................................................................... 2 Obrázek 2 Konkrétní zápis ................................................................................. 2 Obrázek 3 Příklad diagonální matice .................................................................. 3 Obrázek 4 Příklad horní trojúhelníkové matice ................................................... 4 Obrázek 5 Příklad pásové (band) matice ............................................................. 5 Obrázek 6 Příklad řídké matice č. 1 .................................................................... 6 Obrázek 7 Příklad řídké matice č. 2 .................................................................... 6 Obrázek 8 Zjednodušené schéma uložení řídké matice ........................................ 7 Obrázek 9 Compressed Row Storage .................................................................. 9 Obrázek 10 Compressed Column Storage ......................................................... 10 Obrázek 11 Compressed Diagonal Storage ....................................................... 11 Obrázek 12 Příklad Old Yale sparse matrix formátu ......................................... 12 Obrázek 13 New Yale sparse matrix formát ...................................................... 13 Obrázek 14 Diagram aktivit ............................................................................. 17 Obrázek 15 Diagram komponent ...................................................................... 19 Obrázek 16 Vývojový diagram pro vygenerování množství nenulových prvků na řádek ............................................................................................................... 28 Obrázek 17 Vývojový diagram generování indexů sloupců a hodnot ................. 32 Obrázek 18 Vývojový diagram průběhu generování pásové matice ................... 36 Obrázek 19 Grafické uživatelské rozhraní, karta pro náhodné matice ................ 42 Obrázek 20 Grafické uživatelské rozhraní, karta pro pásové matice .................. 42 Obrázek 21 Ukázka okna Nápověda ................................................................. 43 Obrázek 22 Ukázka okna O Programu .............................................................. 43
xiii
xiv
Seznam tabulek
Tabulka 1 Symetrická náhodná matice.............................................................. 35 Tabulka 2 Ukázka hlavičky výstupního souboru ve formátu MM coordinate ..... 40
xv
xvi
1 Úvod
1.1 Popis problému
Vlastnit nějaký prostý, rychlý a přehledný generátor řídkých matic by chtěl, při nejmenším, téměř každý vývojář algoritmů, které jsou učené nejenom pro provádění matematických operací nad těmito maticemi. Přitom by nemělo jít pouze o řídké matice s plně náhodným rozmístěním nenulových prvků, ale i o matice, jejichž rozmístění nenulových prvků by bylo podmíněno pomocí předem předdefinovaných kritérií, ze kterých by si uživatel zvolil. Takto vygenerované matice by se ukládaly do uživatelem určeného souboru. Ovšem, existují i jiné programy, které umějí generovat řídké matice, např. MatLab, ale to už vyžaduje mít tento program nainstalovaný a umět s ním pracovat. Hlavním cílem práce bude tedy vytvořit program, který bude mít výše vyjmenované vlastnosti. Mimo těchto vlastností by měl být multiplatformní, s jednoduchým a dostatečně přehledným uživatelským rozhraním. Protože možností generování řídkých matic je nespočetně mnoho, měla by být výsledná implementace otevřená pro rozšíření o další metody generování bez větších komplikací. Vstupy programu se budou z velké části odvíjet od toho, jaký typ generování matice použijeme. Obecně lze říct, že vstupem budou omezující kritéria pro vygenerování matice. Výstup programu bude soubor, obsahující zápis matice v předem zvoleném formátu. Abychom mohli takový program vytvořit, je vhodné, se nejprve seznámit s maticemi jako takovými a řídkými maticemi.
1
1.2 Definice matice
Pojem matice se v matematice používá pro označení obdélníkové tabulky čísel nebo nějakých matematických objektů – prvky matice (též elementy matice). Obecně matice obsahuje m řádků a n sloupců. Pak hovoříme o matici typu m×n. Ve většině případů se matice využívají pro obecné rotace vektorů, transformace vektorů od jedné báze k jiné bázi, k řešení soustav lineárních rovnic anebo také k vyjádření operátorů v kvantové mechanice. Jednotlivé prvky matice označujeme indexy, které udávají řádek a sloupec, v nichž se prvek nachází.
Prvek v i-tém řádku a v j-tém sloupci matice A se
obvykle označuje a ij . Např. a 23 označuje prvek, který se nachází na druhém řádku ve třetím sloupci. Existuje i označení a 2 3 , které se používá pokud potřebujeme rozlišovat kovariantní a kontravariantní indexy, ale tím se v této práci hlouběji zabývat nebudeme.
Obrázek 1 Obecný zápis matice
Obrázek 2 Konkrétní zápis
2
1.3 Druhy matic
Pro vyřešení zadání je zapotřebí se blíže seznámit s jednotlivými druhy matic. Druhů matic je mnoho, ale my se zaměříme na ty, které mají něco společného s pravidelným či logickým uspořádáním prvků v matici. Logickým či pravidelným uspořádáním budeme mít na mysli např. umístění všech nenulových prvků v jednom řádku matice a zbytek prvků v matici s nulovými hodnotami nebo umístění nenulových prvků kolem hlavní diagonály, apod. 1.3.1 Řádková matice Je matice typu 1 × n, která je tvořena jedním řádkem. 1.3.2 Sloupcová matice Je matice typu m × 1, která je tvořena jedním sloupcem. 1.3.3 Čtvercová matice Platí-li n=m, nebo-li počet řádků matice je shodný s počtem sloupců matice, pak tuto matici označujeme jako čtvercovou matici n-tého řádu (stupně). Matici, u které platí n ≠ m, označujeme jako matici obdélníkovou. 1.3.4 Diagonální matice Je matice, která obsahuje nenulové prvky pouze na hlavní diagonále, tzn. a ij = 0 pro i ≠ j a a ij ≠ 0. Diagonální matici označujeme písmenem D.
Obrázek 3 Příklad diagonální matice
3
1.3.5 Jednotková matice Je speciální případ diagonální matice, která na své hlavní diagonále obsahuje samé jedničky. Tuto matici označujeme písmenem E. 1.3.6 Symetrická matice Matici A považujeme za symetrickou, pokud transponovaná matice A T je shodná s původní maticí A, tzn. A T = A. 1.3.7 Horní trojúhelníková matice Je matice, jejíž všechny prvky pod hlavní diagonálou nabývají nulových hodnot.
Obrázek 4 Příklad horní trojúhelníkové matice
1.3.8 Dolní trojúhelníková matice Je matice, která má všechny prvky nad hlavní diagonálou nulové.
4
1.3.9 Pásová matice Je matice, která rozšiřuje diagonální matici a to tím způsobem, že podél hlavní diagonály jsou vedeny další diagonály, které jsou složené pouze z nenulových prvků.
Obrázek 5 Příklad pásové matice
1.3.10
Řídká matice
V matematickém odvětví se označení řídká matice používá pro matice, jejichž počet nenulových prvků je menší než 10%. Uvedených 10% je třeba brát s rezervou, protože někdy se uvádí, že tato hodnota má být 5%. Z toho vyplývá, že neexistuje ostrá hranice, od které je možné danou matici označit za řídkou. Toto označení se také odvíjí od toho, jak efektivně můžeme danou matici uložit, čímž se vlastně budeme dále zaobírat. Některé matice můžou mít 30% a něco více nenulových prvků, ale vzhledem k tomu, jak jsou uspořádány, může být označena za řídkou matici. Jako příklad se můžou uvést 2 matice, které mají shodný n nenulových prvků, ale jedna z nich má tyto prvky náhodně rozmístěné po celé své ploše a druhá má všechny prvky souvisle uloženy v několika řádcích. S tím souvisí uložení matice do paměti (souboru), kdy je určitě jednodušší určit začátek a konec bloku, který obsahuje po sobě jdoucí nenulové prvky matice, než každému jednotlivému prvku přiřadit konkrétní umístění pomocí indexu řádku a sloupce. Text a obrázky jsou převzaty ze zdroje [1] a [2].
5
Obrázek 6 Příklad řídké matice č. 1
Obrázek 7 Příklad řídké matice č. 2
6
2 Reprezentace řídkých matic v paměti (souboru)
Toto téma je obecně obecn velice rozsáhlé, protože metod pro ukládání dat do paměti jee velice mnoho. Důvod velkého množství metod pro uložení úzce souvisí s charakteristickým uspořádáním uspo nenulových prvků v řídké matici. Z toho vyplývá, že pro každý typ řídké matice je vhodná jiná metoda pro uložení. Všeobecně se proto nedá určit, ur která metoda je nejvhodnější jší pro ukládání řídkých matic, protože tento výběr výb závisí na konkrétním typu řídké ídké matice. Ve výsledném programu použijeme pouze formát CRS, i když pro pásovou matici by byl vhodný formát CDS. Důvod vod takového použití po je čistě implementační, implementač ale nic nebrání tomu, aby matice byly ukládaný do souborů v níže uvedených formátech.
Obrázek 8 Zjednodušené schéma uložení řídké ídké matice
Další informace jsou uvedeny na adrese [3].
7
2.1 Compressed Row Storage (CRS)
Jeden z hlavních a nejjednodušších formátů pro uložení řídkých matic. Formát si předem nevytváří žádnou analýzu o struktuře řídké matice, a také neukládá žádné nadbytečné prvky matice, tedy její nulové prvky. Princip CRS formátu spočívá v uložení sekvence nenulových prvků, které se nacházejí na jednom řádku matice do souvislého paměťového prostoru. Předpokládejme,
že
máme
nesymetrickou
řídkou
matici
A.
Matice
je
reprezentována prostřednictvím tří polí, první dvě pole col_ind a row_ptr, určují polohu nenulových prvků a třetí, s názvem val, obsahuje hodnoty nenulových prvků matice A uložené řádek po řádku (tzv. row-wise). Pole col_ind obsahuje indexy sloupců prvků, které jsou obsahem pole val. Z toho vyplývá, že velikosti obou polí jsou stejné (co se týká počtu položek) a platí-li val(k) = a i,j pak col_ind(k) = j, kde i je číslo řádku, j je číslo sloupce matice A a index k slouží jako index do pole col_ind. Pole row_ptr v sobě uchovává indexy na prvky v poli val, které jsou prvními nenulovými prvky matice A v řádku i. Matematicky můžeme vyjádřit následovně: jestli-že platí val(k)=a i,j , pak row_ptr(i) ≤ k < row_ptr(i + 1). Velikost pole row_ptr je rovna m + 1, kde m je počet řádků matice. Protože nejnižší index řádku a sloupce je 1, obsahuje row_ptr(0) defaultní hodnotu 1. To umožňuje snadné zjištění počtu prvků na prvním řádku matice pouhým odečtením hodnot row_ptr(1) – row_ptr(0). Úspora místa, při použití formátu CRS pro uložení matice, je značná. Místo uložení n 2 prvků si vystačíme pouze s 2nnz + m + 1 jednotek pro uložení, kde nnz je počet nenulových prvků. Výše popsaný princip graficky znázorňuje Obrázek 9.
8
Obrázek 9 Compressed Row Storage
9
2.2 Compressed Column Storage (CCS)
Patří do stejné skupiny jako formát CRS a jeho princip je analogický s principem CRS. Tento formát je někdy také nazýván jako Harwell-Boeingův. Formát. CCS je identický s CSR formátem, ale hodnoty nenulových prvků matice A jsou do pole val ukládány po sloupcích místo po řádcích. Jinými slovy můžeme říct, že CCS formát je CRS formát pro A T . Základem je opět rozložení matice do tří polí (val, row_ind, col_ptr), kde pole row_ind obsahuje indexy řádků,do kterých patří hodnoty z pole val. Dalším polem je col_ptr a jeho velikost je rovna počtu sloupců + 1, tedy n + 1. Protože řádky a sloupce jsou číslovány od indexu 1, obsahuje pole col_ptr na indexu 0 defaultní hodnotu 1. Opět slouží pro snadné zjištění počtu prvků v prvním sloupci matice. Ukázka formátu CCS je na obrázku Obrázek 10.
Obrázek 10 Compressed Column Storage
10
2.3 Compressed Diagonal Storage
Jestli-že matice A je tvořená pásy nenulových prvků kolem podél hlavní diagonály a samotná diagonála je také tvořená nenulovými prvky, je výhodné využít tuto vlastnost ve formátu, ve kterém matici A uložíme. Schéma pro tento formát se zakládá na uložení vedlejších diagonál matice spolu s hlavní diagonálu v souvislém datovém prostoru. Výhoda formátu je v ušetření místa pro zaznamenávání pozice pro jednotlivé prvky nebo menší bloky. Na začátku nám stačí určit, o kterou diagonálu se jedná a následně souvisle uložit prvky z konkrétní diagonály. Nevýhoda v tom, že se tato metoda dá použít pouze na velmi úzký okruh řídkých matic. Matice A=(a i,j ) je pásová, jestli-že obsahuje nezáporné konstanty p, q nazývaná jako levá a pravá halfbandwidth, pak a i,j ≠ 0 pouze když i-p ≤ j ≤ i+p. Pro takovou matici A pak stačí alokovat pole val o velikosti (1:n, p:q). Obrázek 11 demostruje použití CDS na matici A. Matici A ukládáme v poli val s dimenzí (6, -1:1) při použití mapování val(i,j)=a i,i+j .
Obrázek 11 Compressed Diagonal Storage 11
2.4 Old Yale sparse matrix formát
Formát plně totožný s formátem CRS, který je uvedený v podkapitole 2.1. Jedná se pouze o přejmenování polí, které reprezentují řídkou matici. Pole A reprezentuje pole val. Pole JA je ekvivalentní s polem col_ind, obsahuje tedy indexy sloupců. Poslední pole IA je určeno pro ukazatele na konce řádků a jeho vlastnosti korespondují s polem row_ptr ve formátu CRS.
Obrázek 12 Příklad Old Yale sparse matrix formátu
12
2.5 New Yale sparse matrix formát
Je obdoba formátu Old Yale Sparse Matrix, která vychází z nepsaného pravidla, že prvky umístěné na hlavní diagonále jsou ve většině případů nenulové a může k nim být častěji přistupováno, než k prvkům mimo diagonálu. Proto se prvky z hlavní diagonály ukládají odděleně do jiného pole, které má velikost m. Tím jsme ušetřeni zavádění čísel sloupců těchto prvků Nový vzniklý prostor v poli JA se vyplní hodnotami z pole IA. Pole vzniklé sloučením těchto dvou polí označujeme jako IJA. Jeho velikost se rovná počtu všech nenulových prvků + 1. Rozdíl mezi Old Yale sparse matrix a New Yale sparse matrix pěkně znázorněno na obrázku Obrázek 13.
Obrázek 13 New Yale sparse matrix formát
Uvedené obrázky a texty jsou převzaté z elektronických zdrojů [4], [5], [6] a [7].
13
14
3 Analýza a návrh implementace
V předchozí kapitole byly představeny metody jak reprezentovat řídké matice v paměti. To bude zejména důležité při návrhu generujících algoritmů. I když v tomto případě nám postačí jednoduchý formát CRS, můžou se popsané techniky použít pro reprezentaci matic ve výstupních souborech programu. Nicméně v této kapitole se budeme zabývat analýzou programu. Nejprve určíme technologii, na které program postavíme a následně rozdělíme aplikaci do komponent. Dále si naznačíme, co bude obsahem těchto komponent a jakým způsobem bude probíhat komunikace mezi nimi. V neposlední řadě bude uvedeno rozvržení grafické části aplikace.
3.1 Analýza prostředí
Než začneme navrhovat program, je vhodné určit, na jaké technologii bude postaven. V úvodu je naznačeno, že aplikace má být multiplatformní a proto bylo zvoleno, že aplikace bude postavena na technologii Java, konkrétně na verzi 1.6. Ta zajistí bezproblémový běh aplikace na operačních systémech Windows a operačních systémech založených na technologii UNIX. Konečná aplikace bude soubor typu .jar, který je spustitelný v prostředí jre (Java Runtime Environment). Jelikož má být aplikace má obsahovat grafické rozhraní, nepředpokládají se žádné vstupní parametry, kterými by se řídila činnost aplikace. Vzhledem k tomu, že samotná aplikace nebude využívat žádné systémové knihovny ani jiné softwarové prostředky kromě těch, které poskytuje prostředí jre, můžeme se pustit do další analýzy programu.
15
3.2 Průběh činnosti programu
Hlavní činnosti programu bude vygenerování řídké matice a následně její uložení do souboru. Parametry matice se budou zadávat prostřednictvím editovatelných polí zobrazených na uživatelském rozhraní. Uživatelské rozhraní bude spouštěno zároveň s hlavním programem. Mezi vstupní parametry patří i výběr souboru, do kterého se má uložit vygenerovaná řídká matice. Předtím, než se vůbec spustí generování matice do paměti, se provede kontrola vstupních dat. Po uložení vygenerované matice z paměti do souboru zůstanou zadané vstupní parametry zobrazené v uživatelském rozhraní a uživatel bude mít možnost tyto parametry pozměnit a nechat matici znovu vygenerovat. Jak je vidět, samotný průběh zadání vstupních parametrů včetně určení výstupního souboru není nikterak složitý. To pomůže k vytvoření jednoduchého uživatelského grafického rozhraní. Průběh činnosti programu je znázorněn na obrázku Obrázek 14.
16
Obrázek 14 Diagram aktivit
17
3.3 Komponenty systému
Velice důležitá část návrhu, která při správné analýze umožní vytvořit přehlednou aplikaci a přispěje k jednodušší implementaci. Protože aplikace má být jednoduše rozšířitelná, bude nutné s touto skutečností počítat. Proto aplikaci rozdělíme do jednotlivých komponent. Komponenty budou poskytovat rozhraní, přes které budou schopné přijímat požadavky a komunikovat s ostatními komponentami. Protože aplikace má obsahovat grafické rozhraní, bude existovat právě jedna komponenta, která bude obstarávat grafické rozhraní a poskytovat funkce pro komunikaci s ní. Další komponenty si uvedeme v následujících odstavcích. Důležité je, že z toho rozdělení vyplývá použití softwarové architektury zvané MVC (Model – View - Controller), která oddělí grafickou část od programové. Navíc pomocí MVC a výše zmíněným dělením se dosáhne k celkovému zpřehlednění systému a spolu se správnou volbou komponent umožní snadné rozšíření celého systému. Vzhledem k tomu, že MVC architektura je víceméně objektově založena, je pro tuto skutečnost jazyk Java přímo stvořený. Základ celého systému tvoří komponenta Main Controller. Její hlavní činnosti je přijímat a vyhodnocovat data, která na vstupu zadá uživatel. Tento proces
předávání
uživatelských
vstupních
dat
probíhá
prostřednictvím
komponenty GUI. Mimo zadávání uživatelských vstupních dat komponenta umožňuje zobrazování varovných hlášení neboli výjimek, které se vyskytly v průběhu
kontroly
uživatelského
vstupu
nebo
při
startu
běhu
některých komponent. Další komponentou je Matrix Generator. Komponenta má na starost generování zmíněných řídkých matic. Jaká matice se bude generovat, určí Main Controller zavoláním příslušné metody z komponenty Matrix Generator. Výběr metody se odvíjí od zadaného vstupu. Poslední komponentou systému je Matrix Saver. Matrix Saver má za úkol uložit předanou matici, ve formátu CRS, do souboru. Oddělení komponenty Matrix Saver od komponenty Matrix Generátor s sebou nese jednu velkou výhodu, která byla v průběhu tvorby využita. Původně komponenta uměla ukládat 18
matici pouze ve formátu CRS, ale následně bylo rozhodnuto, že ukládání bude v MM Coordinate formátu. Proto stačilo vytvořit další třídu se stejnými metodami, která umí uložit matice v takovémto formátu. Proto rozšíření programu o další ukládací algoritmy nebude vůbec obtížné. Taktéž nebude obtížné rozšíření komponenty Matrix Generator
o další třídy pro generování
řídkých matic. Rozdělení aplikace do komponent tak, jak bylo popsáno výše, je zobrazeno na obrázku Obrázek 15. Z obrázku je jasně vidět, že veškeré řízení bude obstarávat komponenta Main Controller.
Obrázek 15 Diagram komponent
19
3.3.1 Komponenta Matrix Generator Jak už bylo naznačeno, komponenta Matix Generator bude sobě sdružovat algoritmy pro generování řídkých matic. Algoritmy pro jednotlivé typy matic budou rozděleny do tříd, které prostřednictvím svých metod umožní vygenerovat konkrétní matice do paměti. Protože generátor v této verzi bude umět generovat 2 typy matic, bude komponenta Matix Generator obsahovat právě dvě třídy. První třída s názvem Simple bude určená pro generování náhodné řídké matice. Druhá se jménem Band bude sloužit pro generování pásové řídké matice. Bude-li to v budoucnu zapotřebí, může se tato komponenta rozšířit o další třídy s tím, že se vhodně doplní metody pro uložení v třídách obsažených v komponentě Matix Saver. Protože tříd pro generování může být nespočetně mnoho, tak pro dodržení základní funkčnosti budou muset implementovat základní výstupní CRS interface. Interface bude obsahovat metody pro získání obsahu polí reprezentující řídkou matici ve formátu CRS.
3.3.1.1 Náhodná matice (třída Simple) Pod pojmem náhodná matice se v programu skrývají tyto druhy matic: 1. Matice s jedním a více nenulových prvků na řádku umístěných tak, že jsou od sebe, ve většině případů, odděleny nulovým prvkem. 2. Matice
s několika
nenulovými
prvky
na
řádku,
které
svým
uspořádáním tvoří „čárky“ o určité délce. Dále každá z výše uvedených matic může mít vlastnost: i.
Symetrická matice
ii.
Dolní trojúhelníková matice
iii.
Horní trojúhelníková matice
Dalším požadavkem na matici může být „regulárnost“. V tomto případě se nejedná o regulárnost matice jako takovou, že hodnost matice se musí rovnat
20
počtu řádků, ale o „regulárnost“, která zaručuje, že v každém řádku bude alespoň 1 nenulový prvek. Při prvních fázích vývoje bylo počítáno s tím, že se vytvoří algoritmy jak pro matici 1. typu, tak pro matici 2. typu. Nakonec se od toho řešení upustilo, protože hlubší analýzou bylo dospěno k závěru, že by tyto 2 typy matic by mohl řešit pouze 1 algoritmus. Následkem této skutečnosti byl zaveden pojem element matice: Element matice - definuje minimální počet nenulových prvků vedle sebe. Pro větší exaktnost si uvedeme další pojem a to je normální matice: Normální matice – matice, která nemá jiná kritéria, než je šířka elementu a „regulárnost“.
Vstupem všech náhodných matic bude: 1. Element – jeho šířka (velikost) 2. Velikost matice 3. Počet nenulových prvků 4. „Regulárnost“ Výstupem všech náhodných matic bude matice ve formátu CRS.
3.3.1.2 Pásová matice (třída Band) Pojmem pásová matice se rozumí matice, která v základu obsahuje po celé hlavní
diagonále
nenulové
prvky.
Širší
pás
vzniká
přidáváním
dalších
subdiagonál těsně nad nebo těsně pod hlavní diagonálu. Přidávané subdiagonály opět obsahují po celé své délce nenulové prvky. Už z toho, co bylo uvedeno, vyplývá, že pro vygenerování pásové matice bude zapotřebí znát šířku pod a nad hlavní diagonálou. Dalším parametrem bude symetričnost matice. Nakonec jako každá matice musí být při generování známa velikost matice, proto posledním parametrem bude velikost matice.
21
Pro pásovou matici bude vstupem: 1. Velikost matice 2. Šířka pásu nad diagonálou 3. Šířka pásu pod diagonálou 4. Symetie Výstupem pásových matic bude matice ve formátu CRS.
3.3.2 Komponenta Matix Saver Komponenta Matix Saver v sobě bude sdružovat třídy pro ukládání řídkých matic do souborů ve zvoleném formátu. Původně jsem měl v plánu, že výstupem bude matice reprezentována ve formátu CRS, ale po konzultaci došlo ke změně na formát MM coordinate (Matrix Market). V tom nebyl žádný problém a tím se zároveň ukázalo, že systém je dobře navržený pro jeho další rozšíření. Jak už bylo předesláno, metody těchto tříd budou úzce propojené s metodami tříd obsažených v komponentě Matrix Generator. Důvod je takový, že je zamýšleno generovat pouze určité části matice do paměti z důvodu zefektivnění algoritmu a ušetření místa v paměti. Proto nebude moci být použitá pouze jedna metoda pro uložení všech matic zapsaný v CRS. Následek této skutečnosti je takový, že bude muset existovat více metod, které budou brát v úvahu, že předaná matice není úplná a bude jí potřeba během ukládání nějakým způsobem dopočítat nebo upravit. 3.3.3 Komponenta GUI Další z důležitých částí programu bude komponenta GUI. Komponenta bude sloužit pro zobrazení uživatelského rozhraní. Kromě hlavní okna a nápověd atd. bude obstarávat i zobrazování výjimek, které se vyskytnou buď během kontroly vstupních dat, nebo v době běhu některého z algoritmů. Hlavní okno se bude skládat z hlavního menu a záložek pro jednotlivé typy matic. V tomto případě budou záložky dvě, jedna pro náhodné matice, druhá pro 22
pásové matice. Oddělení je provedeno z důvodu, že se vstupní parametry obou typů matic od sebe liší. Naopak společné budou mít tlačítko pro výběr výstupního souboru a tlačítko pro vygenerování matice. Hlavní menu bude víceméně tradiční. Bude obsahovat položku pro ukončení programu a položky pro zobrazení nápovědy a informací o programu. Poslední dvě volby způsobí zobrazení nového okna a zároveň se deaktivuje hlavní okno do doby, než dojde k uzavření těchto nově vytvořených oken. Dalším úkolem komponenty GUI bude volat příslušné metody třídy z komponenty Main Controller. Opačný průběh volání metod bude v případě, když třída z komponenty Main Controller bude chtít zobrazit nějakou výjimku uživateli.
3.3.4 Komponenta Main Controller Jako můstek mezi všemi komponentami bude právě komponenta Main Controller. Bude obstarávat veškerou komunikaci mezi komponentami a to tak, že
bude,
ve
správném
pořadí,
volat
metody
tříd
obsažených
v těchto
komponentách. Sled volání metod bude určen na základě uživatelského vstupu. Pro předání parametrů z komponenty GUI bude mít Main Controller své vlastní veřejné metody. Metody budou zajišťovat ověření vstupů a v případě neshody provede zavolání metody z komponenty GUI. Ta zobrazí příslušné varování uživateli.
23
24
4 Popis implementace
V této kapitole se budeme zabývat implementací výše zmíněných komponent. Primárně se ale zaměříme na algoritmy generující řídké matice. Implementace ostatních tříd byla rutina, a protože analýza byla relativně dobře provedena, byla jejich implementace zcela bez potíží.
4.1 Struktura systému
Celý systém je rozčleněn do čtyř komponent. Nejdůležitější komponentou je Matrix Generator, která umí generovat řídké matice. Vývoj aplikace začal právě třídami z této komponenty. Spolu s ní probíhalo vytváření třídy z komponenty Matrix Saver, která jak už bylo mnohokrát zmíněno, úzce spolupracuje právě s třídami komponenty Matrix Generátor. Následně, po úspěšném otestování, byla vytvořena třída z komponenty Main Controller. Během tvorby Main Controlleru probíhala tvorba grafického rozhraní, kdy Main Controller byl souběžně doplňován o nezbytné metody pro komunikaci s GUI. A právě v tomto pořadí bude popsaná implementace uvedených komponent.
4.1.1 Komponenta Matix Generator Komponenta, která je označována za jádro celé aplikace. Část, která vykonává generování řídkých matic, obsahuje celkem 2 třídy. První třída Simple je určená pro generování náhodných matic, druhá třída Band pro generování pásových matic. Obě třídy se liší nejen prováděnou operací, ale taky konstruktory. Konstruktory se od sebe liší vstupními parametry a metodami, které poskytují.
25
Pro náhodnou matici je určen konstruktor z třídy Simple a jeho hlavička vypadá následovně:
Simple(int šířka_elementu, int velikost_matice, int počet_nenulových_prvků, boolean regularní); a pro pásovou matici se volá konstruktor třídy Band: Band(int šířka_pásu_pod_diagonálou, int šířka_pásu_nad_diagonálou, int velikost_matice);.
Třída Simple obsahuje metody: •
generateNormal() – metoda slouží pro vygenerování normální matice.
•
generateSymetricTriang() – metoda vygeneruje symetrickou matici, konkrétně její část nad hlavní diagonálou a samotnou hlavní diagonálu. Celá symetrická matice je vytvářená při ukládání do souboru.
•
generateUpperTriangle() – metoda vygeneruje horní trojúhelníkovou matici. Metoda neslouží pouze pro tento typ matice, ale i pro dolní trojúhelníkovou matici. O tom, jaký typ matice se uloží, se rozhodne použitím příslušné metody třídy z komponenty Matix Saver.
Třída Band obsahuje metody: •
generateNormal() – metoda generuje do paměti pásovou matici o zadaných parametrech.
•
generateSymetricValues() – metoda zajistí vygenerování diagonály a pásu nad hlavní diagonálou. Symetrická pásová matice je vytvářená během ukládání do souboru.
26
Mimo jiné, výše zmíněné třídy implementují metody pro získání obsahu polí rows[], cols[], vals[], které reprezentují formát CRS. Metody jsou typu getr 1 a jsou následující: •
int[] getRows() – vrací pole obsahující ukazatelé na konce řádků (dle specifikace formátu CRS).
•
int[] getCols() – vrací pole indexů sloupců (dle specifikace CRS).
•
int[] getVals() – vrací pole s nenulovými prvky z rozsahu -20 až 20, množinově <-20, 20> mimo 0.
4.1.1.1 Princip generování náhodných řídkých matic Princip, jakým se budou generovat náhodné matice, byl zvolen následovně. Původně se nabízelo několik řešení, kterými by se dalo generovat náhodné matice, např. souběžně generovat délky řádků matice a indexy sloupců, ale tady docházelo k omezení náhodnosti matice. Problém byl v tom, že i když byl znám počet nenulových prvků, které se ještě můžou vložit, aby nebyl překročen stanovený limit prvků, docházelo k tomu, že poslední generované řádky trpěly tím, že obsahovaly pouze minimální počet nenulových prvků. Proto jsem přistoupil k řešení, že se počet nenulových prvků na jednotlivé řádky vygeneruje samostatně. Po vygenerování se pak předají metodě, která už pouze bude doplňovat indexy sloupců s tím. Výhodou tohoto řešení bude, že bude předem znám počet nenulových prvků na řádek a vyvarujeme zmíněnému nedostatku. Generování počtu nenulových prvků na řádek popisu vývojový diagram na obrázku Obrázek 16.
1
V programovacím jazyce Java se označení getr používá zejména pro metody přistupující k privátním proměnným daného objektu a vracejí jejich obsah. Opakem jsou setry, které slouží pro nastavování privátních proměnných. 27
Start
1. Vypočti průměrný počet elementů na řádek 2. Vypočti rozšířený průměrný počet elementů na řádek
Je matice „regulární“?
ANO
NE 3. Nastav minimální počet elementů na 1
3. Nastav minimální počet elementů na 0
4. Ke každé řádce matice vygeneruj množství nenulových prvků
Nadbývá množství nenulových prvků?
NE
ANO
NE Nedostatek nenulových prvků?
ANO
5. Snížit počet nenulových prvků na požadované množství
6. Zvýšit počet nenulových prvků na požadované množství
Konec Obrázek 16 Vývojový diagram pro vygenerování množství nenulových prvků na řádek
28
Pozn. č. 1: V textu se často zaměňuje pojem element za nenulové prvky. V principu jsou nenulové prvky přepočítané z elementů. Je zapotřebí si uvědomit, že ne vždy se podaří odebrat nebo přidat celý element, je-li matice např. trojúhelníkového typu a ve výsledku má být regulární. Tím chci naznačit, že do řádku, který má max. délku 2 se nedá vložit celý element o šířce 5 a proto dochází ke vkládání nenulových prvků neboli tzv. zkrácených elementů. Pozn. č. 2: Zkracování elementů se musí provádět u „regulární“ horní a dolní trojúhelníkové matice. Dále bývá tato jev způsobován symetrickými maticemi a to tehdy, leží-li nějaký prvek na diagonále. Tyto prvky se tzv. nedvojí při vytváření symetrické matice, s čím je počítáno při generování prázdné matice. Má-li být matice řídká, je pravděpodobnost výskytu nenulového prvku na diagonále velice malá.
Vysvětlení vývojového diagramu zobrazeného na obrázku Obrázek 16: 1. Spočte se průměrný počet elementů na řádek. 2. Spočte se rozšířený průměrný počet elementů na řádek a to tak, že se přičte polovina průměrného počtu elementů na řádek k stávající hodnotě. Tím se stanoví prozatímní maximální počet elementů na řádek. 3. Určí se minimální počet elementů na řádek. Ve všech případech, které jsem potřeboval, se hodnota pohybovala mezi čísly 0 a 1. Minimální počet elementů s hodnotou 1 se nastavuje tehdy, má-li být výsledná matice „regulární“, jinak 0. 4. Řádek po řádku se do statického pole rows[velikost
matice]
generuje počet prvků na řádek (jak jsou řádky reprezentované v CRS formátu je uvedené v podkapitole 2.1, ale místo ukazatelů na konce řádků zde zatím bude počet prvků na řádek). Počet prvků na řádek ve většině případů odpovídá celistvému násobku elementů. Případy, kdy tomu tak není, se vyskytují tehdy, když se do řádku nevejde celý element. Více k této problematice v poznámce č. 2. Důležité je, že taková matice je zcela náhodná.
29
5. V další fázi se nachází kontrola počtu prvků. První část kontroly zjišťuje, zda počet vygenerovaných prvků je nadbytečný. Je-li počet nadbytečný, dojde k odebírání elementů (nenulových prvků). To se provádí while cyklem. Ještě před jeho samotným spuštěním se provede náhodné vygenerování čísla řádku, od kterého se začnou odebírat prvky. Tento náhodný výběr řádku přispívá ke zvýšení náhodnosti matice. Elementy se začnou odebírat tak, že se stanoví maximální možný počet prvků k odebrání (bere se ohled na zachování „regulárnosti“ matice). Z tohoto stanoveného počtu se generátorem náhodných hodnot vygeneruje počet elementů k odebrání. Minimální počet prvků, který se vždy odebere je 1, tím je zaručeno, že while cyklus nepoběží nekonečněkrát. 6. V druhé části kontroly se zjišťuje, jestli je množství nenulových prvků menší, než je přípustné. Pokud ano, je princip přidávání elementů analogický s principem odebírání elementů v bodě č. 5. Výše uvedeným postupem získáme pole rows[], které obsahuje počet nenulových prvků na řádek. Tento formát sice neodpovídá formátu CRS, ale můžeme ho snadno vytvořit. Celková cena pro vytvoření bude minimální, bude se rovnat velikosti pole rows[]. Bohužel je toto největší míra náhodnosti, kterou se podařilo dosáhnout. Obecně se náhodnost všech algoritmů jevila jako velký problém. Nicméně se tím vyřešil problém, který je nastíněn výše a to, že poslední generované řádky netrpí nedostatkem prvků. Doteď byly předchozí odstavce věnovány problematice generování velikosti řádků. Proto je čase se obeznámit s generováním indexů sloupců a nenulových prvků. Další fáze je generování indexů sloupců do pole cols[počet prvků matice]. Zde získáváme velkou výhodu, protože už známe, kolik nenulových prvků se může vložit na daný řádek a nemusí se brát ohled na zbývající řádky.
30
Zároveň ve fázi generování indexů sloupců probíhá generování náhodných hodnot do pole vals[počet nenulových prvků]. Je to z toho důvodu, že pole vals[] je stejně velké jako pole cols[]. To nám dovoluje vložit hodnotu indexu sloupce na pozici cols[i] a zároveň na pozici vals[i] náhodně vygenerovanou hodnotu nenulového prvku.. Tímto ušetříme program jednoho for cyklu, který by prošel celé pole vals[] a každé jeho položce by vygeneroval hodnotu nenulového prvku. V některých
případech
je
generování
indexů
sloupců
specifickou
záležitostí. Nicméně ve většině případů je o analogickou záležitost. Průběh generování indexů sloupců do pole cols[] a hodnot do pole vals[] je znázorněn na obrázku Obrázek 17.
31
Start
I. Spočti skutečný počet nenulových prvků v matici.
II. Na základě skutečného počtu nenulových prvků vytvoř pole cols[] a vals[].
III. Urči minimální a maximální index na řádku.
IV. Urči počáteční index.
V. Vygeneruj indexy v závislosti na šířce elementu. K těmto indexům vygeneruj náhodné
Ne
Poslední řádek matice? Ano
Existují v matici zkrácené elementy?
Ano
VI. Doplň indexy a hodnoty do zkrácených elementů.
Ne
Konec Obrázek 17 Vývojový diagram generování indexů sloupců a hodnot 32
Popis vývojového diagramu na obrázku Obrázek 17. I.
Spočte se celkový počet nenulových prvků v řídké matici. To se provede tak, že sečte obsah pole rows[]. Z důvodu, který je uveden v pozn. č. 2, se nemůže počet nenulových prvků, který zadal uživatel, vzít jako skutečný počet nenulových prvků.
II.
Na základě skutečného počtu nenulových prvků se vytvoří pole cols[] a pole vals[]. Obě tyto pole mají velikost, která se rovná skutečnému počtu nenulových prvků generované řídké matice. Ovšem toto neplatí v případě symetrické matice, kdy je generovaná pouze část matice. Velikosti polí těchto matic jsou zhruba poloviční.
III.
Dalším krokem je samotné generování indexů sloupců a hodnot nenulových prvků matice. Celá tato operace je soustředěna do 3 for cyklů, z nichž dva jsou vnořené do sebe tak, že všechny 3 tvoří strom hloubky 3. Hlavní cyklus, který má v sobě vnořený cyklus, zajišťuje procházení matice řádek po řádku. Vnořený cyklus se stará o generování indexů sloupců. Generování těchto indexů sloupců probíhá tak, že se určí minimální možný index na řádku a maximální možný index na řádku. Toto nastavení má především význam v případě, že generujeme symetrickou nebo jednu z trojúhelníkových matic. V tomto případě pak dochází k časté změně minimálního dovoleného indexu.
IV.
Po určení minimálního a maximálního indexu sloupců je vygenerován tzv. počáteční index, kterým je dán počátek vložení elementu matice. Tento počáteční index je vygenerován tak, aby vždy došlo k bezproblémovému vložení všech indexů sloupců a aby výsledné nenulové prvky byly rozmístěny po celé délce řádku matice. To je vše, co první vnořený cyklus vykonává.
V.
Druhý vnořený cyklus, se stará o vložení celého elementu. To provádí tak, že předaný počáteční index si vezme za svůj referenční. K tomuto indexu pak v cyklu přičítá neustále hodnotu 1 tak dlouho, dokud nedosáhne plné délky elementu. S tímto navyšováním indexů se do pole cols[] vkládají zmíněné indexy sloupců a do pole vals[] se generují hodnoty nenulových prvků, které pak budou odpovídat řádku a sloupci, které jsou určené hlavním cyklem a druhým vnořeným cyklem. 33
VI.
K provedení bodu č. VI dochází pouze tehdy, jsou-li v matici elementy kratší než jejich požadovaná velikost. To se týká pouze řádků, které mají délku menší než je šířka elementu. Takové případy se vyskytují v pouze trojúhelníkových maticích, u kterých je požadována „regulárnost“ (pozn. netýká se symetrické „regulární“). Dojde tedy k doplnění indexů a hodnot posledním prvkům. V několika
předešlých
odstavcích
byly
popsány
základní
principy
algoritmu pro generování náhodných řídkých matic. Uvedené principy by měli postačit k pochopení fungování generujícího algoritmu náhodných matic. Operační složit algoritmu odpovídá Θ(n). Paměťová složitost je Ο(n + velikost matice). 4.1.1.1.1
Princip generování náhodné řídké symetrické matice
Generování matice tohoto typu se v mnohém od jiných typů matic mírně liší. Především se liší v tom, jak se v systému interpretuje počet nenulových prvků matice zadaných uživatelem. Interpretuje se jako polovina této hodnoty. Proč? To vyplývá z postupu, jakým je symetrická matice generována. Důležitou vlastností je symetričnost. Co je to symetrická matice je popsáno v podkapitole 1.3.6. Z ní lze vyčíst, že všechny prvky nad hlavní diagonálou mají svůj protějšek 2 pod hlavní diagonálou. Hlavní diagonála je pro obě části společná. Z toho vyplývá, že při generování lze ušetřit téměř polovinu paměťového prostoru, protože bude stačit vygenerovat ½ prvků. Následně se při ukládání matice do souboru zvolí metoda, která z této „půl matice“ vytvoří plnohodnotnou symetrickou řídkou matici. Proto postačí vygenerovat část matice napravo od hlavní diagonály (včetně). Fáze generování počtu nenulových prvků na řádek probíhá téměř stejně, jak bylo uvedeno výše. Co je zde jiné, je bod č. 3. Má-li být matice „regulární“, potom už není požadavkem, aby v každém řádku byl alespoň 1 element nebo prvek. Při hlubším zamýšlení se dá dojít k závěru, že stačí mít alespoň jeden element každých x řádků. Číslo x se rovná délce jednoho elementu + 1. To je 2
Protějšek zde označuje prvek, který má stejnou hodnotu, zaměněný index řádku za index sloupce a index sloupce za index řádku. 34
dáno tím, jak se hodnoty kopírují při symetrii. V tabulce Tabulka 1 je znázorněná matice, která má šířku elementu 3. Už tento element o velikosti 3 zaručí matici o rozměrech 4x4 „regulárnost“. Ta se dosáhne vhodným umístěním elementu dle uvedené tabulky Tabulka 1. Z matice taky vyplývá, že největší pokrytí nenulovými prvky získáme při umístění elementu ihned napravo od hlavní diagonály. 0 1 2 3
1 0 0 0
2 0 0 0
3 0 0 0
Tabulka 1 Symetrická náhodná matice
Operační složit algoritmu je stejná jako v předchozím případě, ale pracuje se s n/2 nenulových prvků. 4.1.1.2 Princip generování řídkých pásových matic Generování řídkých pásových matic je o mnoho jednodušší záležitost, než bylo generování náhodných řídkých matic. Hlavním důvodem zjednodušení je skutečnost, že zde není problematika náhodnosti. Už totiž před samotným generováním je známo, že nenulové prvky se budou vyskytovat v subdiagonálach kolem hlavní diagonály. Takové uspořádání ve výsledku vytvoří pás nenulových prvků souběžný s hlavní diagonálou. V základu je zapotřebí jeden algoritmus pro generování pásových matic, ať už symetrických nebo nesymetrických. Jeho vstupem je šířka pásu nad diagonálou a pod diagonálou. Má-li být matice symetrická, dojde k vygenerování pouze části nad hlavní diagonálou. To se zajistí pouhým nastavením šířky pasu pod diagonálou na hodnotu 0. Symetrická matice se vytvoří při zápisu matice do souboru, kdy se prvkům nad hlavní diagonálou zamění indexy sloupců a řádků. Takto zaměněné indexy se spolu s příslušnou hodnotou nenulového prvku uloží do souboru. Společně s prvky z hlavní diagonály a s prvky nad diagonálou vytvoří symetrickou matici. Vývojový diagram průběhu generování pásové matice je zobrazen na obrázku Obrázek 18. 35
Operační složit algoritmu odpovídá Θ(n). Paměťová složitost je Ο(n).
Start
Ano Je matice symetrická?
Ne
Vygeneruj prvky pod hlavní diagonálou.
Vygeneruj prvky na hlavní diagonále a prvky nad hlavní diagonálou
Konec
Obrázek 18 Vývojový diagram průběhu generování pásové matice
36
4.1.2 Komponenta Matrix Saver Komponenta Matix Saver v sobě sdružuje třídy pro ukládání řídkých matic do souborů. V této fázi vývoje obsahuje pouze třídu MMCoordianteSave, která poskytuje metody pro uložení matice ve formátu MM coordinate (Matrix Market). Jak už bylo několikrát zmíněno, nebude obtížné přidat do této komponenty další třídy, které umožní uložení matic do jiných formátů, jako např. CRS, CDS. Aby třída MMCoordinaSave mohla uložit matici do souboru, je zapotřebí jejímu konstruktoru předat potřebné objekty. Hlavička konstruktoru třídy MMCoordinateSave vypadá následovně: MMCoordinateSave(int[]rows, int[] cols, int[] vals, int matrixSize, File file). Obsahy polí rows[], cols[] a vals[] získáme velice jednoduše prostřednictvím getrů obsažených ve třídě (třídách) z komponenty Matrix Generator. Jména příslušných getrů korespondují s názvy polí, což přidává na přehlednosti kódu. Dalším parametr je matrixSize, který musí být shodný s velikosti matice, která je předávána v prvních třech parametrech konstruktoru. V podstatě by tento parametr zde nemusel být, protože velikost matice se dá určit z velikosti pole rows[]. Posledním vstupním parametrem je file. Ten určuje, kde se uloží předaná matice. O vytvoření objektu File se postará komponenta MainController. Třída MMCoordinateSave obsahuje metody, které jsou úzce propojené s metodami, které generují matice. Není proto možné použít jakoukoliv metodu na předanou matici. Takové použití vede k nesprávnému chování celého programu. Správnému použití metod pomáhá jejích rozdělení do dvou skupin a to do skupiny saveSimple, která má na starost ukládání náhodných matic a do skupiny saveBand, která je určena pro ukládání pásových matic. Proto v následující části bude stručně uvedena funkčnost jednotlivých metod a s jakým typem matice mohou být použité. Sled metod, generujících matice a metod pro uložení matic, má na starost Main Controller.
37
Obecné schéma popisu tříd: Kategorie saveSimple (pro náhodnou matici) nebo saveBand (pro pásovou matici). Název metody z dané třídy s krátkým popisem funkčnosti.
Jméno_třídy.jméno_metody,
která
pochází
z komponenty
Matrix
Generátor. Metoda, která může použít s výše uvedenou metodou.
saveSimple saveSimpleNormal() – umožňuje uložit normální matici.
Simple.generateNormal().
saveSimpleSymetric() – umožňuje uložit symetrickou matici. Vzhledem k tomu, že tato metoda přijímá pouze vygenerovanou horní část matice včetně hlavní diagonály, je zapotřebí, aby při zápisu do souboru byly zapisovány i prvky z části pod hlavní diagonálou.
Simple.generateSymetricTriang().
saveSimpleUpper() – slouží pro uložení horní trojúhelníkové matice.
Simple.generateUpperTriangle().
saveSimpleUpper() – slouží pro uložení dolní trojúhelníkové matice. Protože vstupní matice je horní trojúhelníková, musí se před uložením matice přepočítat indexy sloupů.
Simple. generateUpperTriangle().
saveBand saveBandNormal() – jeho funkce umožňuje uložit pásovou matici. Matice je předávaná kompletní, není zapotřebí nic přepočítávat.
Band. saveBandNormal().
saveBandSymetric() – metoda pracuje pouze s vygenerovanou horní částí matice včetně hlavní diagonály. Proto se zároveň s ukládáním do souboru provádí přeindexování části matice nad hlavní diagonálou a kopíruji se hodnoty nenulových prvků.
Band. saveBandSymetric(). 38
Použití metod ve správném spojení je zaručeno správné vygenerování do výstupního souboru. Jak vypadá reprezentace matice v souboru ve formátu MM coordinate, je ukázáno v následující podkapitole 4.1.2.1.
4.1.2.1 Formát MM coordinate pro uložení matice Formát MM coordinate (Matrix Market) je formát, který reprezentuje matici způsobem, že každý její nenulový prvek je určen absolutní polohou v matici. Absolutní poloha je určena indexem řádku a sloupce. Jelikož nejnižší index může být hodnota 0 nebo 1, je tato skutečnost uvedena v hlavičce. Celá struktura souboru vypadá následovně: 1. Hlavička – obsahuje název programu, kterým byl tento soubor vygenerován. Dále obsahuje informace o autorovi, o verzi programu a další informace.
V našem
případě důvod vytvoření
projektu a
poděkování. Hlavička dále obsahuje: a. Popis jednotlivých symbolů – ASCII tabulka, která popisuje významy použitých symbolů, např. symbol pro nadpis, symbol pro komentář atd. b. Informaci o matici - první nezakomentovaný řádek uvádí počet řádků, sloupců a množství nenulových prvků. Jednotlivé údaje na řádku jsou od sebe oddělené mezerou. c.
Popis dat reprezentující řídkou matici – obsahuje popis dalších nezakomentovaných řádků. Stanovuje, co která hodnota na řádku reprezentuje (řádek, sloupec, hodnota). Dále informuje, o nejnižším možném indexu sloupce a řádku.
2. Vlastní data – První nezakomentovaný řádek obsahuje informaci uvedenou v odstavci b. Další řádky obsahují zápis prvků matice. Všechny výše uvedené informace postačují k tomu, aby matice mohla být zpětně zrekonstruovaná. Nepovinně je hlavička matice ještě doplněná o řádek, který informuje o možných hodnotách prvků. Ukázka hlavičky je v tabulce
39
##Generátor řídkých matic # Autor: Tomáš Bílek # Verze 1.0 # Tento projekt byl vytvořen na základě zadání bakalářské práce. # Zvláštní poděkování patří panu Ing. Ivanu Šimečkovi, Ph.D. za pomoc při vytváření tohoto # projektu. #========================================================================================= # # Tento soubor reprezentuje řídkou matici o rozměrech MxN s # L nenulovými prvky v následujícím Matrix Market formátu: # # +---------------------------------------------+ # |##Generátor řídkých matic | <--- nadpis # |# | <--+ # |# komentář | |-- 0 nebo více # |# | <--+ # | M N L | <--- řádky, sloupce, hodnoty # | R1 C1 A(R1, C1) | <--+ # | R2 C2 A(R2, C2) | | # | R2 C2 A(R1, C2) | |-- L řádky # | . . . | | # | RL CL A(RL, CL) | <--+ # +---------------------------------------------+ # # Indexy sloupců a řádků začínají na indexu 1, např. A(1, 1) je první element. # #========================================================================================= # Nenulové prvky můžou nabývat hodnot z množiny celých čísel v rozsahu <-20, 20>, mimo 0."
Tabulka 2 Ukázka hlavičky výstupního souboru ve formátu MM coordinate
Struktura hlavičky byla převzatá z [8]. 4.1.3 Komponenta Main Controller Main controller obsahuje pouze jednu třídu, která obstarává komunikaci mezi všemi komponentami. Obsahuje statické metody typu setr, prostřednictvím kterých přijímá parametry z grafického rozhraní. Dále zachytává všechny výjimky a jejich obsah posílá komponentě GUI, která se stará o jejich zobrazení. Základem jsou 2 statické metody, které spouštějí generování matic voláním příslušné posloupnosti metod z komponent Matrix Generator a Matrix Saver. Větvení uvnitř metod je realizováno pomocí větvícího bloku switch. 4.1.4 Komponenta GUI Je komponenta určená pro zobrazení grafického uživatelského rozhranní. Kromě zobrazení hlavního okna také obstarává zobrazování výjimek, které se vyskytnou během kontroly vstupních dat nebo v době běhu výkonné části programu. Hlavním úkolem komponenty GUI je volat příslušné metody Main Controlleru na základě uživatelových pokynů, tj. při zadávání velikosti matice, 40
při stisku klávesy, atd. Tato interakce vyvolá předání vstupních parametrů zadaných uživatelem do řídicí části programu, tedy do Main Controlleru. Všechny vstupy jsou ošetřeny pomocí Plain Documentů, které jsou přiřazené jednotlivým vstupním polím (tzv. JEditTextům). V Plain Documentech Metoděje přetížená metoda insertString ve které je definované, jaké řetězce (znaky) může JTextEdit přijímat. V tomto případě se jedná o kontrolu, zda znaky vkládané uživatelem odpovídají přirozeným číslům včetně nuly. Pokud vkládaný znak nebo řetězec neodpovídají číslu, nejsou vloženy do JTextEditu. Výhoda řešení spočívá v nezatěžování Main Controlleru, který by v jiném případě musel kontrolovat správnost zadaného řetězce. Takto definovaný dokument nám zaručí, že předaný řetězec Main Controlleru bude reprezentovat přirozené číslo včetně nuly. Grafické rozhraní je postaveno na Frameworku Java Swing. Pro vytváření samotné není použit žádný grafický designer, ale je vytvořen manuálně. Designer není použit z důvodu generování velkého množství neefektivního kódu. Podle analýzy byl kladen velký důraz na přehlednost a jednoduchost celého grafického rozhraní. Důraz byl kladen na to, aby se stejné komponenty nebo podobného významu nacházely na stejných pozicích v obou „záložkách“. Protože k jednoduchosti patří i příjemné ovládání, je možnost celý program plně ovládat pomocí klávesových zkratek. To umožňuje použití programu i v případě, není-li u počítače dostupná myš. K jednotlivým položkám se přistupuje mocí klávesy ALT + podtržené písmeno v názvu vlastnosti. Dalším možným způsobem je se k dané položce dostat pomocí klávesy TAB. Co se týče velikosti jednotlivých oken, mají všechny stanovou fixní velikost až na okno s nápovědou. Hierarchie hlavního menu: •
Soubor o Konec – ukončí aplikaci
•
Nápověda o Nápověda – zobrazí nápovědu programu o O Programu – zobrazí okno s informacemi o programu
41
Výsledek realizace grafického uživatelského rozhraní je následující:
Obrázek 19 Grafické uživatelské rozhraní, karta pro náhodné matice
Obrázek 20 Grafické uživatelské rozhraní, karta pro pásové matice
42
Obrázek 21 Ukázka okna Nápověda
Obrázek 22 Ukázka okna O Programu
43
44
5 Ukázka výstupu generátoru řídkých matic
Zde je uvedená ukázka výstupu generátoru řídkých matic ve formátu MM coordinate uvedeného v podkapitole 4.1.2.1.
##Generátor řídkých matic # Autor: Tomáš Bílek # Verze 1.0 # Tento projekt byl vytvořen na základě zadání bakalářské práce. # Zvláštní poděkování patří panu Ing. Ivanu Šimečkovi, Ph.D. za pomoc při vytváření tohoto # projektu. #========================================================================================= # # Tento soubor reprezentuje řídkou matici o rozměrech MxN s # L nenulovými prvky v následujícím Matrix Market formátu: # # +---------------------------------------------+ # |##Generátor řídkých matic | <--- nadpis # |# | <--+ # |# komentář | |-- 0 nebo více # |# | <--+ # | M N L | <--- řádky, sloupce, hodnoty # | R1 C1 A(R1, C1) | <--+ # | R2 C2 A(R2, C2) | | # | R2 C2 A(R1, C2) | |-- L řádky # | . . . | | # | RL CL A(RL, CL) | <--+ # +---------------------------------------------+ # # Indexy sloupců a řádků začínají na indexu 1, např. A(1, 1) je první element. # #========================================================================================= # Nenulové prvky můžou nabývat hodnot z množiny celých čísel v rozsahu <-20, 20> mimo 0.
30 30 40 1 1 11 1 2 18 1 8 5 1 9 2 1 12 -12 1 13 14 2 2 -18 2 3 -2 3 15 -5 3 16 -7 4 6 -3 4 7 15 5 7 19 5 8 -18 7 16 5 7 17 -7 9 14 6 9 15 15 10 18 2 10 19 16
11 11 12 12 15 15 16 16 18 18 21 21 22 22 23 23 27 27 29 29
17 18 12 13 25 26 24 25 23 24 22 23 22 23 26 27 29 30 29 30
12 -15 -3 -10 15 -1 -19 -5 8 -10 1 5 19 -13 -1 -9 -16 8 8 14
Z uvedeného výstupu lze vyčíst, že matice je rozměrů 30 x 30 se 40 nenulovými prvky. Po důkladnějším prostudování se dá zjistit, že matice je typu horní trojúhelníková a šířka elementu je 2.
45
46
6 Závěr
Cílem mé práce bylo vytvořit generátor řídkých matic s jednoduchým grafickým rozhraním. Samotný vývoj byl z počátku velice obtížný. V první fázi jsem se snažil navrhnout algoritmy pro generování řídkých matic se složitostí Θ(počet nenulových prvků). Kdyby tato podmínka byla jako jediná, obtížnost by se snížila. Jenže jsem nedal na doporučení uchovávat řídkou matici v paměti pomocí spojového seznamu. Tato možnost mi připadala jako plýtváním místem v paměti a proto jsem algoritmus vyvíjel s tím, že matice bude uložena ve statických polích. I když se tím celá práce ztížila a došlo k drobným omezením, tak si myslím, že mi to nakonec povedlo. Rychlost generování matic, s množstvím prvků řádově 10 8 a víc, je velice rychlá. Opačná situace je při otevírání souborů s takovým množstvím prvků. Další části programu už byly řádově snadnější a to proto, že jsem zde uplatnil své znalosti nabyté během studia. Ukázalo se, že model programování MVC je velice silná stránka objektově orientovaného programování. To mi umožnilo zbytek aplikace naprogramovat tak, aby v budoucnosti mohla být snadno doplněná o další funkce. Vývojem programu jsem nabyl mnoho znalostí z oblasti řídkých matic, hlavně co se týče jejich reprezentace v paměti. Ověřil jsem si, že tvorba efektivních algoritmů není triviální záležitost. I přes potíže během vývoje jsem se svou práci plně spokojen.
47
48
7 Seznam použité literatury
[1] Matice. http://cs.wikipedia.org/wiki/Matice. [2] Sparse matrix. http://en.wikipedia.org/wiki/Sparse_matrix. [3] Sparse file. http://en.wikipedia.org/wiki/Sparse_file. [4] Sparse formats. http://www.metal.agh.edu.pl/~banas/OWW/sparse_formats.pdf. [5] Shahnaz, Rukhsana a Usman, Anila. Review of Storage Techniques for Sparse Matrices. Nilore, Islamabad, Pakistan , 2005. [6] Harder, Douglas Wilhelm. The Yale Sparse-Matrix Data Structure, 2006. www.ece.uwaterloo.ca/~ece250/Lectures/Slides/11.02.Sparse.ppt. [7] Sparse Matrix Storage Formats. http://www.cs.utk.edu/~dongarra/etemplates/node371.html. [8] Matrix Market Exchange Formats. http://math.nist.gov/MatrixMarket/formats.html.
49
50
Příloha A: Obsah přiloženého CD
soubor readme.txt – obsahuje informace o obsahu složek na CD složka doc – obsahuje tento dokument ve formátu .docx a .pdf složka application – obsahuje zdrojové kódy a zkompilovaný program
51
52
Příloha B: Uživatelský manuál
Aby se mohlo s programem začít pracovat, je nutné nejprve provést jeho nainstalování. Pro práci s ním s důležité znát, jak správně provést i jeho nastavení. Tyto úkony budou popsané v následujících ostavcích.
Instalace a spuštění Instalace programu je velice jednoduchá. V principu se jedná o pouhé rozbalení archívu s programem na nějaké místo v počítači. Pro běh aplikace je zapotřebí mít nainstalovaný Java Runtime Environment (JRE) verze 6.0, update alespoň 13. V nižších verzích se vyskytuje problém s file dialogem, kdy jeho otevírání trvá delší dobu. Nejnovější verzi je možné stáhnout na adrese http://www.java.com/en/download/index.jsp. Po nainstalování JRE se může generátor řídkých matic spustit dvojitým kliknutím na soubor s názvem Generator_ridkych_matic.jar. Jiný způsob spuštění je prostřednictvím příkazového řádku ve Windows nebo systémové konzole v UNIX systémech. To se provede příkazem java -jar cesta_k_souboru.
Nastavení Po úspěšném spuštění aplikace následuje zadání vstupních parametrů prostřednictvím grafického uživatelského prostředí. Nastavení u náhodných matic se provádí následovně: 1. Do pole velikost matice se zadá kladné celé číslo vyjadřující velikost čtvercové matice. 2. Zadá se přibližný počet prvků. Zde je nutné mít toto číslo promýšlené s následujícím nastavením a šířkou elementu. 53
3. Zvolí se nastavení z levé části nabídky („regulární“, Normální, Symetrická…) 4. Zadá se šířka 1 elementu. 5. Zvolí se výstupní soubor, do kterého se uloží vygenerovaná matice. 6. Kliknutím na tlačítko „Vygeneruj matici a ulož“ se spustí generování matice. Jestliže je vše v pořádku, bude uživatel příslušným dialogem oznámen u úspěchu. Pokud ne, bude uživateli zobrazen dialog s oznámením, kde se chyba nachází. Nastavení u pásových matic se provádí následovně: 1. Do pole velikost matice se zadá kladné celé číslo vyjadřující velikost čtvercové matice. 2. Zadá se velikost šířky pásu nad a pod hlavní diagonálou. Zde je nutné brát na vědomí, že tyto hodnoty nemůžou být větší než je velikost matice – 1. 3. V případě
požadavku
na
symetričnost
se
zaškrtne
položka
„Symetrická“. 4. Zvolí se výstupní soubor, do kterého se uloží vygenerovaná matice. 5. Kliknutím na tlačítko „Vygeneruj matici a ulož“ se spustí generování matice. Jestliže je vše v pořádku, bude uživatel příslušným dialogem oznámen u úspěchu. Pokud ne, bude uživateli zobrazen dialog s oznámením, kde se chyba nachází.
54
