Post on 10-Jan-2016
description
transcript
10. června 2010
Paralelní výpočet SVD s aplikacemi pro vyhledávání informací
Petr Kotas, Vít Vondrák,Pavel Praks
Fakulta elektrotechniky a Informatiky VŠB - TUO
10. června 2010
Motivace
• Proč se problémem SVD a vlastních čísel zabývat
– Řešení homogeních lineárních rovnic
– Využití při analýze DNA
– Registrace obrazu
– Komprimace dat
– Statistika
– Vyhledávače
10. června 2010
Obsah
• Úvod do SVD– Výpočet a problémy při něm vznikající– Návrh řešení → paralelizace
• Výpočet SVD– Bidiagonalizace– Výpočet singulárních čísel– Výpočet singulárních vektorů– Sestavení rozkladu
• Aplikace na multimediální data
10. června 2010
Úvod do SVD
• Výpočet je velmi náročný na HW– Pro plné matice je SVD vysoce paměťově náročné– Značná náročnost na floating point operace (kvůli přesnosti)
• Iterační charakter → větší náročnost než jiné rozklady• Praktická implementace → rozdělení problému
– Bidiagonalizace– Výpočet singulárních čísel z bidiagonální matice– Výpočet singulárních vektorů
10. června 2010
Výpočet SVD - Bidiagonalizace
• Praktická implementace– Využití Householderových zrcadlení
• Urychlení výpočtu• Numerická stabilita
– Householderova matice
Ortogonální tranformace, redukující dimenzi problému. Ortogonální tranformace, redukující dimenzi problému.
10. června 2010
Výpočet SVD - Bidiagonalizace
10. června 2010
Výpočet SVD - Bidiagonalizace
10. června 2010
Výpočet SVD - Bidiagonalizace
10. června 2010
Výpočet SVD - Bidiagonalizace
10. června 2010
Výpočet SVD - Bidiagonalizace
10. června 2010
Výpočet SVD - Bidiagonalizace
10. června 2010
Výpočet SVD - Bidiagonalizace
10. června 2010
Výpočet SVD - Bidiagonalizace
10. června 2010
Výpočet SVD – Bidiagonalizace : Distribuce
10. června 2010
Výpočet SVD – Paralelní bidiagonalizace• Distribuovaný výpočet
– V každém kroku se spočítá Householderův vektor
– Houselderoův vektor se rozdistribuuje na každý uzel
– Každý uzel dále elimuje prvky jemu přiřazené
10. června 2010
Výpočet SVD – Bidiagonalizace : Škálovatelnost
• Největší problém— Dimenze 12800 x 12800 (1.2GB)— Doba běhu 1(h)
10. června 2010
Výpočet SVD – Výpočet singulárních čísel
• Diagonalizace matice– Pomocí Givensonových
rotací– Iterační proces– Řád konvergence je O(N2)
10. června 2010
Výpočet SVD – Výpočet singulárních čísel
• Vynulování prvního prvku bidiagonály
10. června 2010
Výpočet SVD – Výpočet singulárních čísel
• Vynulování prvního prvku bidiagonály
• Vynulování nově vzniklého prvku
10. června 2010
Výpočet SVD – Výpočet singulárních čísel
• Vynulování prvního prvku bidiagonály
• Vynulování nově vzniklého prvku
• Opravení prvního řádku
10. června 2010
Výpočet SVD – Výpočet singulárních čísel
• Vynulování prvního prvku bidiagonály
• Vynulování nově vzniklého prvku
• Opravení prvního řádku• Na třetím řádku se
objeví prvek navíc
10. června 2010
Výpočet SVD – Výpočet singulárních čísel
• Vynulování prvního prvku bidiagonály
• Vynulování nově vzniklého prvku
• Opravení prvního řádku• Na třetím řádku se
objeví prvek navíc• Opravení druhého řádku
10. června 2010
Výpočet SVD – Výpočet singulárních čísel
• Vynulování prvního prvku bidiagonály
• Vynulování nově vzniklého prvku
• Opravení prvního řádku• Na třetím řádku se objeví
prvek navíc• Opravení druhého řádku• Vynulování posledního
prvku navíc
10. června 2010
Výpočet SVD – Výpočet singulárních čísel
• Diagonalizace– Ukončovací podmínka
• Největší problém– Dimence 12800 x 12800– Doba běhu 791.79 (s)– Počet iterací 325161
Důkaz lze najít v G.W.Stewart – Matrix algorithms vol 2
10. června 2010
Výpočet SVD – Singulární vektory
• Sestavení matic U a V (ortogonálních tranformací)– Matice a jsou sestaveny postupnou akumulací z
Householderových vektorů• Potřebuje
– Sestavení matic a je proces řešení třídiagonálních soustav
– Výsledné matice U a V vzniknou pronásobením přechozích
U~V~
10. června 2010
Porovnání s Matlabem – sekvenční kód
10. června 2010
Závěr
• Existující implementace– ScaLapack, Lapack, MatLab, ProPack ...
• Proč se zabývat novou implementací– Výpočet úplného singulárního rozkladu pro plné velké matice– Licence paralelního MatLabu je drahá– Většina stávajících implentací je pro řídké matice– Stávající řešení se povětšinou zaměřují na největší vlastní čísla
• Budoucnost– Akcelerace výpočtu pomocí „kompaktní reprezentace“
Householderovy tranformace– Další zvětšení dimenze řešitelných problémů– Možnost volby části spektra pro výpočet
10. června 2010
Aplikace na multimediální data
• Hledání podobnosti dvou digitálních obrazů– Problém velikost
• Aproximace matic pomocí SVD (LSI) • Umožní redukci dimenze původní datové matice řádově na desetinu
– Matematický popis (pro úplnost , zde se jím nezabýváme)• MPEG-7• Rozdělění histogramu• Frekvenční odezva na waveletové filtry
10. června 2010
Aplikace na multimediální data : Ukázka
10. června 2010
Aplikace na multimediální data : Ukázka
10. června 2010
Děkuji za pozornost.
Dotazy?