Generating Optimized Sparse Matrix Vector Product over Finite Fields

Abstract. Sparse Matrix Vector multiplication (SpMV) is one of the most important operation for exact sparse linear algebra. A lot of re-search has been done by the numerical community to provide efficient sparse matrix formats. However, when computing over finite fields, one need to deal with multi-precision values and more complex operations. In order to provide highly efficient SpMV kernel over finite field, we pro-pose a code generation tool that uses heuristics to automatically choose the underlying matrix representation and the corresponding arithmetic