Query: The University of Florida sparse matrix collection

Candidate papers:

abstract: We describe the University of Florida Sparse Matrix Collection, a large and actively growing set of sparse matrices that arise in real applications. The Collection is widely used by the numerical linear algebra community for the development and performance evaluation of sparse matrix algorithms. It allows for robust and repeatable experiments: robust because performance results with artificially generated matrices can be misleading, and repeatable because matrices are curated and made publicly available in many formats. Its matrices cover a wide spectrum of domains, include those arising from problems with underlying 2D or 3D geometry (as structural engineering, computational fluid dynamics, model reduction, electromagnetics, semiconductor devices, thermodynamics, materials, acoustics, computer graphics/vision, robotics/kinematics, and other discretizations) and those that typically do not have such geometry (optimization, circuit simulation, economic and financial modeling, theoretical and quantum chemistry, chemical process simulation, mathematics and statistics, power networks, and other networks and graphs) We provide software for accessing and managing the Collection, from MATLAB#8482; Mathematica#8482; Fortran, and C, as well as an online search capability. Graph visualization of the matrices is provided, and a new multilevel coarsening scheme is proposed to facilitate this task.
author_names: Timothy A Davis

Yifan Hu
title: The university of Florida sparse matrix collection
venue: TOMS
year: 2011

abstract: The SuiteSparse Matrix Collection (formerly known as the University of Florida Sparse Matrix Collection) (Davis Hu, 2011) has grown significantly since its introduction, with newly added matrices representing almost seven times as much data than the entirety of the original Collection. With this growth, searching the Collection for matrices with specific names, structures, and other properties has become increasingly difficult. To make the Collection more accessible to the scientific computing community, we have developed a web application that allows real time search and filtering of the Collection matrices.
author_names: Scott P Kolodziej

Mohsen Mahmoudi Aznaveh

Matthew Bullock

Jarrett David

Timothy A Davis

Matthew Henderson

Yifan Hu

Read Sandstrom
title: The SuiteSparse Matrix Collection Website Interface
venue: J. Open Source Softw.
year: 2019

abstract: Intel announced to launch a Xeon with high latency main memory based on 3D Xpoint in 2018. This paper presents the performance evaluation of sparse matrix kernels on the future supercomputers with high latency main memory such as 3D Xpoint. The authors propose a high throughput evaluation methodology for exhaustive experiments, which use the University of Florida sparse matrix collection and/or LIS (a Library of Iterative Solvers for linear systems) etc. Proposed methodology is very simple to use, highly flexible for environment and high throughput. Latency sensitivity of SpMV is measured based on the proposed methodology with 208 sparse matrices and ten storage formats only in two days, which would take for about ten years by conventional simulators. We got several interesting knowledge about latency sensitive kernels, sparse matrices, storage formats, and preconditioners, etc. We observed notable latency sensitivity in some applications, which are Graph500, HPCG and a part of preconditioners of iterative solvers. We found latency sensitivities of SpMV are high for larger matrices than the capacity of last level cache. This suggests main memory using 3D Xpoint must be combined with large DRAM cache.
author_names: Noboru Tanabe

Toshio Endo
title: Characterizing Memory Latency Sensitivity of Sparse Matrix Kernels
venue: 2018 26th Euromicro International Conference on Parallel, Distributed and Network based Processing (PDP)
year: 2018

abstract: Matrix Depot is a Julia software package that provides easy access to a large and diverse collection of test matrices. Its novelty is threefold. First, it is extensible by the user, and so can be adapted to include the user's own test problems. In doing so it facilitates experimentation and makes it easier to carry out reproducible research. Second, it amalgamates in a single framework two different types of existing matrix collections, comprising parametrized test matrices (including Hansen's set of regularization test problems and Higham's Test Matrix Toolbox) and real life sparse matrix data (giving access to the University of Florida Sparse Matrix Collection) Third, it fully exploits the Julia language. It uses multiple dispatch to help provide a simple interface and, in particular, to allow matrices to be generated in any of the numeric data types supported by the language.
author_names: Weijian Zhang

