Rethinking Sparse Formats for RISC-V: A Hierarchical Approach to High-Performance SpMV Anna Pirova, Anastasia Vodeneeva, Konstantin Kovalev, Alexander Ustinov, Maksim Zagriadskov, Daniil Litvyakov, Arthur Kulik, Evgeny Kozinov, Valentin Volokitin, Iosif Meyerov* Department of HPC and System Programming, Lobachevsky State University of Nizhny Novgorod, 23, Prospekt Gagarina, Nizhny Novgorod, 603022, Russia
arXiv:2609.11352v1 [cs.DC] 10 Sep 2026
Abstract The sparse matrix-vector multiplication (SpMV) algorithm is a fundamental computational kernel of linear algebra and serves as a building block for numerous applications, primarily iterative solvers for systems of linear equations used in scientific and engineering simulations. This paper compares vectorized implementations of the SpMV algorithm across eight established sparse matrix storage formats and proposes a novel modification of the CSR format, Hierarchical CSR (HCSR), which enhances SpMV performance on RISC-V processors. Our SpMV implementations utilize RVV 1.0 intrinsics and are publicly available as an open-source C++ library named RVVLASparse. Computational experiments conducted on SpacemiT K1 and K3 RISC-V boards demonstrate that selecting an appropriate matrix storage format accelerates SpMV computations by an average of 1.6x, while the proposed HCSR format achieves the shortest execution time among all considered formats across a broad class of sparse matrices.
Keywords: linear algebra, RISC-V, HPC, sparse matrix, vectorization, matrix-vector multiplication, mathematical libraries, benchmarking, performance
1. Introduction
The emergence of the RISC-V open and patent-free instruction set architecture (ISA) has opened new research directions and opportunities for computer architects and high-performance software developers. Within just 15 years, the RISC-V ISA has evolved significantly from a research prototype to commercially available microprocessors and microcontrollers. Although the vast majority of currently produced devices belong to the IoT segment, early prototypes of server processors featuring dozens of modern out-of-order computational cores with RVV 1.0 vector extensions have emerged, making them suitable for many problems in the HPC domain [4], [5]. The development of the RISC-V ecosystem requires optimization of the entire software stack, ranging from system-level and low-level software to end-user application packages. A potential solution is to rely entirely on an optimizing compiler, delegating code optimization responsibilities to it. This approach offers obvious advantages, including rapid adaptation speed, minimal effort expenditure, and the ability to simply recompile the code upon the release of newer, more advanced hardware. Nevertheless, a number of architecture-specific optimizations can still only be implemented manually, which entails substantial effort when adapting numerous applications. The problem of mathematical software optimization for RISC-V is actively being investigated by the scientific and engineering communities. For instance, recent studies [21], [22] * Corresponding author.
Email address: [email protected] (Iosif Meyerov)
examine an approach to optimizing codes in computational fluid dynamics and bioinformatics. In [16], the authors propose a method for RISC-V specific vectorization within the CatBoost machine learning package. In [8], performance issues are studied for astrophysics codes implemented using HPX and Kokkos, while [26] proposes an optimization for the Fast Fourier Transform. Overall, the problem of tailoring mathematical software to the specifics of the new RISC-V ISA is of significant practical interest. In this work, we investigate the dependence of sparse matrixvector multiplication (SpMV) performance on the sparse matrix storage format for RISC-V processors. The SpMV algorithm is one of the key computational kernels in linear algebra. Specifically, it serves as the primary computationally intensive kernel for iterative solvers of sparse systems of linear equations (SLAE), which are applied to solve a wide range of engineering problems using supercomputers. Despite the apparent simplicity of this algorithm, efficient representation of sparse matrices that allows unlocking the potential of modern computing systems remains an unsolved challenge. Researchers proposed various approaches to increasing SpMV performance for x86 CPUs and GPUs through the use of specialized sparse matrix storage formats, leveraging SIMD instructions, and applying non-trivial parallelization schemes. The most common sparse linear algebra libraries for CPUs (e.g., Intel oneAPI MKL, AOCL-Sparse, SparseBLAS) utilize classic matrix storage formats that often fail to fully exploit the SIMD mechanisms supported by modern processors and are not adapted for RISC-V architectures. Meanwhile, most implementations of non-standard storage formats
are distributed as standalone libraries and are not integrated into SLAE solvers. Thus, although the problem is well-studied for traditional architectures, there remains room for further SpMV algorithm optimizations. These can be performed at different levels, ranging from leveraging the architectural peculiarities of the new RISC-V platform to attempting to overcome the fundamental memory wall issue, which prevents achieving acceptable performance in the SpMV operation (current results show a twoorder-of-magnitude gap on the HPCG benchmark compared to Linpack test results). In this paper, we present RVVLASparse 1 , a software library designed for RISC-V processors that enables the SpMV operation across nine different sparse matrix storage formats. Supported formats include CSR, Sell-C-σ, CSR2, CSR5, LAV, VHCC, VNEC, CVR, as well as a novel format, Hierarchical CSR (HCSR). The core idea behind the new format lies in improving memory subsystem efficiency by partitioning matrices into blocks of CSR and COO formats. The scientific contributions of this work are as follows:
algebra algorithms in the Eigen library were optimized for the RISC-V architecture. In [23], [27], [31], new vector instructions improved the performance of linear algebra operations. SpMV is a widely studied memory-bound problem. Numerous papers propose improving SpMV performance on CPUs and GPUs by using non-standard sparse matrix storage formats. The classical sparse matrix storage formats such as Compressed Sparse Row (CSR), compressed column storage (CCS), and coordinate format (COO) were developed in the 1960s–1970s and remain the standard, most widely used data structures for general sparse matrices. Since 2000, many modifications of the classical storage formats have been developed, primarily targeting x86 processors with support for vector SIMD instructions and GPUs. A detailed survey of sparse matrix storage formats can be found, for example, in [10]. Below, we discuss some of them. Many data structures are built as modifications of the CSR format by grouping nonzero elements into dense blocks or lanes of equal size, which allows better utilization of vector operations and improves cache locality compared to standard CSR. These formats include CSR5 [19], CSR2 [3], CVR [32], and others. Such formats demonstrate performance gains over CSR on general sparse matrices. Other modifications of CSR aim to improve SpMV performance on matrices with regular structure. For example, the CSX format [15] extracts regular dense patterns (e.g., dense rectangular blocks, diagonal and vertical lines) within the matrix, while the VBFS format [18] uses dense blocks of non-fixed size. For matrices with small dense blocks, block analogues of classical formats are often used: block compressed sparse row (BCSR), block coordinate (BCOO), and generalized block coordinate (BCCOO) [33]. Many papers have investigated hybrid versions of classical formats in various combinations, for example, COO + ELL (HYB format [2]), COO + CSR, CSR + DIA, SELL-C-σ + CSR5 (HYB5 [6]), and others. For GPUs, modifications of the ELLPACK format [14] are widely used: ELL-R [29], SELL [20], SELL-C-σ [17], and others. The latter format, SELL-C-σ, also demonstrates high performance on x86 processors [12]. In [11], the performance of this format was studied on CPUs supporting long vector registers. Note that for the x86 architecture, the most common software libraries (Intel oneAPI MKL, AOCL-Sparse, SparseBLAS, and others) support sparse matrix representations in CSR, CSC, COO, DIA, and BCSR formats. For graphics processors, CSR, BCSR, CSC, COO, and ELL modifications are typically supported. For most custom storage formats, the SpMV operation is implemented as a standalone code. Although often publicly available, integrating it into third-party software packages, such as iterative SLAE solvers, frequently requires significant additional engineering effort. A number of papers discuss automatic selection of the optimal matrix storage format to yield the best performance using machine learning methods. For instance, the paper [34] proposed the WISE machine learning framework, which uses decision trees to predict the SpMV operation speedup for various storage formats compared to CSR. In [35], CNNs trained on 2D matrix images were utilized. The authors of [1] proposed an approach for determining the optimal threading configuration for SpMV computations in shared-memory architectures. In
1. We propose a new sparse matrix storage format, HCSR. Compared to scalar and typical vectorized SpMV implementations for the CSR format, the new format improves average SpMV performance on RISC-V CPUs by 1.6x. 2. We present a comparative performance analysis of the SpMV operation on two generations of RISC-V processors across different storage formats. 3. We discuss the tunability of hyperparameters for various storage formats and identify the main characteristics of sparse matrices that influence format selection. 4. We release the RVVLASparse library, which implements SpMV algorithms for nine sparse data structures for RISCV CPUs, as publicly available open-source software. The remainder of this paper is structured as follows. Section section 2 provides an overview of sparse matrix storage formats. Section section 3 describes several matrix storage formats along with their corresponding SpMV algorithms and details the new HCSR format. Section section 4 presents experimental results for all implemented formats and analyzes SpMV performance. Section section 5 describes the results of automatic storage format selection based on matrix sparsity pattern characteristics using gradient boosting of decision trees. Finally, Section section 6 concludes the paper and outlines future work plans. 2. Related Work Several papers on software development for RISC-V CPUs address low-level optimization of linear algebra algorithms. Specifically, we previously proposed efficient vectorized implementations for BLAS operations with band matrices based on the reference from OpenBLAS [24]. In [25], dense linear 1 https://github.com/UNN-ITMM-Software/RVVLASparse
2
[9], a method is proposed for generating a machine-designed format and SpMV algorithm that combines several base formats. Our project adapts ideas from the WISE framework for the mechanism of automatic format selection based on the matrix structure. We also note that a closely related work [28] appeared during the preparation of this paper. In [28], vectorized algorithms for the SpMV operation were proposed for CSR, SELL-p, and JDS formats on RISC-V processors. The results were presented on three RISC-V platforms and demonstrated a noticeable performance improvement for SpMV due to vectorization. The best performance was achieved by the authors for the SELL-p format. A comparison with this implementation will be presented in Section section 4.4.
Listing 1 shows the pseudo-code for the vectorized implementation of CSR-based SpMV in double precision. The algorithm assumes that the vector register holds gvl doubleprecision elements. In the pseudo-code, the dot product of row A[i] and vector b is computed via a contiguous vector load from Val and an indexed load from b (lines 8–12). The products are accumulated in res (line 13) and subsequently reduced after the loop (lines 16–18). The efficiency of vectorizing the CSR SpMV algorithm is highly dependent on the number of nonzeros in each row. Specifically, for highly sparse matrices, the number of nonzeros per row may be too low to fully utilize the vector registers. A second issue with the CSR SpMV algorithm is irregular access to vector b, which causes numerous cache misses, degrades cache utilization, and hinders data reuse. A third issue is load imbalance in the parallel implementation, although this can be addressed through dedicated load-balancing strategies.
3. SpMV Algorithm for Various Matrix Storage Formats 3.1. Sparse matrix-vector multiplication Let A ∈ RN×M be a sparse matrix with NZ nonzeros, b ∈ R M and y ∈ RN be dense vectors, and α, β ∈ R be scalar coefficients. Real numbers are represented as floating-point numbers. The objective is to compute the result of the following operation: y = αAb + βy
3.3. Sell-C-σ Format The Sell-C-σ format was introduced in [17] as an ELLPACKbased storage scheme tailored for CPUs with SIMD support and GPUs. To build a matrix in this format, the original matrix is first partitioned into slices of width σ, and within each slice, rows are sorted by descending nonzero count. The rows in each slice are then grouped into chunks of C rows, and each chunk is padded with zeros to ensure uniform row length within the chunk. Within every chunk, the nonzero values and their column indices are stored column-wise in the Val and Col arrays: i.e., the first nonzero element of each row in the chunk is stored first, followed by the second nonzero element of each row, and so forth. In addition, metadata describing chunk sizes and offsets is stored, together with the global row permutation perm. The vectorized Sell-C-σ SpMV algorithm is shown in listing 2. The algorithm assumes that the vector register holds bs double-precision values. In the pseudo-code, computations are parallelized blockwise. For each block, the vector register v_py accumulates partial sums of the products of C rows of the matrix and vector b. This is done by multiplying each block of bs nonzeros by their corresponding elements in vector b (lines 10–14). After processing the block, the updated y values are loaded and stored using the permutation computed during the Sell-C-σ conversion (lines 16–21). Notably, the row permutation and column-wise block layout enable the use of contiguous loads rather than indexed loads for the matrix entries, while also eliminating expensive reductions. Furthermore, the vector length parameter remains fixed for most of the intrinsics used. For certain matrices, these factors can provide considerable performance gains over the vectorized CSR version.
(1)
By definition, every element of the vector y is calculated as follows: yi =
M ∑︁
αAi j b j + βy j
for
i = 1, . . . , N
(2)
j=1
For a sparse matrix A, the algorithm for evaluating eq. (2) depends on the matrix storage format. A straightforward implementation of SpMV using the traditional CSR, CCS, and COO formats has significant performance limitations. In this paper, we present an implementation of the SpMV operation in both single and double precision using nine storage formats: CSR, Sell-C-σ, CSR2, CSR5, CVR, VHCC, VNEC, LAV, and a novel format introduced herein, named Hierarchical CSR (HCSR). The implementation is built upon RVV 1.0 intrinsics and OpenMP. For the sake of conciseness and clarity, we restrict our algorithmic exposition to the formats that achieved the highest performance in our numerical evaluation, along with a thorough description of the proposed HCSR format. Detailed discussions of the other formats are deferred to their original publications. 3.2. CSR Format The Compressed Sparse Row (CSR) format is a standard sparse matrix storage scheme supported by most sparse linear algebra libraries. In CSR, the nonzeros of the matrix are stored row by row. The representation consists of three arrays: Val stores the nonzero values in row-major order, Col holds their column indices, and rowIndex marks the beginning of each row within the Col array. The Val and Col arrays are of size NZ, and rowIndex is of size N + 1 (see fig. 1).
3.4. CSR5 Format The CSR5 format was introduced in [19] as an extension of CSR for CPUs with SIMD units and GPUs. It offers good load balancing under parallel execution and supports uniform storage of matrices with arbitrary nonzero patterns. 3
Listing 1: SpMV algorithm for CSR format 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
void SP_MV_CSR_RVV ( CSRmatrix mat , double * b , double * y , double alpha , double beta ) { size_t vlmax = _ _ r i s c v _ v s e t v l m a x _ e 6 4 m 4 () ; # pragma omp parallel for for ( int i = 0; i < mat . m ; ++ i ) { size_t vl = vlmax ; vfloat64m4_t res = _ _ r i s c v _ v f m v _ v _ f _ f 6 4 m 4 (0.0 , vl ) ; for ( int j = mat . Rst [ i ]; j < mat . Rst [ i + 1]; j += vlmax ) { vl = _ _ r i s c v _ v s e t v l _ e 6 4 m 4 ( mat . Rst [ i + 1] - j ) ; { vfloat64m4_t val = _ _ r i s c v _ v l e 6 4 _ v _ f 6 4 m 4 ( mat . Val + j , vl ) ; vuint32m2_t index = _ _ r i s c v _ v l e 3 2 _ v _ u 3 2 m 2 ( mat . Col + j , vl ) ; vuint32m2_t index_shift = _ _ r i s c v _ v s l l _ v x _ u 3 2 m 2 ( index , 3 , vl ) ; vfloat64m4_t b_ = _ _ r i s c v _ v l o x e i 3 2 _ v _ f 6 4 m 4 (b , index_shift , vl ) ; res = _ _ r i s c v _ v f m a c c _ v v _ f 6 4 m 4 _ t u ( res , val , b_ , vl ) ; } vl = _ _ r i s c v _ v s e t v l _ e 6 4 m 4 ( vlmax ) ; vfloat64m1_t zero = _ _ r i s c v _ v f m v _ v _ f _ f 6 4 m 1 (0.0 , vl ) ; vfloat64m1_t sum = _ _ r i s c v _ v f r e d u s u m _ v s _ f 6 4 m 4 _ f 6 4 m 1 ( res , zero , vl ) ; double tmp = _ _ r i s c v _ v f m v _ f _ s _ f 6 4 m 1 _ f 6 4 ( sum ) ; y [ i ] = alpha * tmp + beta * y [ i ]; } }
Listing 2: SpMV algorithm for Sell-C-σ format 1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
void S P _ M V _ S E L L _ C _ S I G M A _ R V V ( S E L L _ C _ S I G M A m a t r i x mat , double * b , double * y , double alpha , double beta ) { # pragma omp parallel for for ( int i = 0; i < mat . cnt_b ; i ++) { int cur_pos = SBs [ i ]; uint32_t bs = _ _ r i s c v _ v s e t v l m a x _ e 6 4 m 2 () ; for ( int k = 0; k < Bs [ i ]; k += bs ) { bs = _ _ r i s c v _ v s e t v l _ e 6 4 m 2 ( Bs [ i ] - k ) ; vfloat64m2_t v_py = _ _ r i s c v _ v f m v _ v _ f _ f 6 4 m 2 (0.0 , bs ) ; for ( int j = 0; j < Cl [ i ]; j ++) { vuint32m1_t index = _ _ r i s c v _ v l e 3 2 _ v _ u 3 2 m 1 ( Col + Cs [ i ]+ j * Bs [ i ] + k , bs ) ; vuint32m1_t index_shift = _ _ r i s c v _ v s l l _ v x _ u 3 2 m 1 ( index , 3 , bs ) ; vfloat64m2_t v_val = _ _ r i s c v _ v l e 6 4 _ v _ f 6 4 m 2 ( Val + Cs [ i ] + j * Bs [ i ] + k , bs ) ; vfloat64m2_t v_b = _ _ r i s c v _ v l o x e i 3 2 _ v _ f 6 4 m 2 (b , index_shift , bs ) ; v_py = _ _ r i s c v _ v f m a c c _ v v _ f 6 4 m 2 ( v_py , v_val , v_b , bs ) ; } vuint32m1_t index_perm = _ _ r i s c v _ v l e 3 2 _ v _ u 3 2 m 1 ( Perm + cur_pos + k , bs ) ; vuint32m1_t i n d e x _ p e r m _ s h i f t = _ _ r i s c v _ v s l l _ v x _ u 3 2 m 1 ( index_perm , 3 , bs ) ; vfloat64m2_t v_py_c = _ _ r i s c v _ v l o x e i 3 2 _ v _ f 6 4 m 2 (y , index_perm_shift , bs ) ; v_py_c = _ _ r i s c v _ v f m u l _ v f _ f 6 4 m 2 ( v_py_c , beta , bs ) ; v_py = _ _ r i s c v _ v f m a d d _ v f _ f 6 4 m 2 ( v_py , alpha , v_py_c , bs ) ; _ _ r i s c v _ v s o x e i 3 2 _ v _ f 6 4 m 2 (y , index_perm_shift , v_py , bs ) ; } } }
4
Figure 1: Sparse matrix storage scheme using the CSR format.
Figure 2: Sparse matrix storage scheme using the Sell-C-σ format.
In the CSR5 format, nonzeros and their column indices are stored in fixed-size dense 2D tiles (fig. 3). The format has two parameters, ω and σ. ω is the tile width, which corresponds to the vector register length, and σ is the tile height, which is a tunable parameter chosen experimentally. Elements within a tile are stored column-wise so that a single SIMD lane processes an entire column during SpMV. The position of a tile in the matrix is determined by the row number of its first element, which is stored in the tileptr array; empty rows within a tile are also marked in tileptr. In fig. 3, such markers are shown as negative values. Additionally, each tile maintains a descriptor that encodes its internal structure. Let B be the tile matrix and j be the current column index. For each column, the tile descriptor includes the following:
in the bit_flag array; • y_offset – an integer array used to compute the index in vector y where the product should be written; • seg_offset – an integer array used for rows that occupy multiple columns within the tile. It specifies the number of subsequent columns that are completely filled by the last row beginning in the current column; • empty_offset – an array shared across all columns, utilized when the tile contains empty rows to maintain correct indexing into vector y.
• bit_flag – an array of bits of length σ, with bit_flag[i] = 1 if the corresponding entry B[i][ j] is the first nonzero in its row. For the correctness of the SpMV algorithm, the first element of the first column of the tile is also marked 5
In our implementation, bit_flag, y_offset, and seg_offset are stored as bit fields within one or more 32bit integers in the tiledesc array. The empty_offset entries for all blocks are stored in a single shared array. The SpMV operation for a matrix in CSR5 format can be performed independently per tile. When all entries of a tile
Figure 3: Sparse matrix storage scheme using the CSR5 format. It is assumed that tiles contain no empty rows.
belong to the same row of the original matrix, no cross-column accumulation is required, and the product is computed in the same way as in CSR. The pseudo-code for this case is given below (listing 3). The computation proceeds row by row through the tile. As in CSR, for each row the corresponding values from the Val and b arrays are loaded, an FMA operation is performed, and the products are accumulated into the vector register sum. If a block contains elements from two or more rows of the original matrix, a more complex algorithm is used. Within each column of a tile, the elements belonging to the same matrix row form contiguous segments. These segments can be classified into three categories: “red” – the row is the first in the tile or starts in one of the previous columns; “green” – the row lies entirely within the column; and “blue” – the row extends beyond the current tile. When a tile spans multiple rows, the partial results must be combined appropriately. The pseudo-code for this case is shown in listing 4. During row processing, whenever a “green” segment ends in a column, the corresponding entry in the sum register holds the complete result. This accumulated value is stored in vector y (lines 14–20). All such columns are marked in a mask vector register green_mask. If a “red” segment ends, the result is stored in first_sum for later use (lines 21–27). All such columns are marked in red_mask. After the loop terminates, sum holds the results for the “blue” segments marked in blue_mask. These need to be combined with the values in first_sum to compute the correct result for rows spanning multiple tile columns. To do so, sum is copied to last_sum; first_sum is copied to sum and shifted left by one lane; a prefix sum is computed on sum, and the resulting values are added to the corresponding elements of last_sum according to the blue segment mask (lines 28–35). As a result, last_sum contains the correct value for rows with “blue” segments, which is then stored in y (listing 4). In each tile, the first row of the original matrix is treated in a
special way due to parallel tile processing. In our implementation, static OpenMP scheduling is used to distribute tiles among threads. Consequently, each thread computes a product for a contiguous segment of rows of the original matrix. Under this scheme, the value computed for the first row in the row segment may be incorrect, because part of the product for that row may be computed by the preceding thread. For such rows, results from different threads must be combined correctly. This is done as follows. A shared array calibrator of length equal to the thread count is used. Each thread stores its portion of the product for the first row it processes in this array (lines 37–41). After the parallel region, the entries of the calibrator array are used to update vector y at the positions corresponding to the conflicting rows. The implementations of the SpMV algorithm in CSR5 format using AVX instructions and RVV instructions are generally similar. An important difference is that RVV contains more specific instructions, such as vector slide operations, bitwise operations with mask vector registers, and masked instructions. The latter also takes a mask register as input and performs the operation only on those elements for which the corresponding bit in the mask register is set. All these features enable the implementation of the algorithm using fewer instructions. Furthermore, RVV instructions can operate on a group of registers, where the number of registers is determined by the LMUL parameter in the vector configuration. The LMUL affects the number of tile columns and needs to be chosen carefully to achieve the best performance. 3.5. HCSR Format We propose a novel storage format, Hierarchical CSR (HCSR), a block-based variant of CSR. Although block variants of the CSR format have been widely discussed in the literature, we 6
Listing 3: SpMV algorithm for CSR5 format for tile containing elements from one row of the matrix 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
void S P _ M V _ C S R 5 _ R V V _ S I M P L E _ L O O P ( CSR5matrix mat , FLOAT * b , FLOAT * y , FLOAT alpha ) { size_t vl = _ _ r i s c v _ v s e t v l m a x _ e 6 4 m 2 () ; vfloat64m2_t sum = _ _ r i s c v _ v f m v _ v _ f _ f 6 4 m 2 (0.0 , vl ) ; for ( int i = 0; i < sigma ; i ++) { vuint32m2_t vcol = _ _ r i s c v _ v l e 3 2 _ v _ u 3 2 m 2 ( mat . col + i * omega , vl ) ; vcol = _ _ r i s c v _ v s l l _ v x _ u 3 2 m 2 ( vcol , 3 , vl ) ; vfloat64m2_t vx = _ _ r i s c v _ v l o x e i 3 2 _ v _ f 6 4 m 2 (b , vcol , vl ) ; vfloat64m2_t vval = _ _ r i s c v _ v l e 6 4 _ v _ f 6 4 m 2 ( mat . val + i * omega , vl ) ; sum = _ _ r i s c v _ v f m a d d _ v v _ f 6 4 m 2 ( vval , vx , sum , vl ) ; } vfloat64m2_t vzero = _ _ r i s c v _ v f m v _ v _ f _ f 6 4 m 2 (0.0 , vl ) ; sum = _ _ r i s c v _ v f r e d u s u m _ v s _ f 6 4 m 2 _ f 6 4 m 1 ( sum , vzero , vl ) ; vfloat64m1_t res = _ _ r i s c v _ v f m v _ f _ s _ f 6 4 m 1 _ f 6 4 ( sum , vl ) ; if ( t h r e a d _ f i r s t _ r o w ) mat . calibrator [ thread_id ] += res * alpha ; else y [ current_row ] += res * alpha ; }
Listing 4: SpMV algorithm for CSR5 format for tile containing elements from different rows of the matrix 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
void S P_MV_C SR5_RV V ( CSR5matrix mat , FLOAT * b , FLOAT * y , FLOAT alpha ) { size_t vl = _ _ r i s c v _ v s e t v l m a x _ e 6 4 m 2 () ; vfloat64m2_t sum = _ _ r i s c v _ v f m v _ v _ f _ f 6 4 m 2 (0.0 , vl ) ; vfloat64m2_t first_sum = _ _ r i s c v _ v f m v _ v _ f _ f 6 4 m 2 (0.0 , vl ) ; vfloat64m2_t vval = _ _ r i s c v _ v l e 6 4 _ v _ f 6 4 m 2 ( mat . val , vl ) ; vuint32m2_t vcol = _ _ r i s c v _ v l e 3 2 _ v _ u 3 2 m 2 ( mat . col , vl ) ; vcol = _ _ r i s c v _ v s l l _ v x _ u 3 2 m 2 ( vcol , 3 , vl ) ; vfloat64m2_t vx = _ _ r i s c v _ v l o x e i 3 2 _ v _ f 6 4 m 2 (x , vcol , vl ) ; sum = _ _ r i s c v _ v f m a d d _ v v _ f 6 4 m 2 ( vval , vx , sum , vl ) ; for ( int i = 1; i < sigma ; ++ i ) { vcol = _ _ r i s c v _ v l e 3 2 _ v _ u 3 2 m 2 ( mat . col + i * vl , vl ) ; vcol = _ _ r i s c v _ v s l l _ v x _ u 3 2 m 2 ( vcol , 3 , vl ) ; vx = _ _ r i s c v _ v l o x e i 3 2 _ v _ f 6 4 m 2 (x , vcol , vl ) ; if ( _ _ r i s c v _ v c p o p _ m _ b 3 2 ( green_mask , vl ) > 0) { vfloat64m2_t vy = _ _ r i s c v _ v l o x e i 3 2 _ v _ f 6 4 m 2 _ m ( green_mask , y , vy_off , vl ) ; vy = _ _ r i s c v _ v f m a d d _ v f _ f 6 4 m 2 ( vy , sum , alpha , vl ) ; _ _ r i s c v _ v s o x e i 3 2 _ v _ f 6 4 m 2 _ m ( green_mask , y , vy_off , vy , vl ) ; sum = _ _ r i s c v _ v m e r g e _ v v m _ f 6 4 m 2 ( sum , 0.0 , green_mask , vl ) ; vfloat64m2_t vy_off = _ _ r i s c v _ v a d d _ v x _ u 6 4 m 2 _ m ( green_mask , vy_off , 1 , vl ) ; } if ( _ _ r i s c v _ v c p o p _ m _ b 3 2 ( red_mask , vl ) > 0) { first_sum = _ _ r i s c v _ v m e r g e _ v v m _ f 6 4 m 2 ( first_sum , sum , red_mask , vl ) ; sum = _ _ r i s c v _ v m e r g e _ v v m _ f 6 4 m 2 ( sum , 0.0 , red_mask , vl ) ; } vval = _ _ r i s c v _ v l e 6 4 _ v _ f 6 4 m 2 ( val + i * vl , vl ) ; sum = _ _ r i s c v _ v f m a d d _ v v _ f 6 4 m 2 ( vval , vx , sum , vl ) ; } vfloat64m2_t last_sum = _ _ r i s c v _ v s e 6 4 _ v _ f 6 4 m 2 ( sum , vl ) ; sum = _ _ r i s c v _ v m e r g e _ v v m _ f 6 4 m 2 ( sum , first_sum , first_mask , vl ) ; sum = _ _ r i s c v _ v s l i d e d o w n _ v x _ f 6 4 m 2 ( sum , 1 , vl ) ; vfloat64m2_t tmp_sum = _ _ r i s c v _ v s e 6 4 _ v _ f 6 4 m 2 ( sum , vl ) ; sum = prefix_sum ( sum ) ; vfloat64m2_t sum_perm = _ _ r i s c v _ v r g a t h e r _ v v _ f 6 4 m 2 ( sum , perm , vl ) ; sum = _ _ r i s c v _ v f a d d _ v v _ f 6 4 m 2 ( _ _ r i s c v _ v f s u b _ v v _ f 6 4 m 2 ( sum_perm , sum ) , tmp_sum ) ; last_sum = _ _ r i s c v _ v f a d d _ v v _ f 6 4 m 2 ( blue_mask , last_sum , sum , vl ) ; _ _ r i s c v _ v s o x e i 3 2 _ v _ f 6 4 m 2 _ m ( blue_mask , y , vy_off , last_sum , vl ) ; if ( t h r e a d _ f i r s t _ r o w ) mat . calibrator [ thread_id ] += first_prod * alpha ; else y [ first_row ] += first_prod * alpha ; }
7
propose to store the block partitioning structure of the original matrix also as a sparse matrix. In HCSR, we split the matrix into blocks of fixed size R × C. Each nonempty block is stored either in CSR or in COO format, depending on its nonzero occupancy; otherwise, it is marked as empty. Note that when the matrix dimensions are not divisible by R and C, the last block column contains blocks of size R × (M mod C), and the last block row contains blocks of size (N mod R) × C. We use a switching threshold pfix , computed as the average number of nonzeros per row in the original matrix. The occupancy of a block is defined as pblock = nzblock /R, where nzblock is the number of nonzero entries in the block. Based on this threshold, a block is stored in CSR if pblock > pfix ; otherwise, COO is used. Since the block decomposition of the matrix, including empty blocks, forms a sparse structure, we store the nonempty block information in CSR format. Thus, the HCSR representation of a sparse matrix consists of five arrays (fig. 4):
Thus, we obtain the two-level matrix storage scheme that combines the advantages of standard sparse formats and, in many cases, improves cache efficiency. Note that the sparse block representation approach can be extended recursively, for example, during distributed processing of huge sparse matrices. For this reason, we call the new format hierarchical, although in this paper we limit ourselves to two levels, which are sufficient for the RISC-V processors we use. 4. Experimental Results 4.1. Experimental Setup Experiments were carried out on two devices. The first test system, the Banana Pi BPI-F3 board, features a SpacemiT Keystone K1 processor (8x1.6GHz SpacemiT x60 cores with 8-stage in-order dual-issue pipeline, RVA22 Profile and 256bit RVV 1.0 standard) with 16 GB of RAM and the Bianbu 2.1 operating system. The Banana Pi BPI-F3 (8x X60) has a theoretical peak double precision performance of 102.4 GFLOPs and a single precision performance of 204.8 GFLOPs. The second test system is based on the SpacemiT Keystone K3 processor (8x SpacemiT X100 high-performance cores clocked at up to 2.4 GHz with 12-stage out-of-order quad-issue pipeline, RVA23 Profile and RVV 1.0 standard with VLEN=256 and 8x SpacemiT A100 AI cores clocked at up to 2.1 GHz with 8-stage in-order dual-issue pipeline, RVA22 Profile and RVV 1.0 standard with VLEN=1024) with 8 GB of RAM (LPDDR5-6400) and the Bianbu 4.0.1 operating system. The SpacemiT K3 high-performance cores (8x X100) feature a theoretical peak double precision performance of 153.6 GFLOPs and a single precision performance of 307.2 GFLOPs. The SpacemiT K3 AI cores (8x A100) offer a theoretical peak double precision performance of 134.4 GFLOPs, a single precision performance of 537.6 GFLOPs, and up to 60 TOPS of AI performance. All our experiments were performed using only X100 cores. A GCC RISC-V 14.2.0 cross-compiler was used on both test systems.
• values – an array of nonzero values of the matrix, shared across all blocks; • col_idx – an array of column indices of nonzero values, shared across all blocks; • row_ptr – an array of row-start indices in the col_idx array for CSR blocks, or row indices of nonzeros for COO blocks, shared across all blocks; • row_offset – an array where the lower 30 bits of each element store the offset into the row_ptr array for each block, and the upper 2 bits store a key value describing the block type (0 for empty, 1 for CSR, or 2 for COO); • block_ptr – an array of offsets into the col_idx and values arrays for each block. The HCSR-based SpMV algorithm performs a parallel traversal of the matrix, proceeding row-wise through the nonempty block rows (listing 5). Unlike the standard CSR format, which operates on individual matrix entries and vector elements, the HCSR scheme computes the product of each nonempty block of the matrix with the corresponding segment of vector b. Compared to traditional CSR, the use of the new format still preserves efficient processing of nonzero values in the matrix, while improving the locality of accesses to the vector b. In the pseudocode, for each block being processed (lines 8–18), we first compute its parameters: the block number block (line 8), the number of nonzeros nz (line 14), the offset row_ptr_offset into the row_ptr array (line 13), and the block type key. Depending on the block type, either KERNEL_HCSR_CSR (line 16) or KERNEL_HCSR_COO (line 18) is called. The KERNEL_HCSR_CSR function is essentially the same as the vectorized CSR SpMV implementation in listing 1, aside from the vector register length and the multiplication of y by β. For KERNEL_HCSR_COO, we use a scalar implementation, as experimental evaluation demonstrated that the vectorized version of this function is less performant than the scalar one.
4.2. Benchmark Suite A set of 121 matrices from the SuiteSparse Matrix collection [7] was used in the experiments. Our test set covers matrices from a variety of application domains, including HPC applications and graph processing. Many of them have been used in previous SpMV-related studies. The benchmark suite included matrices of sizes from 0.5K to 8.39M rows, with fill-in from 3.1 × 10−7 % to 1.4 × 10−2 %. Detailed information about the test set is given in table A.5. For eq. (1), the dense vector b was filled with random numbers from the interval [0, 1), and the scalar coefficients α and β were fixed to 1.0 and 0.0, respectively. For the formats that support tunable block sizes (Sell-C-σ, CSR5, VHCC, HCSR), we pre-tuned the parameter sets to find the combinations that minimize the computation time on most test matrices, separately for single and double precision. All experiments were run using 1 and 8 cores in both single and double precision. For each format, the minimum time of a single 8
Figure 4: Sparse matrix storage scheme using the HCSR format.
• Sell-C-σ achieves the best performance among all evaluated formats in single-core execution. It outperforms CSR by an average of 1.5× on 107 matrices. On 8 cores, however, its runtime is comparable to that of scalar CSR.
SpMV operation across five independent runs was used for performance comparison. For each test case, we compare the results by taking the ratio of the SpMV runtime for a given matrix and format to the run time of the scalar CSR SpMV implementation. The relative speedups over CSR are presented as heatmaps in section 4.3. Yellow indicates values close to 1.0 (no speedup), red marks the lowest performance (near 0.0), and green denotes the best values (> 1.0). The matrices are sorted by increasing fill-in. We have observed that the performance of vectorized SpMV implementations is highly sensitive to the choice of the LMUL parameter. For highly sparse matrices, the runtime can differ by a factor of two or three. Thus, to maximize performance, LMUL must be chosen by taking into account both the hardware and the matrix structure. For instance, in the CSR format, the fastest execution for highly sparse matrices was obtained with LMUL=1 in single precision and LMUL=2 in double precision. For denser matrices, LMUL=4 performed best in both precisions. For the results presented below, a single LMUL value was selected per format for all test matrices, with separate tuning for single and double precision.
• HCSR outperforms both scalar and vectorized CSR on most matrices, with average speedups of 1.6× where it wins. The most substantial improvements are observed for rectangular matrices and Kronecker matrices. On 8 cores, HCSR is the fastest format on 80 of the 121 matrices, with an average speedup of 1.6× over scalar CSR. • CVR and VNEC perform close to scalar CSR in singlecore execution, but in parallel, they outperform it by 10% on average. • CSR5 and VHCC significantly outperform CSR on rectangular and denser matrices, with average speedups of 1.6×. The advantage increases with the number of cores employed. • CSR2 and LAV perform worse than CSR, with average slowdowns of 34% and 20%, respectively. However, on a single core for denser matrices, LAV outperforms CSR by 25% on average.
4.3. SpMV performance comparison 4.3.1. SpacemiT K1 For the SpacemiT K1 platform, fig. 5 compares the execution time of a single SpMV operation for all implemented formats relative to the scalar CSR implementation. Figure 6 presents the speedup distribution. Analyzing the results allows us to summarize the performance of each sparse format as follows:
Figure 7 shows the speedup of all formats over scalar CSR in single precision. Figure 8 shows the speedup distribution. The results indicate that, similarly to double precision, Sell-Cσ delivers the best single-core performance on most matrices, being 1.5× faster than CSR on average. On 8 cores, HCSR is the fastest, achieving average speedups of 1.7× over CSR (fig. 9). The vectorized CSR implementation is also faster than its scalar analogue, with an average speedup of 16%, though this gain is lower than in double precision. Notably, CSR5 exhibits a substantially higher speedup, outperforming scalar CSR on most matrices by an average factor of 1.2.
• The vectorized CSR implementation is faster than its scalar analogue on 100 of the 121 matrices, delivering average speedups of 1.4× on a single core and 1.1× on 8 cores where it wins. 9
Listing 5: SpMV algorithm for HCSR format 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
17 18
19 20 21 22
void SPMV_HCSR ( HCSRmatrix mat , double * b , double * y , double alpha , double beta ) { # pragma omp parallel for schedule ( dynamic ) for ( int i = 0; i < mat . m ; i += mat . R ) { int maxr = min ( mat .R , mat . m - i ) ; for ( int r = 0; r < maxr ; ++ r ) { y [ i + r ] *= beta ; for ( int j = 0; j < mat . n ; j += mat . C ) { int block = j / mat . C + ( i / mat . R ) * mat . b_n ; int bptr = mat . block_ptr [ block ]; int row _ptr_o ffset = mat . row_offset [ block ]; int mask = 0 x3FFFFFFF ; int key = row_p tr_off set >> 30; row_ ptr_of fset &= mask ; int nz = mat . block_ptr [ block + 1] - bptr ; if ( key == 1) K ER N EL _H C SR _C S R ( alpha , mat . row_ptr + row_ptr_offset , mat . col_idx + bptr , mat . values + bptr , b + j , y + i , maxr ) ; else K ER N EL _H C SR _C O O ( alpha , mat . row_ptr + row_ptr_offset , mat . col_idx + bptr , mat . values + bptr , b + j , y + i , nz ) ; } } } }
23 24
25 26 27
void K ER NE L _H CS R _C OO ( double alpha , int * row_ptr , int * col_idx , double * values , double * b , double * y , int nz ) { for ( int i = 0; i < nz ; ++ i ) y [ row_ptr [ i ]] += alpha * values [ i ] * b [ col_idx [ i ]]; }
In [28], the authors reported a performance of vectorized CSR of 0.05–1.25 GFlops/s on 8 cores of SpacemiT K1 (double precision). Our vectorized CSR falls within a similar range: 0.03–1.22 GFlops/s, with a mean of 0.67 GFlops/s and variance of 0.15. These results validate the competitiveness of our implementation.
3. The performance gap between scalar CSR and vectorized formats is considerably wider on the SpacemiT K3 than on the K1. This observation applies to CSR itself and is particularly evident for formats using fixed-width block processing (Sell-C-σ, CSR5, CSR2, CVR). The average and maximum speedups over scalar CSR have increased for all formats except VHCC (which is now slower) and HCSR. HCSR demonstrates better stability with respect to these metrics: its average speedup over CSR varies by 20% across the two platforms, while the maximum speedup is unchanged.
4.3.2. SpacemiT K3 We next evaluate SpMV performance on the SpacemiT K3 processor. Compared to the K1, the absolute SpMV time is reduced on average by 3× (double precision) and 2× (single precision). For web graphs, Kronecker matrices, and some rectangular matrices, the reduction reaches up to 18× on a single core for selected formats. Figure 10 presents the relative SpMV speedups in double precision, and fig. 11 shows their distribution. For single precision, the speedups are shown in fig. 12, with the corresponding distribution in fig. 13. The experimental results lead to the following key observations:
4. Vectorized CSR shows considerably improved performance relative to the other formats, outperforming all other implementations on a substantial portion of the test matrices. We next consider the count of matrices where each format attains the lowest running time (fig. 14). On one core, vectorized CSR leads in double precision and Sell-C-σ in single precision. On 8 cores, HCSR outperforms all other implementations on the majority of matrices (fig. 14).
1. On a single core, vectorized CSR, CSR5, Sell-C-σ, and HCSR achieve the best performance among all formats in both single and double precision. They outperform scalar CSR by 1.7×–2.2× on average, with Sell-C-σ being the fastest.
4.4. Discussion The fast-paced evolution of RISC-V technology drives strong interest in performance evaluation of new hardware, especially when a vendor releases a next-generation device. We therefore analyze how the SpacemiT K3 affects SpMV performance compared to the previous-generation SpacemiT K1. We first
2. On 8 cores, vectorized CSR, CSR5, and HCSR yield the best performance, outperforming scalar CSR by 1.5×–2.1× on average. Sell-C-σ also outperforms CSR, but with a more modest speedup (1.2× on average). 10
Figure 5: SpMV speedup for various sparse formats relative to scalar CSR (SpacemiT K1, double precision).
Figure 6: Distribution of SpMV speedup for various sparse formats relative to scalar CSR (SpacemiT K1, double precision).
highlight the key differences of the new device that are relevant to this study. First, the K3 device features significantly faster memory (LPDDR5-6400 vs. LPDDR4/LPDDR4x-2666). While peak memory bandwidth figures give a rough estimate, the STREAM benchmark provides more meaningful real-world measurements of memory subsystem performance. We adapted our earlier benchmark [30] for RVV 1.0 and used the following experimental methodology. We ran four tests that perform elementary array operations (Copy, Scale, Add, Triad). The array sizes are selected so that the working set fits entirely in L1 cache, L2 cache, and DRAM, respectively. Both scalar and vectorized versions are executed with thread binding aligned to the memory hierarchy. The workload was configured as follows: 1 thread was used for L1 testing (with the result scaled by 8), 4 threads for the shared L2 (scaled by 2), and 8 threads for measuring the global DRAM bandwidth. The results (table 1) demonstrate a substantial increase in achieved memory bandwidth, from 6.9 GB/s on the K1 to 19.9 GB/s on the K3 – a speedup of nearly 3×.
This improvement is particularly significant for memory-bound algorithms like SpMV, which has an arithmetic intensity of ∼0.1 FLOP/byte. Second, it is worth noting that the K3 employs an Out-ofOrder (OoO) CPU, unlike the In-Order CPU in the K1. This difference is crucial for performance. With in-order execution, the pipeline stalls on memory accesses; OoO, by contrast, allows independent instructions to proceed, boosting throughput and hardware utilization. This effect is challenging to model and quantify in a general setting; instead, one must experiment with the specific algorithm on specific data sets and analyze various indirect performance indicators. We collected available PMU counters on the SpacemiT K1 and K3 using the perf utility. Although the set of available counters is relatively limited, we selected the most informative ones. For the experiments, we used matrix spal_004 (10K rows, 321K columns, 46M nonzeros). table 2 shows the metrics for SpMV execution in three formats: CSR, Sell-C-σ, and HCSR. 11
Figure 7: SpMV speedup for various sparse formats relative to scalar CSR (SpacemiT K1, single precision).
Figure 8: Distribution of SpMV speedup for various sparse formats relative to scalar CSR (SpacemiT K1, single precision).
The results show a significant performance gain on the K3 compared to the K1, consistent with the memory bandwidth improvement seen in STREAM. The IPC values and stalled-cycles counter, which reflects the aggregate core idle time, confirm that the workload is memory-bound, with compute units stalled about 95% of the time regardless of format or hardware. The L1D-load-miss count, which measures L1 data cache misses, increases several times for CSR on the K3. We attribute this to faster instruction processing, which increases memory request rates and L1 misses. On the K1, this effect is weaker due to longer memory access intervals. In contrast, the HCSR format exhibits a different behavior: since this algorithm is designed to be cache-friendly, its performance advantages are further amplified on the new architecture. Notably, OoO execution significantly affects SpMV performance and likely other sparse linear algebra algorithms. This stems from their low arithmetic intensity and irregular memory accesses, including indexed loads that lead to a large number of
cache misses. The X100 OoO core in the SpacemiT K3 can partially hide these latencies by issuing and handling significantly more memory requests concurrently. This architectural feature explains the significant performance gain on the new hardware. When comparing various sparse matrix storage formats, it is informative to examine their effective memory bandwidth. For our estimation, we assume that each nonzero element (NZ) requires loading at least 20 bytes of data in sparse formats. The effective memory bandwidth was calculated as the ratio of the useful data volume (20 bytes × NZ) to the execution time of a single multiplication. The analysis shows that the standard CSR algorithm on both hardware platforms utilizes almost 70% of the peak DRAM bandwidth (the remainder corresponds to the inherent overhead of the algorithm). The Sell-C-σ format achieves near-peak DRAM bandwidth for the matrix under study. This indicates that efficient data caching is effective in mitigating the associated overhead. HCSR also shows a significant DRAM advantage. Our estimates prove that its performance for this 12
Figure 9: Number of matrices where the given format outperforms all others (SpacemiT K1).
Table 1: STREAM benchmark results for SpacemiT K1 (top) and SpacemiT K3 (bottom).
K1 MB/s × 8 cores
K1 MB/s
Copy Scale Add Triad
L1
Scalar L2 DRAM
L1
RVV L2
DRAM
L1
Scalar L2 DRAM
L1
RVV L2
DRAM
5121 2432 3965 3293
27906 10014 13836 12056
4846 4909 6782 6711
27351 27906 20462 20261
5832 5789 5680 5663
40966 19454 31717 26346
55813 20028 27672 24112
38770 39268 54252 53687
54702 55813 40925 40523
5832 5789 5680 5663
L1
RVV L2
DRAM
129659 122714 171086 169330
99391 104715 87378 91309
19200 19474 19858 18729
5752 6824 6938 6955
K3 MB/s × 8 cores
K3 MB/s
Copy Scale Add Triad
L1
Scalar L2 DRAM
L1
RVV L2
DRAM
L1
13554 9874 14810 14810
53374 54600 48687 48472
16207 15339 21386 21166
49695 52358 43689 45655
19200 19474 19858 18729
108433 78988 118482 118482
19290 19636 19681 18686
5752 6824 6938 6955
matrix is limited only by loading the nonzeros and index array. This is a strong indication of the algorithm’s efficiency for SpMV. Overall, the architectural changes introduced in the SpacemiT K3 have a substantial impact on SpMV performance across various sparse matrix formats, enabling a severalfold reduction in execution time for a broad range of sparse matrices, and likely for virtually all of them.
Scalar L2 DRAM 106749 109200 97374 96944
19290 19636 19681 18686
access and, consequently, the efficiency of processor cache utilization. Selecting the best matrix storage format is a non-trivial task. The decision may depend on subtle features of the matrix portrait, as well as the characteristics of the host machine. Therefore, automatic format selection for sparse matrices is of practical use. This study addresses the following key questions: which specific matrix parameters influence the selection of the best storage format? Are they the same for different storage formats? Is it possible to identify a set of matrix profile characteristics that allow a clear choice of one format or another without the use of a complex machine learning model?
5. Machine learning-based automatic format selection Experimental results confirmed that SpMV execution time varies significantly depending on the matrix storage format and its characteristics. The efficiency of a particular format is determined by the matrix portrait. It influences the nature of memory 13
Figure 10: SpMV speedup for various sparse formats relative to scalar CSR (SpacemiT K3, double precision).
Figure 11: Distribution of SpMV speedup for various sparse formats relative to scalar CSR (SpacemiT K3, double precision).
elements in rows (R), columns (C), tiles (T), row blocks (RB), and column blocks (CB), and a number of other features. For each distribution, the following characteristics were taken: sample mean, variance, standard deviation, minimum and maximum values, the number of nonzero values, the Gini index, and the p-ratio. The latter characteristic is the minimum number p in the range [0, 1] such that the largest elements of the sample, constituting a fraction p of the total number of elements, have a sum that is no less than a fraction 1− p of the sum of all elements in the sample. The following features were also considered:
5.1. Model and feature selection In this paper, we implemented several algorithms for automatically selecting a matrix format based on its portrait to achieve the shortest SpMV execution time. The implementation was based on ideas from the WISE framework [34]. The machine learning models used were random forest and gradient boosting of decision trees for classification and regression. The classification models directly determined the best format. The regression models for each format predicted the ratio of SpMV execution time in a given format to SpMV execution time in the CSR format. The format with the smallest value of this ratio was then selected as the best. For each sparse matrix, a feature vector was calculated and fed to the machine learning model. To calculate the features, the matrix was divided into approximately equal-sized blocks (2048 segments along both rows and columns). The basic features were the number of rows, the number of columns and nonzero elements, the distribution characteristics of the number of nonzero
• uniqR and uniqC are the average counts of distinct row and column indices per block, averaged over all blocks; • GrX_uniqR and GrX_uniqC are similar to uniqR and uniqC, except that they operate on groups of X consecutive rows (columns) rather than on individual rows or columns; • potReuseR and potReuseC are the number of blocks con14
Figure 12: SpMV speedup for various sparse formats relative to scalar CSR (SpacemiT K3, single precision).
Figure 13: Distribution of SpMV speedup for various sparse formats relative to scalar CSR (SpacemiT K3, single precision).
taining elements from a specific row (column), averaged over all rows (columns); • GrX_potReuseR and GrX_potReuseC are defined similarly, except that they operate on groups of X rows (columns) rather than individual rows (columns). The corresponding averages are computed over the total number of row groups and column groups, respectively. The values of X were 4, 8, 16, 32, and 64. The distribution characteristics reflect the balancing of computations during row-parallelization, the specifics of accessing elements of the b vector, and the locality of accessing elements in different blocks. Features from the last group reflect the locality of data access in caches at different levels. All implemented formats were used for training, and for formats with parameters, several parameter combinations from a fixed set were evaluated. The dataset included 121 matrices from the SuiteSparse Matrix Collection used in other experiments,
as well as 600 R-MAT matrices with various parameters [13]. Experimental data obtained on both SpacemiT K1 and SpacemiT K3 boards, running in 8 threads, were used to train the models. The training dataset was a random sample comprising 80% of the entire dataset. Algorithms were tested only on matrices from the SuiteSparse collection. The efficiency of format selection was assessed as the speedup achieved when using the selected format in comparison with the CSR format. 5.2. Experimental Results The results are presented in fig. 15 and fig. 16. Relative speedup is shown only for the machine learning methods that demonstrated the best results. For both K1 and K3 platforms, this is RandomForestRegressor. Using the model-predicted format for SpMV instead of scalar CSR yields an average speedup of 1.4×–1.5× on the SpacemiT K1 processor, and 1.7× on the SpacemiT K3 processor for single and double precision. In many cases, speedups
15
Figure 14: Number of matrices where the given format outperforms all others (SpacemiT K3).
Table 2: SpMV performance metrics on SpacemiT K1 (left) and SpacemiT K3 (right) for matrix spal_004.
K1
K3
Metric
CSR
Sell-C-σ
HCSR
CSR
Sell-C-σ
HCSR
Cycles (all cores), million Instructions, million L1D-load-misses, million Stalled-cycles, million IPC Time, ms Effective bandwidth, GB/s
2484.9 78.4 7.6 2387.5 0.03 226.79 4.1
2221.8 113.5 5.7 2099.7 0.05 195.05 4.7
689.6 209.4 2.9 522.5 0.30 86.44 10.7
960.1 74.3 17.2 943.5 0.08 65.02 14.2
840.4 109.8 5.8 810.7 0.13 51.90 17.8
350.0 208.0 0.7 320.1 0.59 32.26 28.6
of 2.0×–6.0× are achieved. In some cases, the selected format turns out to be slower than CSR, which occurs more often on SpacemiT K1 than on SpacemiT K3. The accuracy of format selection can be estimated by the loss under best (LUB), which is the ratio of the speedup from the optimal format to the speedup from the selected format. On K1 and K3, the RandomForestClassifier and RandomForestRegressor methods showed approximately the same speedups relative to CSR, but the classification model’s maximum LUB was significantly higher. This indicates that this method is less stable and more prone to choosing a format that is far from optimal. Therefore, the regression model was preferred. To improve the accuracy of format selection, hyperparameters for the machine learning methods were tuned. For RandomForest, these were num_estimators, max_depth, min_samples_leaf, min_samples_split, and max_samples. The hyperparameter selection criterion was minimizing the maximum LUB across all matrices. As a result, we achieved a maximum LUB within 1.2–1.4 in all cases. However, the resulting models proved to be sensitive to the data: minor adjustments to the experimental results led to a significant deterioration in
the accuracy of format selection in the worst case. On K3, for single precision, the LUB is 1.03 on average and 2.9 in the worst case, and for double precision – 1.07 on average and 2 in the worst case. On K1, for single precision, the LUB is 1.03 on average and 1.8 in the worst case, and for double precision – 1.09 on average and 3 in the worst case. In all cases where a large difference is observed, the HCSR format is predicted, but the optimal format turns out to be different. For the formats that demonstrated the best performance, we analyzed which matrix features had the greatest impact on SpMV efficiency. For each format, a numeric vector of feature importance was obtained from a random forest regression model trained exclusively on the experimental results for that format. For each feature, the higher the number, the more important the feature is; all numbers sum to 1.0. The most important features for each format are presented in Tables 3 and 4, separately for SpacemiT K1 and SpacemiT K3, for double and single precision. For some features, it was possible to determine the ranges of values in which the highest performance is achieved. In such cases, the ranges are also provided. 16
Table 3: The most important matrix portrait features for each format. SpacemiT K1.
Sparse format
Double precision
Single precision
CSRvec
• C-distribution, p-ratio • CB-distribution, min • RB-distribution, p-ratio • C-distribution, variance
• R-distribution, p-ratio • R-distribution, Gini index • C-distribution, p-ratio • CB-distribution, min
CSR5
• R-distribution, p-ratio < 0.4 • C-distribution, p-ratio < 0.4
• R-distribution, p-ratio < 0.4 • RB-distribution, p-ratio < 0.4 • RB-distribution, Gini index • C-distribution, p-ratio
CVR
• R-distribution, p-ratio < 0.4 • C-distribution, p-ratio < 0.4
• R-distribution, p-ratio < 0.4 • RB-distribution, p-ratio < 0.4 • C-distribution, p-ratio < 0.4 • RB-distribution, Gini index • C-distribution, max
Sell-C-σ
• R-distribution, st. deviation < 100 • Gr32_potReuseR • Gr64_potReuseC • Gr4_uniqC • RB-distribution, max
• R-distribution, variance < 10000 • R-distribution, max < 100 • R-distribution, p-ratio • R-distribution, Gini index
VHCC
• Gr32_potReuseR • Gr64_potReuseC • R-distribution, variance
• Gr64_potReuseR • Gr4_uniqC • Gr64_uniqR • Gr16_uniqC
VNEC
• Gr32_potReuseR • Gr64_potReuseC • R-distribution, variance
• R-distribution, p-ratio • RB-distribution, p-ratio • RB-distribution, Gini index • C-distribution, p-ratio
HCSR
• R-distribution, p-ratio < 0.4 • C-distribution, p-ratio < 0.4 • potReuseR
• Gr8_uniqR • R-distribution, st. deviation • Gr32_uniqR • Gr16_potReuseC • Gr64_uniqR • Gr64_potReuseR
17
Table 4: The most important matrix portrait features for each format. SpacemiT K3.
Sparse format
Double precision
Single precision
CSRvec
• Gr16_potReuseR • R-distribution, variance • Gr8_potReuseC
• Gr8_uniqR • uniqC • Gr32_potReuseR • R-distribution, mean
CSR5
• R-distribution, Gini index > 0.2 • R-distribution, p-ratio < 0.4 • C-distribution, p-ratio
• R-distribution, Gini index > 0.3 • R-distribution, p-ratio < 0.4 • C-distribution, p-ratio
CVR
• R-distribution, p-ratio < 0.4 • RB-distribution, p-ratio < 0.4 • R-distribution, variance
• R-distribution, p-ratio • R-distribution, Gini index • RB-distribution, Gini index • C-distribution, p-ratio • C-distribution, max
Sell-C-σ
• R-distribution, Gini index < 0.3 • R-distribution, variance < 10000
• R-distribution, p-ratio > 0.4 • R-distribution, variance < 10000 • RB-distribution, p-ratio
VHCC
• R-distribution, variance > 100 • C-distribution, max < 100000 • Gr64_potReuseC • potReuseC
• R-distribution, Gini index • R-distribution, p-ratio • C-distribution, p-ratio • CB-distribution, max
VNEC
• RB-distribution, p-ratio < 0.4 • RB-distribution, min > 100 • R-distribution, p-ratio • CB-distribution, min
• RB-distribution, p-ratio • R-distribution, p-ratio • C-distribution, max • C-distribution, p-ratio
HCSR
• R-distribution, variance • RB-distribution, Gini index • C-distribution, variance
• Gr8_uniqR • T-distribution, p-ratio • Number of rows • C-distribution, max
18
Figure 15: SpMV operation speedup relative to scalar CSR when using the automatically chosen format (crosses) and the best of experiments (dots). SpacemiT K1, 8 cores
Figure 16: SpMV operation speedup relative to scalar CSR when using the automatically chosen format (crosses) and the best of experiments (dots). SpacemiT K3, 8 cores
Based on the feature importance analysis, the following conclusions can be drawn:
irregular matrices, consistent with the concepts of the formats.
1. Significant differences in results are observed between K1 and K3, as well as between single and double precision. This reflects differences in the machine microarchitecture when using data types of different lengths. The results on K3 may be more realistic for future machines that will also implement out-of-order instruction execution.
4. For the SELL-C-σ format, the best performance is achieved when the spread of the number of nonzero elements in rows is small. This implies low variance, a Gini index close to 1, and a p-ratio close to 0.5. 5. VHCC also shows the best results on irregular matrices. However, less common features, such as the distribution of the number of nonzero elements in rows and cache locality features, are also important.
2. It is typical that many formats have three or more features that are considered the most important, but each of them has a negligible importance, less than 0.1. This means that the features are quite complexly interrelated, making it very difficult to draw clear conclusions in such cases.
6. HCSR performance for double precision is determined by p-ratio, i.e., matrix irregularity, while for single precision, locality features are more important. This is observed on both K1 and K3. This may be due to the similar design
3. For the CSR5, CVR, and VNEC formats, many features overlap, and the highlighted areas are characteristic of 19
of the memory subsystem, as well as a bottleneck encountered when switching from double to single precision.
learning models that can select the most appropriate format for a given matrix structure. Additionally, we identified which structural properties of matrices influence the suitability of each format. We hope that our results will be useful to other researchers when adapting algorithms to the RISC-V architecture. In future work, we plan to focus on extending the range of supported sparse operations, as well as integrating our developments into iterative solvers for sparse linear systems.
An analysis of the influence of matrix features suggests that for many formats, features corresponding to the matrix types for which they were originally designed were significant. This confirms the adequacy of the model. However, it is difficult to trace the relationships between features in more detail. It is not yet possible to define a set of simple rules for selecting the optimal format when calling the SpMV function; a more complex procedure is required. The currently developed functionality for automatic selection of the optimal format can be used as an auxiliary tool, offering a fairly good, but not the best, solution.
Declaration of Generative AI and AI-assisted technologies in the writing process During the preparation of this work, the authors used AI tools in order to translate the paper, improve the English language phrasing and proofread the manuscript. After using AI tools, the authors reviewed and edited the manuscript and take full responsibility for the content of the publication.
6. Conclusion Despite numerous efforts by the research community, many algorithms operating on sparse matrices still fail to achieve even tens of percent of the peak performance of modern computing systems. SpMV is a prominent representative of memory-bound algorithms, combining several factors that prevent efficient utilization of processor capabilities. First, its arithmetic intensity is low, since we perform only two floating-point operations while loading two floating-point numbers and an integer index from memory. Second, the irregular sparsity pattern leads to numerous cache misses and makes memory access remarkably inefficient. Third, the irregular distribution of nonzero entries may cause load imbalance in parallel execution. Many of these factors are inherent to the nature of sparse matrices and can hardly be eliminated entirely; nevertheless, developing new data structures and efficient implementations of the algorithm for novel architectures, which can accelerate computations at least to some extent, has clear practical value. This work is a step in this direction. We have proposed a new format, HCSR, which is not only sufficiently simple in its design, inheriting numerous advantages of standard formats, but also improves memory access efficiency for a wide range of sparse matrices. Experiments demonstrated that the results of the baseline SpMV implementation in CSR on RISC-V are consistent with those reported by other researchers and can be considered a fair reference. Based on this, we observed an average speedup of 1.6× when using HCSR compared to the best CSR implementation. Furthermore, we have implemented support for nine popular sparse formats for the SpMV operation in our publicly available open-source library RVVLASparse and performed a detailed performance comparison of SpMV in different formats on two generations of RISC-V devices – SpacemiT K1 and SpacemiT K3. Particularly noteworthy are the changes we observed on the new K3 boards. The presence of an out-of-order processor enabled a severalfold acceleration of computations, which is not observed when working with dense matrices. Experiments show that there is a group of sparse formats that dominate others on the vast majority of matrices. At the same time, selecting the most suitable format requires significant engineering effort. We adapted the methodology developed by the authors of WISE to our implementation and trained machine
Acknowledgements The project is supported by the Lobachevsky University academic excellence program “Priority-2030”. The authors acknowledge the use of computational resources provided by the University (Lobachevsky Supercomputer). References [1] Ahmad, M., et al., 2024. Elegante: A machine learningbased threads configuration tool for spmv computations on shared memory architecture. Information 15, 685. [2] Bell, N., Garland, M., 2009. Implementing sparse matrixvector multiplication on throughput-oriented processors, in: Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, pp. 1–11. [3] Bian, H., Huang, J., Dong, R., Guo, Y., Liu, L., Huang, D., Wang, X., 2021. A simple and efficient storage format for simd-accelerated spmv. Cluster Computing 24, 3431– 3448. [4] Brown, N., 2024. RISC-V for HPC: Where we are and where we need to go. arXiv preprint arXiv:2406.12398 . [5] Brown, N., 2025. Is RISC-V ready for high performance computing? an evaluation of the sophon sg2044, in: Proceedings of the SC’25 Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1703–1711. [6] Chen, S., et al., 2022. Adaptive hybrid storage format for sparse matrix–vector multiplication on multi-core simd cpus. Applied Sciences 12, 9812. [7] Davis, T.A., Hu, Y., 2011. The university of florida sparse matrix collection. ACM Transactions on Mathematical Software (TOMS) 38, 1–25. 20
[8] Diehl, P., Syskakis, P., Daiß, G., Brandt, S.R., Kheirkhahan, A., Singanaboina, S.Y., Kaiser, H., et al., 2024. Preparing for HPC on RISC-V: examining vectorization and distributed performance of an astrophysics application with hpx and kokkos, in: SC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE. pp. 1656–1665.
[20] Monakov, A., Lokhmotov, A., Avetisyan, A., 2010. Automatically tuning sparse matrix-vector multiplication for gpu architectures, in: International Conference on High-Performance Embedded Architectures and Compilers, Springer, Berlin, Heidelberg. pp. 111–125. [21] Olas, T., Szustak, L., Wyrzykowski, R., Olas, M., Lapegna, M., 2025. Advances in adapting memory-bound cfd computations to RISC-V multicore architecture, in: International Conference on Computational Science, Springer Nature, Cham. pp. 151–166.
[9] Du, Z., et al., 2022. Alphasparse: Generating high performance spmv codes directly from sparse matrices, in: SC22: International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE. pp. 1–15. [10] Gao, J., et al., 2024. A systematic literature survey of sparse matrix-vector multiplication. arXiv preprint arXiv:2404.06047 .
[22] Olas, T., Wyrzykowski, R., Olas, M., Palkowski, M., Gruzewski, M., 2026. Towards the efficient use of RISC-V architecture in scientific computation. Journal of Computational Science , 102853.
[11] Gómez, C., Mantovani, F., Focht, E., Casas, M., 2021. Efficiently running spmv on long vector architectures, in: Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 292– 303.
[23] Osterno, M., Marcon, C., Silveira, J., Moraes, F., Silveira, J., 2025. Conjunctive merge instruction to accelerate sparse matrix-dense vector multiplication, in: 2025 IFIP/IEEE 33rd International Conference on Very Large Scale Integration (VLSI-SoC), IEEE. pp. 1–5.
[12] Gómez, C., et al., 2020. Optimizing sparse matrix-vector multiplication in NEC SX-Aurora Vector Engine. Technical Report. Barcelona Supercomputing Center.
[24] Pirova, A., Vodeneeva, A., Kovalev, K., Ustinov, A., Kozinov, E., Liniov, A., Meyerov, I., et al., 2026. Performance optimization of BLAS algorithms with band matrices for RISC-V processors. Future Generation Computer Systems 174, 107936.
[13] Khorasani, F., Gupta, R., Bhuyan, L.N., 2015. Scalable simd-efficient graph processing on gpus, in: Proceedings of the 24th International Conference on Parallel Architectures and Compilation Techniques, pp. 39–50.
[25] Puzikova, V., Sokolov, A., Zaytseva, K., 2025. RISC-V acceleration for linear algebra problems: Eigen library enhancements with rvv support, in: International Conference on Parallel Computing Technologies, Springer Nature, Cham. pp. 185–199.
[14] Kincaid, D., Oppe, T., Young, D., 1989. ITPACKV 2D user’s guide. Technical Report. Center for Numerical Analysis, Texas Univ., Austin, TX (USA). DOE/ER/25048-T4; CNA-232. [15] Kourtis, K., et al., 2011. CSX: an extended compression format for spmv on shared memory systems. ACM SIGPLAN Notices 46, 247–256.
[26] Suárez, D., Almeida, F., Blanco, V., 2024. Comprehensive analysis of energy efficiency and performance of arm and RISC-V socs. The Journal of Supercomputing 80, 12771– 12789.
[16] Kozinov, E., Vasiliev, E., Gorshkov, A., Kustikova, V., Maklaev, A., Volokitin, V., Meyerov, I., 2024. Vectorization of gradient boosting of decision trees prediction in the catboost library for RISC-V processors, in: International Conference on Parallel Processing and Applied Mathematics, Springer, Cham. pp. 32–47.
[27] Titopoulos, V., Alexandridis, K., Peltekis, C., Nicopoulos, C., Dimitrakopoulos, G., 2024. IndexMAC: A custom RISC-V vector instruction to accelerate structured-sparse matrix multiplications, in: 2024 Design, Automation & Test in Europe Conference & Exhibition (DATE), IEEE. pp. 1–6.
[17] Kreutzer, M., Hager, G., Wellein, G., Fehske, H., Bishop, A.R., 2014. A unified sparse matrix data format for efficient general sparse matrix-vector multiplication on modern processors with wide simd units. SIAM Journal on Scientific Computing 36, C401–C423.
[28] Tomás, A., Martínez, H., Catalán, S., Siwinska, P., Castelló, A., Casas, M., Quintana-Ortí, E., 2026. Sparse matrix– vector product on RISC-V processors with simd units. Computing 108, 66.
[18] Li, Y., 2020. VBSF: a new storage format for simd sparse matrix–vector multiplication on modern processors. Journal of Supercomputing 76.
[29] Vázquez, F., Fernández, J., Garzón, E., 2011. A new approach for sparse matrix vector product on nvidia gpus. Concurrency and Computation: Practice and Experience 23, 815–826.
[19] Liu, W., Vinter, B., 2015. CSR5: An efficient storage format for cross-platform sparse matrix-vector multiplication, in: Proceedings of the 29th ACM on International Conference on Supercomputing, pp. 339–350.
[30] Volokitin, V., Kozinov, E., Kustikova, V., Liniov, A., Meyerov, I., 2023. Case study for running memory-bound kernels on risc-v cpus, in: International Conference on Parallel Computing Technologies, Springer. pp. 51–65. 21
[31] Xia, T., Fan, Z., Xue, J., Qin, S., Ye, X., Li, W., 2026. RISC-V isa extensions for vectorized unstructured sparse spmm in llm inference, in: 2026 Design, Automation & Test in Europe Conference (DATE), IEEE. pp. 1–7. [32] Xie, B., Zhan, J., Liu, X., Gao, W., Jia, Z., He, X., Zhang, L., 2018. CVR: Efficient vectorization of spmv on x86 processors, in: Proc. of the 2018 International Symposium on Code Generation and Optimization, pp. 149–162. [33] Yan, S., Li, C., Zhang, Y., Zhou, H., 2014. yaspmv: Yet another spmv framework on gpus. ACM SIGPLAN Notices 49, 107–118. [34] Yesil, S., et al., 2023. WISE: Predicting the performance of sparse matrix vector multiplication with machine learning, in: Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, pp. 329–341. [35] Zhao, Y., et al., 2018. Bridging the gap between deep learning and sparse matrix format selection, in: Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 94–108.
22
Appendix A. Test matrices Table A.5: Matrix characteristics ID
Matrix name
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
italy_osm Hardesty3 delaunay_n23 rajat31 patents cit-Patents circuit5M_dc Freescale1 Freescale2 memchip cont11_l cont1_l circuit5M ljournal-2008 delaunay_n21 LargeRegFile kkt_power G3_circuit webbase-1M rgg_n_2_22_s0 indochina-2004 channel-500x100x100-b050 cage15 Delor295K stormG2_1000 ecology1 atmosmodd ASIC_680k NACA0015 web-Google vas_stokes_4M packing-500x100x100-b050 mc2depi watson_2 in-2004 Transport StocF-1465 IMDB soc-Pokec cage14 ss Delor338K vas_stokes_2M Hardesty2 Bump_2911 Stanford_Berkeley amazon0601 af_shell10 nlpkkt80
m
n
nz
6,686,493 8,217,820 8,388,608 4,690,002 3,774,768 3,774,768 3,523,317 3,428,755 2,999,349 2,707,524 1,468,599 1,918,399 5,558,326 5,363,260 2,097,152 2,111,154 2,063,494 1,585,478 1,000,005 4,194,304 7,414,866 4,802,000 5,154,859 295,734 528,185 1,000,000 1,270,432 682,862 1,039,183 916,428 4,382,246 2,145,852 525,825 352,013 1,382,908 1,602,111 1,465,137 428,440 1,632,803 1,505,785 1,652,680 343,236 2,146,677 929,901 2,911,419 683,446 403,394 1,508,065 1,062,400
6,686,493 7,591,564 8,388,608 4,690,002 3,774,768 3,774,768 3,523,317 3,428,755 2,999,349 2,707,524 1,961,394 1,921,596 5,558,326 5,363,260 2,097,152 801,374 2,063,494 1,585,478 1,000,005 4,194,304 7,414,866 4,802,000 5,154,859 1,823,928 1,377,306 1,000,000 1,270,432 682,862 1,039,183 916,428 4,382,246 2,145,852 525,825 677,224 1,382,908 1,602,111 1,465,137 896,308 1,632,803 1,505,785 1,652,680 887,058 2,146,677 303,645 2,911,419 683,446 403,394 1,508,065 1,062,400
14,027,956 40,451,632 50,331,568 20,316,253 14,970,767 16,518,948 14,865,409 17,052,626 14,313,235 13,343,948 5,382,999 7,031,999 59,524,291 79,023,142 12,582,816 4,944,201 12,771,361 7,660,826 3,105,536 60,718,396 194,109,311 85,362,744 99,199,551 2,401,323 3,459,881 4,996,000 8,814,880 2,638,997 6,229,636 5,105,039 131,577,616 34,976,486 2,100,225 1,846,391 16,917,053 23,487,281 21,005,389 3,782,463 30,622,564 27,130,349 34,753,577 4,211,599 65,129,037 4,020,731 127,729,899 7,583,376 3,387,388 52,259,885 28,192,672
nz/row
fill-in
2 5 6 4 4 4 4 5 5 5 4 4 11 15 6 2 6 5 3 14 26 18 19 8 7 5 7 4 6 6 30 16 4 5 12 15 14 9 19 18 21 12 30 4 44 11 8 35 27
3.14e-07 6.48e-07 7.15e-07 9.24e-07 1.05e-06 1.16e-06 1.20e-06 1.45e-06 1.59e-06 1.82e-06 1.87e-06 1.91e-06 1.93e-06 2.75e-06 2.86e-06 2.92e-06 3.00e-06 3.05e-06 3.11e-06 3.45e-06 3.53e-06 3.70e-06 3.73e-06 4.45e-06 4.76e-06 5.00e-06 5.46e-06 5.66e-06 5.77e-06 6.08e-06 6.85e-06 7.59e-06 7.60e-06 7.74e-06 8.84e-06 9.15e-06 9.78e-06 9.85e-06 1.15e-05 1.20e-05 1.27e-05 1.38e-05 1.41e-05 1.42e-05 1.51e-05 1.62e-05 2.08e-05 2.30e-05 2.50e-05
Continued on next page 23
Table A.5 – continued from previous page ID
Matrix name
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
Hook_1498 Cube_Coup_dt0 Cube_Coup_dt6 ins2 Stanford web-Stanford vas_stokes_1M NotreDame_actors mac_econ_fwd500 Serena Rucci1 dielFilterV2real Long_Coup_dt6 Flan_1565 ldoor turon_m Emilia_923 ML_Geer bone010 sls gsm_106857 degme Fault_639 PFlow_742 af_2_k101 higgs-twitter dielFilterV3real bundle_adj tp-6 kron_g500-logn20 audikw_1 hollywood-2009 stat96v3 CoupCons3D stat96v2 msdoor inline_1 kron_g500-logn19 Si87H76 ML_Laplace BenElechi1 F1 pwtk halfb Ga41As41H72 troll fcondp2 karted fullb bmw7st_1 gearbox Si41Ge41H72 s4dkt3m2
m
n
nz
1,498,023 2,164,760 2,164,760 309,412 281,903 281,903 1,090,664 392,400 206,500 1,391,349 1,977,885 1,157,456 1,470,152 1,564,794 952,203 189,924 923,136 1,504,002 986,703 1,748,122 589,446 185,501 638,802 742,793 503,625 456,626 1,102,824 513,351 142,752 1,048,576 943,695 1,139,905 33,841 416,800 29,089 415,863 503,712 524,288 240,369 377,002 245,874 343,791 217,918 224,617 268,096 213,453 201,822 46,502 199,187 141,347 153,746 185,639 90,449
1,498,023 2,164,760 2,164,760 309,412 281,903 281,903 1,090,664 127,823 206,500 1,391,349 109,900 1,157,456 1,470,152 1,564,794 952,203 189,924 923,136 1,504,002 986,703 62,729 589,446 659,415 638,802 742,793 503,625 456,626 1,102,824 513,351 1,014,301 1,048,576 943,695 1,139,905 1,113,780 416,800 957,432 415,863 503,712 524,288 240,369 377,002 245,874 343,791 217,918 224,617 268,096 213,453 201,822 133,115 199,187 141,347 153,746 185,639 90,449
59,374,451 124,406,070 124,406,070 2,751,484 2,312,497 2,312,497 34,767,207 1,470,404 1,273,389 64,131,971 7,791,168 48,538,952 84,422,970 114,165,372 42,493,817 1,690,876 40,373,538 110,686,677 47,851,783 6,804,304 21,758,924 8,127,528 27,245,944 37,138,461 17,550,675 14,855,842 89,306,020 20,207,907 11,537,419 89,239,674 77,651,847 113,891,327 3,317,736 17,277,420 2,852,184 19,173,163 36,816,170 43,562,265 10,661,631 27,582,698 13,150,496 26,837,113 11,524,432 12,387,821 18,488,476 11,985,111 11,294,316 1,770,349 11,708,077 7,318,399 9,080,404 15,011,265 3,753,461
nz/row
fill-in
40 57 57 9 8 8 32 4 6 46 4 42 57 73 45 9 44 74 48 4 37 44 43 50 35 33 81 39 81 85 82 100 98 41 98 46 73 83 44 73 53 78 53 55 69 56 56 38 59 52 59 81 41
2.65e-05 2.66e-05 2.66e-05 2.87e-05 2.91e-05 2.91e-05 2.92e-05 2.93e-05 2.99e-05 3.31e-05 3.58e-05 3.62e-05 3.91e-05 4.66e-05 4.69e-05 4.69e-05 4.74e-05 4.89e-05 4.92e-05 6.21e-05 6.27e-05 6.64e-05 6.67e-05 6.73e-05 6.92e-05 7.13e-05 7.34e-05 7.66e-05 7.97e-05 8.11e-05 8.72e-05 8.76e-05 8.81e-05 9.95e-05 1.02e-04 1.11e-04 1.45e-04 1.58e-04 1.84e-04 1.94e-04 2.18e-04 2.27e-04 2.43e-04 2.45e-04 2.57e-04 2.63e-04 2.77e-04 2.86e-04 2.95e-04 3.66e-04 3.84e-04 4.35e-04 4.59e-04
Continued on next page 24
Table A.5 – continued from previous page ID
Matrix name
103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
SiO2 ESOC kron_g500-logn17 torso1 pkustk14 x104 12month1 JP mip1 rail4284 raefsky3 rail2586 crankseg_2 nd24k connectus specular nd12k TSOPF_RS_b2383 spal_004
m
n
nz
nz/row
fill-in
155,331 327,062 131,072 116,158 151,926 108,384 12,471 87,616 66,463 4,284 21,200 2,586 63,838 72,000 512 477,976 36,000 38,120 10,203
155,331 37,830 131,072 116,158 151,926 108,384 872,622 67,320 66,463 1,096,894 21,200 923,269 63,838 72,000 394,792 1,600 36,000 38,120 321,696
11,283,503 6,019,939 10,228,360 8,516,500 14,836,504 8,713,602 22,624,727 13,734,559 10,352,819 11,284,032 1,488,768 8,011,362 14,148,858 28,715,634 1,127,525 7,647,040 14,220,946 16,171,169 46,168,124
73 18 78 73 98 80 1814 157 156 2634 70 3098 222 399 2202 16 395 424 4525
4.68e-04 4.87e-04 5.95e-04 6.31e-04 6.43e-04 7.42e-04 2.08e-03 2.33e-03 2.34e-03 2.40e-03 3.31e-03 3.36e-03 3.47e-03 5.54e-03 5.58e-03 1.00e-02 1.10e-02 1.11e-02 1.41e-02
25