### Project description

The sparse matrix storage scheme (format) has great

impact on performance and scalability of the sparse matrix-vector

multiplication operation and other iterative algorithms for sparse

matrix computations. Ideal format ensures minimal memory storage

requirements, maximum utilization of floating point vector units,

maximum utilization of cache memories, and enables load balanced

parallelization of the algorithms on massively parallel systems.

#### State of the art

Several sparse matrix formats have been proposed and some are due to their

simplicity widely used, such as Compressed Sparse Row/Column (CSR/CSC) or

Jagged Diagonal Storage (JDS) formats. The feasibility of particular

format is given mainly by the sparsity pattern of a matrix. Sparse

matrices often contain dense submatrices (blocks). Therefore, some formats

use blocking techniques which exploit knowledge about clustering of matrix

non-zero entries. These blocking formats like SPARSITY, CARB, or M-CARB or

based on based on quadtree storage scheme, may give significantly better

performance of the algorithms on sparse matrices than allows the CSR

format, due to eliminating memory read stalls, consuming less memory,

allowing a better use of registers, and improving vector unit utilization.

But these specialized and efficient formats have also some drawbacks. They

suffer from a large transformation overhead, are designed only for a

limited set of matrix operations, or do not support fast adding or

removing nonzero elements.

#### Future research

This project goal is to conduct research of new sparse-matrix formats

for massively parallel architectures with the goal to address these

trade-offs and develop optimization heuristics for using these formats for

sparse matrix operations. The project will build on the results

of the dissertation thesis of Ivan.Šimeček.

These sparse-matrix formats should be used for efficient implementation of

numerical linear algebra operations like LU factorization or eigensolvers.

#### Soucre codes

pripadne odkaz na zdrojaky

### People