Log in

Relevant bibliographies by topics / Sparse Matrix Vector Multiplication / Journal articles

To see the other types of publications on this topic, follow the link: Sparse Matrix Vector Multiplication.

Journal articles on the topic 'Sparse Matrix Vector Multiplication'

Author: Grafiati

Published: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Sparse Matrix Vector Multiplication.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Tao, Yuan, Yangdong Deng, Shuai Mu, Zhenzhong Zhang, Mingfa Zhu, Limin Xiao, and Li Ruan. "GPU accelerated sparse matrix-vector multiplication and sparse matrix-transpose vector multiplication." Concurrency and Computation: Practice and Experience 27, no. 14 (October 7, 2014): 3771–89. http://dx.doi.org/10.1002/cpe.3415.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Filippone, Salvatore, Valeria Cardellini, Davide Barbieri, and Alessandro Fanfarillo. "Sparse Matrix-Vector Multiplication on GPGPUs." ACM Transactions on Mathematical Software 43, no. 4 (March 23, 2017): 1–49. http://dx.doi.org/10.1145/3017994.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

ERHEL, JOCELYNE. "SPARSE MATRIX MULTIPLICATION ON VECTOR COMPUTERS." International Journal of High Speed Computing 02, no. 02 (June 1990): 101–16. http://dx.doi.org/10.1142/s012905339000008x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Haque, Sardar Anisul, Shahadat Hossain, and M. Moreno Maza. "Cache friendly sparse matrix-vector multiplication." ACM Communications in Computer Algebra 44, no. 3/4 (January 28, 2011): 111–12. http://dx.doi.org/10.1145/1940475.1940490.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Bienz, Amanda, William D. Gropp, and Luke N. Olson. "Node aware sparse matrix–vector multiplication." Journal of Parallel and Distributed Computing 130 (August 2019): 166–78. http://dx.doi.org/10.1016/j.jpdc.2019.03.016.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Heath, L. S., C. J. Ribbens, and S. V. Pemmaraju. "Processor-efficient sparse matrix-vector multiplication." Computers & Mathematics with Applications 48, no. 3-4 (August 2004): 589–608. http://dx.doi.org/10.1016/j.camwa.2003.06.009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Yang, Xintian, Srinivasan Parthasarathy, and P. Sadayappan. "Fast sparse matrix-vector multiplication on GPUs." Proceedings of the VLDB Endowment 4, no. 4 (January 2011): 231–42. http://dx.doi.org/10.14778/1938545.1938548.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Romero, L. F., and E. L. Zapata. "Data distributions for sparse matrix vector multiplication." Parallel Computing 21, no. 4 (April 1995): 583–605. http://dx.doi.org/10.1016/0167-8191(94)00087-q.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Zardoshti, Pantea, Farshad Khunjush, and Hamid Sarbazi-Azad. "Adaptive sparse matrix representation for efficient matrix–vector multiplication." Journal of Supercomputing 72, no. 9 (November 28, 2015): 3366–86. http://dx.doi.org/10.1007/s11227-015-1571-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Yzelman, A. N., and Rob H. Bisseling. "Cache-Oblivious Sparse Matrix–Vector Multiplication by Using Sparse Matrix Partitioning Methods." SIAM Journal on Scientific Computing 31, no. 4 (January 2009): 3128–54. http://dx.doi.org/10.1137/080733243.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Sun, C. C., J. Götze, H. Y. Jheng, and S. J. Ruan. "Sparse matrix-vector multiplication on network-on-chip." Advances in Radio Science 8 (December 22, 2010): 289–94. http://dx.doi.org/10.5194/ars-8-289-2010.

Full text

Abstract:

Abstract. In this paper, we present an idea for performing matrix-vector multiplication by using Network-on-Chip (NoC) architecture. In traditional IC design on-chip communications have been designed with dedicated point-to-point interconnections. Therefore, regular local data transfer is the major concept of many parallel implementations. However, when dealing with the parallel implementation of sparse matrix-vector multiplication (SMVM), which is the main step of all iterative algorithms for solving systems of linear equation, the required data transfers depend on the sparsity structure of the matrix and can be extremely irregular. Using the NoC architecture makes it possible to deal with arbitrary structure of the data transfers; i.e. with the irregular structure of the sparse matrices. So far, we have already implemented the proposed SMVM-NoC architecture with the size 4×4 and 5×5 in IEEE 754 single float point precision using FPGA.