Nicholas John Higham
title: Matrix Depot: an extensible test matrix collection for Julia
venue: PeerJ Comput. Sci.
year: 2016

abstract: In this paper we present PMORSy a new parallel software package for symmetric sparse matrix ordering on shared memory systems. The NP complete fill in minimization problem is solved by means of multilevel nested dissection algorithm with modifications for vertex separators. Parallel processing is done in a task based fashion with the granularity tuning. We employ threading techniques on shared memory using OpenMP 3.0 technology as opposed to the Message Passing Interface based approach widely used for parallel sparse matrix ordering. Experimental results on symmetric matrices from the University of Florida Sparse Matrix Collection and matrices from finite element analysis of three dimensional strength problems show that our implementation is competitive to the ParMETIS and PT Scotch libraries both in ordering quality and performance. The PMORSy library is publicly available from the Lobachevsky State University Supercomputing Center web site.
author_names: Anna Pirova

Iosif B Meyerov

Evgeniy Kozinov

Sergey Lebedev
title: PMORSy: parallel sparse matrix ordering software for fill in minimization+
venue: Optim. Methods Softw.
year: 2017

abstract: Sparse matrix vector multiplication (SpMV) is an important computational kernel in many applications. For performance improvement, software libraries designated for SpMV computation have been introduced, e.g. MKL library for CPUs and cuSPARSE library for GPUs. However, the computational throughput of these libraries is far below the peak floating point performance offered by hardware platforms, because the efficiency of SpMV kernel is greatly constrained by the limited memory bandwidth and irregular data access patterns. In this work, we propose a data locality aware design framework for FPGA based SpMV acceleration. We first include the hardware constraints in sparse matrix compression at software level to regularize the memory allocation and accesses. Moreover, a distributed architecture composed of processing elements is developed to improve the computation parallelism. We implement the reconfigurable SpMV kernel on Convey HC 2ex and conduct the evaluation by using the University of Florida sparse matrix collection. The experiments demonstrate an average computational efficiency of 48.2% which is a lot better than those of CPU and GPU implementations. Our FPGA based kernel has a comparable runtime as GPU, and achieves 2.1x reduction than CPU. Moreover, our design obtains substantial saving in energy consumption, say, 9.3x and 5.6x better than the implementations on CPU and GPU, respectively.
author_names: Sicheng Li

Yandan Wang

Wujie Wen

Yu Wang

Yiran Chen

Hai Helen Li
title: A data locality aware design framework for reconfigurable sparse matrix vector multiplication kernel
venue: 2016 IEEE/ACM International Conference on Computer Aided Design (ICCAD)
year: 2016

abstract: Many recent studies suggest that energy efficiency should be placed as a primary design goal on par with the performance in building both the hardware and the software. As a primary step toward finding a good compromise between these two conflicting design goals, first we need to have a deep understanding about the performance and the energy of different application kernels. In this paper, we focus on evaluating the energy efficiency of the Sparse Matrix Vector Multiplication (SpMV) a very challenging kernel given its irregular aspect both in terms of memory access and control flow. In the present work, we consider the SpMV kernel under four different sparse formats (COO, CSR, ELL, and HYB) on GPU. Our experimental results obtained by using real world sparse matrices from the University of Florida collection on an NVIDIA Maxwell GPU (GTX 980Ti) show that there is no universal best sparse format in terms of energy efficiency. Furthermore, we identified some sparsity characteristics which are related to the energy efficiency of different sparse formats.
author_names: Akrem Benatia

Weixing Ji

Yizhuo Wang

Feng Shi
title: Energy evaluation of Sparse Matrix Vector Multiplication on GPU
venue: 2016 Seventh International Green and Sustainable Computing Conference (IGSC)
year: 2016

