Sparse Linear Algebra

In Numerical Analysis, the solution to ordinary and/or partial differential equation often leads to systems of linear equations of type Ax=b. Such an equation is usually obtained during the discretization process. The solution of such system is crucial in various scientific problems that rely on discretization schemes such as Finite Element Method, Finite Volume Method or Finite Difference Method. They are widely used in domains such as Computional Fluid Dynamics, computational physics or chemistry. Typical matrices have thousands or even millions of rows and columns and are very sparse, with an average number of non-zero elements per row rarely exceeding 100. In some cases the pattern of nonzero elements is quite regular (e.g. for problems resulting from discretization of partial differential equations on regular grids), but the most interesting—and difficult—matrices are those whose distribution of nonzero elements appears to be random.

Since direct methods for solving such systems of equations require a reasonable amount of memory, one employs often iterative solvers that require less memory and still provide a reliable results. The performance of iterative solvers such as Conjugate Gradient or BiConjugate Gradient strongly depend on the performance of Sparse Matrix-Vector Multiplication (SpMV) operation that is invoked in each solver iteration many times.

Therefore, engineers at Vratis took a lot of effort to optimize this operation for a given GPU architecture. As a result, we ended up with one of the fastest SpMV algorithms worldwide. Efficient SpMV allowed us for building iterative solvers with the similar peak performance.

See SpeedIT for more details.