APA, Harvard, Vancouver, ISO, and other styles

12

Isupov, Konstantin. "Multiple-precision sparse matrix–vector multiplication on GPUs." Journal of Computational Science 61 (May 2022): 101609. http://dx.doi.org/10.1016/j.jocs.2022.101609.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Zou, Dan, Yong Dou, Song Guo, and Shice Ni. "High performance sparse matrix-vector multiplication on FPGA." IEICE Electronics Express 10, no. 17 (2013): 20130529. http://dx.doi.org/10.1587/elex.10.20130529.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Gao, Jiaquan, Yifei Xia, Renjie Yin, and Guixia He. "Adaptive diagonal sparse matrix-vector multiplication on GPU." Journal of Parallel and Distributed Computing 157 (November 2021): 287–302. http://dx.doi.org/10.1016/j.jpdc.2021.07.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Yzelman, A. N., and Rob H. Bisseling. "Two-dimensional cache-oblivious sparse matrix–vector multiplication." Parallel Computing 37, no. 12 (December 2011): 806–19. http://dx.doi.org/10.1016/j.parco.2011.08.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Yilmaz, Buse, Bariş Aktemur, MaríA J. Garzarán, Sam Kamin, and Furkan Kiraç. "Autotuning Runtime Specialization for Sparse Matrix-Vector Multiplication." ACM Transactions on Architecture and Code Optimization 13, no. 1 (April 5, 2016): 1–26. http://dx.doi.org/10.1145/2851500.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

MUKADDES, ABUL MUKID MOHAMMAD, MASAO OGINO, and RYUJI SHIOYA. "PERFORMANCE EVALUATION OF DOMAIN DECOMPOSITION METHOD WITH SPARSE MATRIX STORAGE SCHEMES IN MODERN SUPERCOMPUTER." International Journal of Computational Methods 11, supp01 (November 2014): 1344007. http://dx.doi.org/10.1142/s0219876213440076.

Full text

Abstract:

The use of proper data structures with corresponding algorithms is critical to achieve good performance in scientific computing. The need of sparse matrix vector multiplication in each iteration of the iterative domain decomposition method has led to implementation of a variety of sparse matrix storage formats. Many storage formats have been presented to represent sparse matrix and integrated in the method. In this paper, the storage efficiency of those sparse matrix storage formats are evaluated and compared. The performance results of sparse matrix vector multiplication used in the domain decomposition method is considered. Based on our experiments in the FX10 supercomputer system, some useful conclusions that can serve as guidelines for the optimization of domain decomposition method are extracted.

APA, Harvard, Vancouver, ISO, and other styles

18

Liu, Sheng, Yasong Cao, and Shuwei Sun. "Mapping and Optimization Method of SpMV on Multi-DSP Accelerator." Electronics 11, no. 22 (November 11, 2022): 3699. http://dx.doi.org/10.3390/electronics11223699.

Full text

Abstract:

Sparse matrix-vector multiplication (SpMV) solves the product of a sparse matrix and dense vector, and the sparseness of a sparse matrix is often more than 90%. Usually, the sparse matrix is compressed to save storage resources, but this causes irregular access to dense vectors in the algorithm, which takes a lot of time and degrades the SpMV performance of the system. In this study, we design a dedicated channel in the DMA to implement an indirect memory access process to speed up the SpMV operation. On this basis, we propose six SpMV algorithm schemes and map them to optimize the performance of SpMV. The results show that the M processor’s SpMV performance reached 6.88 GFLOPS. Besides, the average performance of the HPCG benchmark is 2.8 GFLOPS.

APA, Harvard, Vancouver, ISO, and other styles

19