abstract: It is well known that the sparse matrix vector product Ax requires two floating point operations per each non zero element in A. However, when computing the number of flops for the symmetric sparse matrix vector product (Sym SpMV) some subtleties should be considered because the number of non zero (nnz) elements reported on symmetric sparse matrices varies from one research work to another. In general, matrices are chosen from the University of Florida Sparse Matrix Collection and for symmetric matrices, in this collection, the nnz elements in the profile differs from the nnz elements stored in file. Therefore, we can find two different works using similar algorithms and reporting different nnz elements for the same matrix because one uses the nnz elements found in the matrix profile and the other reports the nnz elements in store (the lower triangular matrix) which is misleading. If symmetry is exploited, computing four floating point operations per each off diagonal non zero element is correct in a symmetric matrix but it is not accurate to count four floating point operations on diagonal non zero coefficients because they only produce one or two floating point operations per nonzero element depending on the handling of the diagonal. Furthermore, there are symmetric matrices whose diagonal is not dense or all elements are zero. We evaluate three algorithms proposed in the literature to compute the symmetric SpMV and observe their behavior on a small set of different symmetric sparse matrix types. Based on our experimental results we propose a more accurate way to measure flops when dealing with the symmetric sparse matrix vector product. Finally, we show that an algorithm can run faster than another and produce less flops than the slower one.
author_names: Euripides Montagne

Edward Aymerich
title: Let's agree on computing flops for the symmetric sparse matrix vector product
venue: SpringSim
year: 2016

abstract: The sparse matrix partitioning problem arises when minimizing communication in parallel sparse matrix vector multiplications. Since the problem is NP hard, heuristics are usually employed to find solutions. Here, we present a purely combinatorial branch and bound method for computing optimal bipartitionings of sparse matrices, in the sense that they have the lowest communication volume out of all possible bipartitionings obeying a certain load balance constraint. The method is based on a way of partitioning similar to the recently proposed medium grain heuristic, which reduces the number of solutions to be considered in the branch and bound method.We applied the proposed optimal bipartitioner to find the optimal communication volume of all matrices of the University of Florida sparse matrix collection with 1000 nonzeros or less. For 85% of the matrices, an optimal bipartitioning was found within a single day of computation and for 58% even within a second. We also present optimal results for selected larger matrices, up to 129,042 nonzeros. The optimal bipartitionings and corresponding communication volumes are made publicly available in a benchmark collection. We present an exact branch and bound algorithm for sparse matrix bipartitioning.Rows and columns are partitioned instead of nonzeros to reduce computation time.For 85% of a test set of small matrices, an optimal bipartitioning was found.The largest matrix that was optimally bipartitioned has 129,042 nonzeros.A benchmark collection of optimal results will be made publicly available.
author_names: Daniel Maria Pelt

Rob H Bisseling
title: An exact algorithm for sparse matrix bipartitioning
venue: J. Parallel Distributed Comput.
year: 2015

abstract: Sparse Matrix Matrix multiplication (SpMM) is a fundamental operation over irregular data, which is widely used in graph algorithms, such as finding minimum spanning trees and shortest paths. In this work, we present a hybrid CPU and GPU based parallel SpMM algorithm to improve the performance of SpMM. First, we improve data locality by element wise multiplication. Second, we utilize the ordered property of row indices for partial sorting instead of full sorting of all triples according to row and column indices. Finally, through a hybrid CPUGPU approach using two level pipelining technique, our algorithm is able to better exploit a heterogeneous system. Compared with the state of the art SpMM methods in cuSPARSE and CUSP libraries, our approach achieves an average of 1.6x and 2.9x speedup separately on the nine representative matrices from University of Florida sparse matrix collection. INDEX WORDS: Sparse matrix matrix multiplication, Data locality, Pipelining, GPU OPTIMIZING SPARSE MATRIX MATRIX MULTIPLICATION ON A HETEROGENEOUS CPU GPU PLATFORM
author_names: Xiaolong Wu
title: Optimizing Sparse Matrix Matrix Multiplication on a Heterogeneous CPU GPU Platform
year: 2015