Geodesic
A streaming approach for sparse matrix products and its application in Galerkin multigrid methods
Electronic transactions on numerical analysis, Tome 37 (2010), pp. 263-275
In this paper, we present a numerical algorithm for computing products of the form R KRT, where R, RT, and K are sparse matrices. By reformulating the problem into the simultaneous processing of a sequential data and control stream, cache miss penalties are significantly reduced. Even though the algorithm increases memory requirements, it accelerates sparse matrix products on recent processor architectures by a factor of up to 4 compared to previous approaches. We apply the algorithm to compute consistent system matrices at different resolution levels in a dynamic multigrid elasticity simulation, and we show its efficiency for nested and non-nested mesh hierarchies.
Classification : 65F50, 65M55, 65M60, 65Y20, 68W01, 74B99, 74H15
Keywords: sparse matrix products, cache-awareness, multigrid, Galerkin update 
@article{ETNA_2010__37__a9,
     author = {Georgii,  Joachim and Westermann,  R\"udiger},
     title = {A streaming approach for sparse matrix products and its application in {Galerkin} multigrid methods},
     journal = {Electronic transactions on numerical analysis},
     pages = {263--275},
     year = {2010},
     volume = {37},
     zbl = {1205.65164},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2010__37__a9/}
}
TY  - JOUR
AU  - Georgii,  Joachim
AU  - Westermann,  Rüdiger
TI  - A streaming approach for sparse matrix products and its application in Galerkin multigrid methods
JO  - Electronic transactions on numerical analysis
PY  - 2010
SP  - 263
EP  - 275
VL  - 37
UR  - http://geodesic.mathdoc.fr/item/ETNA_2010__37__a9/
LA  - en
ID  - ETNA_2010__37__a9
ER  - 
%0 Journal Article
%A Georgii,  Joachim
%A Westermann,  Rüdiger
%T A streaming approach for sparse matrix products and its application in Galerkin multigrid methods
%J Electronic transactions on numerical analysis
%D 2010
%P 263-275
%V 37
%U http://geodesic.mathdoc.fr/item/ETNA_2010__37__a9/
%G en
%F ETNA_2010__37__a9
Georgii,  Joachim; Westermann,  Rüdiger. A streaming approach for sparse matrix products and its application in Galerkin multigrid methods. Electronic transactions on numerical analysis, Tome 37 (2010), pp. 263-275. http://geodesic.mathdoc.fr/item/ETNA_2010__37__a9/