Jao, Nicholas, Akshay Krishna Ramanathan, John Sampson, and Vijaykrishnan Narayanan. "Sparse Vector-Matrix Multiplication Acceleration in Diode-Selected Crossbars." IEEE Transactions on Very Large Scale Integration (VLSI) Systems 29, no. 12 (December 2021): 2186–96. http://dx.doi.org/10.1109/tvlsi.2021.3114186.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Kamin, Sam, María Jesús Garzarán, Barış Aktemur, Danqing Xu, Buse Yılmaz, and Zhongbo Chen. "Optimization by runtime specialization for sparse matrix-vector multiplication." ACM SIGPLAN Notices 50, no. 3 (May 12, 2015): 93–102. http://dx.doi.org/10.1145/2775053.2658773.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Fernandez, D. M., D. Giannacopoulos, and W. J. Gross. "Efficient Multicore Sparse Matrix-Vector Multiplication for FE Electromagnetics." IEEE Transactions on Magnetics 45, no. 3 (March 2009): 1392–95. http://dx.doi.org/10.1109/tmag.2009.2012640.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Shantharam, Manu, Anirban Chatterjee, and Padma Raghavan. "Exploiting dense substructures for fast sparse matrix vector multiplication." International Journal of High Performance Computing Applications 25, no. 3 (August 2011): 328–41. http://dx.doi.org/10.1177/1094342011414748.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Gao, Jiaquan, Panpan Qi, and Guixia He. "Efficient CSR-Based Sparse Matrix-Vector Multiplication on GPU." Mathematical Problems in Engineering 2016 (2016): 1–14. http://dx.doi.org/10.1155/2016/4596943.

Full text

Abstract:

Sparse matrix-vector multiplication (SpMV) is an important operation in computational science and needs be accelerated because it often represents the dominant cost in many widely used iterative methods and eigenvalue problems. We achieve this objective by proposing a novel SpMV algorithm based on the compressed sparse row (CSR) on the GPU. Our method dynamically assigns different numbers of rows to each thread block and executes different optimization implementations on the basis of the number of rows it involves for each block. The process of accesses to the CSR arrays is fully coalesced, and the GPU’s DRAM bandwidth is efficiently utilized by loading data into the shared memory, which alleviates the bottleneck of many existing CSR-based algorithms (i.e., CSR-scalar and CSR-vector). Test results on C2050 and K20c GPUs show that our method outperforms a perfect-CSR algorithm that inspires our work, the vendor tuned CUSPARSE V6.5 and CUSP V0.5.1, and three popular algorithms clSpMV, CSR5, and CSR-Adaptive.

APA, Harvard, Vancouver, ISO, and other styles

24

Maggioni, Marco, and Tanya Berger-Wolf. "Optimization techniques for sparse matrix–vector multiplication on GPUs." Journal of Parallel and Distributed Computing 93-94 (July 2016): 66–86. http://dx.doi.org/10.1016/j.jpdc.2016.03.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Geus, Roman, and Stefan Röllin. "Towards a fast parallel sparse symmetric matrix–vector multiplication." Parallel Computing 27, no. 7 (June 2001): 883–96. http://dx.doi.org/10.1016/s0167-8191(01)00073-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Zhang, Jilin, Enyi Liu, Jian Wan, Yongjian Ren, Miao Yue, and Jue Wang. "Implementing Sparse Matrix-Vector Multiplication with QCSR on GPU." Applied Mathematics & Information Sciences 7, no. 2 (March 1, 2013): 473–82. http://dx.doi.org/10.12785/amis/070207.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Feng, Xiaowen, Hai Jin, Ran Zheng, Zhiyuan Shao, and Lei Zhu. "A segment-based sparse matrix-vector multiplication on CUDA." Concurrency and Computation: Practice and Experience 26, no. 1 (December 7, 2012): 271–86. http://dx.doi.org/10.1002/cpe.2978.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Neves, Samuel, and Filipe Araujo. "Straight-line programs for fast sparse matrix-vector multiplication." Concurrency and Computation: Practice and Experience 27, no. 13 (January 28, 2014): 3245–61. http://dx.doi.org/10.1002/cpe.3211.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Nastea, Sorin G., Ophir Frieder, and Tarek El-Ghazawi. "Load-Balanced Sparse Matrix–Vector Multiplication on Parallel Computers." Journal of Parallel and Distributed Computing 46, no. 2 (November 1997): 180–93. http://dx.doi.org/10.1006/jpdc.1997.1361.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

