How Many Zeros in the Sparse Matrix

Author: Koba Gelashvili
Keywords: Sparse matrix, conjugate gradient method
Annotation:

Report is devoted to determination of the percentage of zeros in matrix, which is used with conjugate gradient (briefly CG) algorithm, which identifies matrix as sparse. To determine the percentage of nz-elements after which the CG-method is fairly faster using jnz-format data structure, in comparison with common rectangular representation of matrix, the following experiment has been conducted (see https://github.com/vakho10/Sparse-Storage-Formats ). 15 matrices with different sizes (number of rows n changes from 100 to 1500 inclusively, with step of 100) have been used. For each n, 5 versions of symmetric matrices with randomly generated numbers have been constructed, with the different percentage of zeroes: 15, 20, 25, 30 and 35. In total 75 different matrices. Vectors of corresponding dimensions with random numbers have been generated for each matrix. For each pair (matrix+vector), CG-method was used. In case of 35% of zeros, for the absolute majority of tests, using the jnz-submatrix has sped up the solution process of the system. By increasing the number of zeros this difference becomes more significant. Taking into account that jnz-format saves memory in case of 67% zero-entries, it seems to us that the notion of sparsity in the sense of run-time (unlike memory) is considerably weaker.

Lecture files:

How Many Zeros in the Sparse Matrix? [en]
რამდენი ნულია მეჩხერ მატრიცაში? [ka]