Efficient Converting of Large Sparse Matrices to Quadtree Format

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F15%3A00225944" target="_blank" >RIV/68407700:21240/15:00225944 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1109/SYNASC.2014.25" target="_blank" >http://dx.doi.org/10.1109/SYNASC.2014.25</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/SYNASC.2014.25" target="_blank" >10.1109/SYNASC.2014.25</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Efficient Converting of Large Sparse Matrices to Quadtree Format

Popis výsledku v původním jazyce

Computations with sparse matrices are widespread in scientific projects. Used data format affects strongly the performance and also the space-efficiency. Commonly used storage formats (such as COO or CSR) are not suitable neither for some numerical algebra operations (e.g., The sparse matrix-vector multiplication) due to the required indirect addressing nor for I/O file operations with sparse matrices due to their high space complexities. In our previous papers, we prove that the idea of using the quadtree for these purposes is viable. In this paper, we present a completely new algorithm based on bottom-up approach for the converting matrices from common storage formats to the quad tree format. We derive the asymptotic complexity of our new algorithm,design the parallel variant of the classical and the new algorithm, and discuss their performance.

Název v anglickém jazyce

Efficient Converting of Large Sparse Matrices to Quadtree Format

Popis výsledku anglicky

Computations with sparse matrices are widespread in scientific projects. Used data format affects strongly the performance and also the space-efficiency. Commonly used storage formats (such as COO or CSR) are not suitable neither for some numerical algebra operations (e.g., The sparse matrix-vector multiplication) due to the required indirect addressing nor for I/O file operations with sparse matrices due to their high space complexities. In our previous papers, we prove that the idea of using the quadtree for these purposes is viable. In this paper, we present a completely new algorithm based on bottom-up approach for the converting matrices from common storage formats to the quad tree format. We derive the asymptotic complexity of our new algorithm,design the parallel variant of the classical and the new algorithm, and discuss their performance.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F12%2F2011" target="_blank" >GAP202/12/2011: Paralelní vstupně/výstupní algoritmy pro rozsáhlé řídké matice</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

ISBN

978-1-4799-8448-0

ISSN

—

e-ISSN

—

Počet stran výsledku

8

Strana od-do

122-129

Název nakladatele

IEEE Computer Society

Místo vydání

Los Alamitos

Místo konání akce

Timisoara

Datum konání akce

22. 9. 2014

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000366596600018