He, Guixia, and Jiaquan Gao. "A Novel CSR-Based Sparse Matrix-Vector Multiplication on GPUs." Mathematical Problems in Engineering 2016 (2016): 1–12. http://dx.doi.org/10.1155/2016/8471283.

Full text

Abstract:

Sparse matrix-vector multiplication (SpMV) is an important operation in scientific computations. Compressed sparse row (CSR) is the most frequently used format to store sparse matrices. However, CSR-based SpMVs on graphic processing units (GPUs), for example, CSR-scalar and CSR-vector, usually have poor performance due to irregular memory access patterns. This motivates us to propose a perfect CSR-based SpMV on the GPU that is called PCSR. PCSR involves two kernels and accesses CSR arrays in a fully coalesced manner by introducing a middle array, which greatly alleviates the deficiencies of CSR-scalar (rare coalescing) and CSR-vector (partial coalescing). Test results on a single C2050 GPU show that PCSR fully outperforms CSR-scalar, CSR-vector, and CSRMV and HYBMV in the vendor-tuned CUSPARSE library and is comparable with a most recently proposed CSR-based algorithm, CSR-Adaptive. Furthermore, we extend PCSR on a single GPU to multiple GPUs. Experimental results on four C2050 GPUs show that no matter whether the communication between GPUs is considered or not PCSR on multiple GPUs achieves good performance and has high parallel efficiency.

APA, Harvard, Vancouver, ISO, and other styles

31

Liu, Yongchao, and Bertil Schmidt. "LightSpMV: Faster CUDA-Compatible Sparse Matrix-Vector Multiplication Using Compressed Sparse Rows." Journal of Signal Processing Systems 90, no. 1 (January 10, 2017): 69–86. http://dx.doi.org/10.1007/s11265-016-1216-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Giannoula, Christina, Ivan Fernandez, Juan Gómez-Luna, Nectarios Koziris, Georgios Goumas, and Onur Mutlu. "Towards Efficient Sparse Matrix Vector Multiplication on Real Processing-In-Memory Architectures." ACM SIGMETRICS Performance Evaluation Review 50, no. 1 (June 20, 2022): 33–34. http://dx.doi.org/10.1145/3547353.3522661.

Full text

Abstract:

Several manufacturers have already started to commercialize near-bank Processing-In-Memory (PIM) architectures, after decades of research efforts. Near-bank PIM architectures place simple cores close to DRAM banks. Recent research demonstrates that they can yield significant performance and energy improvements in parallel applications by alleviating data access costs. Real PIM systems can provide high levels of parallelism, large aggregate memory bandwidth and low memory access latency, thereby being a good fit to accelerate the Sparse Matrix Vector Multiplication (SpMV) kernel. SpMV has been characterized as one of the most significant and thoroughly studied scientific computation kernels. It is primarily a memory-bound kernel with intensive memory accesses due its algorithmic nature, the compressed matrix format used, and the sparsity patterns of the input matrices given. This paper provides the first comprehensive analysis of SpMV on a real-world PIM architecture, and presents SparseP, the first SpMV library for real PIM architectures. We make two key contributions. First, we design efficient SpMV algorithms to accelerate the SpMV kernel in current and future PIM systems, while covering a wide variety of sparse matrices with diverse sparsity patterns. Second, we provide the first comprehensive analysis of SpMV on a real PIM architecture. Specifically, we conduct our rigorous experimental analysis of SpMV kernels in the UPMEM PIM system, the first publicly-available real-world PIM architecture. Our extensive evaluation provides new insights and recommendations for software designers and hardware architects to efficiently accelerate the SpMV kernel on real PIM systems. For more information about our thorough characterization on the SpMV PIM execution, results, insights and the open-source SparseP software package [21], we refer the reader to the full version of the paper [3, 4]. The SparseP software package is publicly and freely available at https://github.com/CMU-SAFARI/SparseP.

APA, Harvard, Vancouver, ISO, and other styles

33

Dubois, David, Andrew Dubois, Thomas Boorman, Carolyn Connor, and Steve Poole. "Sparse Matrix-Vector Multiplication on a Reconfigurable Supercomputer with Application." ACM Transactions on Reconfigurable Technology and Systems 3, no. 1 (January 2010): 1–31. http://dx.doi.org/10.1145/1661438.1661440.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Catalyurek, U. V., and C. Aykanat. "Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication." IEEE Transactions on Parallel and Distributed Systems 10, no. 7 (July 1999): 673–93. http://dx.doi.org/10.1109/71.780863.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Toledo, S. "Improving the memory-system performance of sparse-matrix vector multiplication." IBM Journal of Research and Development 41, no. 6 (November 1997): 711–25. http://dx.doi.org/10.1147/rd.416.0711.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Williams, Samuel, Leonid Oliker, Richard Vuduc, John Shalf, Katherine Yelick, and James Demmel. "Optimization of sparse matrix–vector multiplication on emerging multicore platforms." Parallel Computing 35, no. 3 (March 2009): 178–94. http://dx.doi.org/10.1016/j.parco.2008.12.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Peters, Alexander. "Sparse matrix vector multiplication techniques on the IBM 3090 VF." Parallel Computing 17, no. 12 (December 1991): 1409–24. http://dx.doi.org/10.1016/s0167-8191(05)80007-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Li, ShiGang, ChangJun Hu, JunChao Zhang, and YunQuan Zhang. "Automatic tuning of sparse matrix-vector multiplication on multicore clusters." Science China Information Sciences 58, no. 9 (June 24, 2015): 1–14. http://dx.doi.org/10.1007/s11432-014-5254-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Dehn, T., M. Eiermann, K. Giebermann, and V. Sperling. "Structured sparse matrix-vector multiplication on massively parallel SIMD architectures." Parallel Computing 21, no. 12 (December 1995): 1867–94. http://dx.doi.org/10.1016/0167-8191(95)00055-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Zeiser, Andreas. "Fast Matrix-Vector Multiplication in the Sparse-Grid Galerkin Method." Journal of Scientific Computing 47, no. 3 (November 26, 2010): 328–46. http://dx.doi.org/10.1007/s10915-010-9438-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Yang, Bing, Shuo Gu, Tong-Xiang Gu, Cong Zheng, and Xing-Ping Liu. "Parallel Multicore CSB Format and Its Sparse Matrix Vector Multiplication." Advances in Linear Algebra & Matrix Theory 04, no. 01 (2014): 1–8. http://dx.doi.org/10.4236/alamt.2014.41001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Ahmad, Khalid, Hari Sundar, and Mary Hall. "Data-driven Mixed Precision Sparse Matrix Vector Multiplication for GPUs." ACM Transactions on Architecture and Code Optimization 16, no. 4 (January 10, 2020): 1–24. http://dx.doi.org/10.1145/3371275.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Tao, Yuan, and Huang Zhi-Bin. "Shuffle Reduction Based Sparse Matrix-Vector Multiplication on Kepler GPU." International Journal of Grid and Distributed Computing 9, no. 10 (October 31, 2016): 99–106. http://dx.doi.org/10.14257/ijgdc.2016.9.10.09.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Dehnavi, Maryam Mehri, David M. Fernandez, and Dennis Giannacopoulos. "Finite-Element Sparse Matrix Vector Multiplication on Graphic Processing Units." IEEE Transactions on Magnetics 46, no. 8 (August 2010): 2982–85. http://dx.doi.org/10.1109/tmag.2010.2043511.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Liang, Yun, Wai Teng Tang, Ruizhe Zhao, Mian Lu, Huynh Phung Huynh, and Rick Siow Mong Goh. "Scale-Free Sparse Matrix-Vector Multiplication on Many-Core Architectures." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 36, no. 12 (December 2017): 2106–19. http://dx.doi.org/10.1109/tcad.2017.2681072.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Aktemur, Barış. "A sparse matrix-vector multiplication method with low preprocessing cost." Concurrency and Computation: Practice and Experience 30, no. 21 (May 25, 2018): e4701. http://dx.doi.org/10.1002/cpe.4701.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Chen, Xinhai, Peizhen Xie, Lihua Chi, Jie Liu, and Chunye Gong. "An efficient SIMD compression format for sparse matrix-vector multiplication." Concurrency and Computation: Practice and Experience 30, no. 23 (June 29, 2018): e4800. http://dx.doi.org/10.1002/cpe.4800.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Karsavuran, M. Ozan, Kadir Akbudak, and Cevdet Aykanat. "Locality-Aware Parallel Sparse Matrix-Vector and Matrix-Transpose-Vector Multiplication on Many-Core Processors." IEEE Transactions on Parallel and Distributed Systems 27, no. 6 (June 1, 2016): 1713–26. http://dx.doi.org/10.1109/tpds.2015.2453970.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Burkhardt, Paul. "Optimal Algebraic Breadth-First Search for Sparse Graphs." ACM Transactions on Knowledge Discovery from Data 15, no. 5 (June 26, 2021): 1–19. http://dx.doi.org/10.1145/3446216.

Full text

Abstract:

There has been a rise in the popularity of algebraic methods for graph algorithms given the development of the GraphBLAS library and other sparse matrix methods. An exemplar for these approaches is Breadth-First Search (BFS). The algebraic BFS algorithm is simply a recurrence of matrix-vector multiplications with the n × n adjacency matrix, but the many redundant operations over nonzeros ultimately lead to suboptimal performance. Therefore an optimal algebraic BFS should be of keen interest especially if it is easily integrated with existing matrix methods. Current methods, notably in the GraphBLAS, use a Sparse Matrix masked-Sparse Vector multiplication in which the input vector is kept in a sparse representation in each step of the BFS, and nonzeros in the vector are masked in subsequent steps. This has been an area of recent research in GraphBLAS and other libraries. While in theory, these masking methods are asymptotically optimal on sparse graphs, many add work that leads to suboptimal runtime. We give a new optimal, algebraic BFS for sparse graphs, thus closing a gap in the literature. Our method multiplies progressively smaller submatrices of the adjacency matrix at each step. Let n and m refer to the number of vertices and edges, respectively. On a sparse graph, our method takes O ( n ) algebraic operations as opposed to O ( m ) operations needed by theoretically optimal sparse matrix approaches. Thus, for sparse graphs, it matches the bounds of the best-known sequential algorithm, and on a Parallel Random Access Machine, it is work-optimal. Our result holds for both directed and undirected graphs. Compared to a leading GraphBLAS library, our method achieves up to 24x faster sequential time, and for parallel computation, it can be 17x faster on large graphs and 12x faster on large-diameter graphs.

APA, Harvard, Vancouver, ISO, and other styles

50

Fitriyani, Fitriyani. "Sliced Coordinate List Implementation Analysis on Sparse Matrix-Vector Multiplication Using Compute Unified Device Architecture." International Journal on Information and Communication Technology (IJoICT) 2, no. 1 (July 1, 2016): 13. http://dx.doi.org/10.21108/ijoict.2016.21.71.

Full text

Abstract:

<p>Matrices are one of the most used data representation form from real-world problems. Lot of matrix was formed very big but sparse, hence information inside the matrix is relatively small compared to its size. This caused into heavy computational resources needed to process those matrices within short time. One of the solutions to do an efficient process to the sparse matrix is to form it into a specialized form of sparse matrix, such as Sliced Coordinate List (SCOO). SCOO format for sparse matrix has been developed and combined within an implementation using Compute Unified Device Architecture (CUDA). In this research, performance of SCOO implementation using GPU – CUDA will be compared to the other sparse matrix format named Coordinate List (COO) based on its memory usage and execution time. Results obtained from this research show that although SCOO implementation for sparse matrix use memory 1.000529 larger than COO format, its serial performance is 3.18 faster than serial COO, besides that, if SCOO implementation is conducted parallel using GPU – CUDA then its performance can be achieved around 123.8 faster than parallel COO or 77 times faster than parallel COO using one of the available library for CUDA, named CUSP.</p>

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!