Log in

Relevant bibliographies by topics / Sparse matrix multiplication / Journal articles

To see the other types of publications on this topic, follow the link: Sparse matrix multiplication.

Journal articles on the topic 'Sparse matrix multiplication'

Author: Grafiati

Published: 4 June 2021

Last updated: 16 November 2024

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 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

Seo, Juwon, and Joonho Kong. "VerSA: Versatile Systolic Array Architecture for Sparse and Dense Matrix Multiplications." Electronics 13, no. 8 (April 15, 2024): 1500. http://dx.doi.org/10.3390/electronics13081500.

Full text

Abstract:

A key part of modern deep neural network (DNN) applications is matrix multiplication. As DNN applications are becoming more diverse, there is a need for both dense and sparse matrix multiplications to be accelerated by hardware. However, most hardware accelerators are designed to accelerate either dense or sparse matrix multiplication. In this paper, we propose VerSA, a versatile systolic array architecture for both dense and sparse matrix multiplications. VerSA employs intermediate paths and SRAM buffers between the rows of the systolic array (SA), thereby enabling an early termination in sparse matrix multiplication with a negligible performance overhead when running dense matrix multiplication. When running sparse matrix multiplication, 256 × 256 VerSA brings performance (i.e., an inverse of execution time) improvement and energy saving by 1.21×–1.60× and 7.5–30.2%, respectively, when compared to the conventional SA. When running dense matrix multiplication, VerSA results in only a 0.52% performance overhead compared to the conventional SA.

APA, Harvard, Vancouver, ISO, and other styles

2

Briggs, Preston. "Sparse matrix multiplication." ACM SIGPLAN Notices 31, no. 11 (November 1996): 33–37. http://dx.doi.org/10.1145/240964.240970.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Yuster, Raphael, and Uri Zwick. "Fast sparse matrix multiplication." ACM Transactions on Algorithms 1, no. 1 (July 2005): 2–13. http://dx.doi.org/10.1145/1077464.1077466.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Park, S. C., J. P. Draayer, and S. Q. Zheng. "Fast sparse matrix multiplication." Computer Physics Communications 70, no. 3 (July 1992): 557–68. http://dx.doi.org/10.1016/0010-4655(92)90116-g.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

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

6

Borna, Keivan, and Sohrab Fard. "A note on the multiplication of sparse matrices." Open Computer Science 4, no. 1 (January 1, 2014): 1–11. http://dx.doi.org/10.2478/s13537-014-0201-x.

Full text

Abstract:

AbstractWe present a practical algorithm for multiplication of two sparse matrices. In fact if A and B are two matrices of size n with m 1 and m 2 non-zero elements respectively, then our algorithm performs O(min{m 1 n, m 2 n, m 1 m 2}) multiplications and O(k) additions where k is the number of non-zero elements in the tiny matrices that are obtained by the columns times rows matrix multiplication method. Note that in the useful case, k ≤ m 2 n. However, in Proposition 3.3 and Proposition 3.4 we obtain tight upper bounds for the complexity of additions. We also study the complexity of multiplication in a practical case where non-zero elements of A (resp. B) are distributed independently with uniform distribution among columns (resp. rows) of them and show that the expected number of multiplications is O(m 1 m 2/n). Finally a comparison of number of required multiplications in the naïve matrix multiplication, Strassen’s method and our algorithm is given.

APA, Harvard, Vancouver, ISO, and other styles

7

Ahmed, Md Salman, Jennifer Houser, Mohammad A. Hoque, Rezaul Raju, and Phil Pfeiffer. "Reducing Inter-Process Communication Overhead in Parallel Sparse Matrix-Matrix Multiplication." International Journal of Grid and High Performance Computing 9, no. 3 (July 2017): 46–59. http://dx.doi.org/10.4018/ijghpc.2017070104.

Full text

Abstract:

Parallel sparse matrix-matrix multiplication algorithms (PSpGEMM) spend most of their running time on inter-process communication. In the case of distributed matrix-matrix multiplications, much of this time is spent on interchanging the partial results that are needed to calculate the final product matrix. This overhead can be reduced with a one-dimensional distributed algorithm for parallel sparse matrix-matrix multiplication that uses a novel accumulation pattern based on the logarithmic complexity of the number of processors (i.e., where is the number of processors). This algorithm's MPI communication overhead and execution time were evaluated on an HPC cluster, using randomly generated sparse matrices with dimensions up to one million by one million. The results showed a reduction of inter-process communication overhead for matrices with larger dimensions compared to another one dimensional parallel algorithm that takes run-time complexity for accumulating the results.

APA, Harvard, Vancouver, ISO, and other styles

8

Wang, Ying, and Korhan Cengiz. "Implementation of the Spark technique in a matrix distributed computing algorithm." Journal of Intelligent Systems 31, no. 1 (January 1, 2022): 660–71. http://dx.doi.org/10.1515/jisys-2022-0051.

Full text

Abstract:

Abstract Two analyzes of Spark engine performance strategies to implement the Spark technique in a matrix distributed computational algorithm, the multiplication of a sparse multiplication operational test model. The dimensions of the two input sparse matrices have been fixed to 30,000 × 30,000, and the density of the input matrix have been changed. The experimental results show that when the density reaches about 0.3, the original dense matrix multiplication performance can outperform the sparse-sparse matrix multiplication, which is basically consistent with the relationship between the sparse matrix multiplication implementation in the single-machine sparse matrix test and the computational performance of the local native library. When the density of the fixed sparse matrix is 0.01, the distributed density-sparse matrix multiplication outperforms the same sparsity but uses the density matrix storage, and the acceleration ratio increases from 1.88× to 5.71× with the increase in dimension. The overall performance of distributed operations is improved.

APA, Harvard, Vancouver, ISO, and other styles

9

Bank, Randolph E., and Craig C. Douglas. "Sparse matrix multiplication package (SMMP)." Advances in Computational Mathematics 1, no. 1 (February 1993): 127–37. http://dx.doi.org/10.1007/bf02070824.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Král, Daniel, Pavel Neogrády, and Vladimir Kellö. "Simple sparse matrix multiplication algorithm." Computer Physics Communications 85, no. 2 (February 1995): 213–16. http://dx.doi.org/10.1016/0010-4655(94)00120-q.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Ballard, Grey, Alex Druinsky, Nicholas Knight, and Oded Schwartz. "Hypergraph Partitioning for Sparse Matrix-Matrix Multiplication." ACM Transactions on Parallel Computing 3, no. 3 (December 26, 2016): 1–34. http://dx.doi.org/10.1145/3015144.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Han, Yoonsang, Inseo Kim, Jinsung Kim, and Gordon Euhyun Moon. "Tensor Core-Adapted Sparse Matrix Multiplication for Accelerating Sparse Deep Neural Networks." Electronics 13, no. 20 (October 10, 2024): 3981. http://dx.doi.org/10.3390/electronics13203981.

Full text

Abstract:

Sparse matrix–matrix multiplication (SpMM) is essential for deep learning models and scientific computing. Recently, Tensor Cores (TCs) on GPUs, originally designed for dense matrix multiplication with mixed precision, have gained prominence. However, utilizing TCs for SpMM is challenging due to irregular memory access patterns and a varying number of non-zero elements in a sparse matrix. To improve data locality, previous studies have proposed reordering sparse matrices before multiplication, but this adds computational overhead. In this paper, we propose Tensor Core-Adapted SpMM (TCA-SpMM), which leverages TCs without requiring matrix reordering and uses the compressed sparse row (CSR) format. To optimize TC usage, the SpMM algorithm’s dot product operation is transformed into a blocked matrix–matrix multiplication. Addressing load imbalance and minimizing data movement are critical to optimizing the SpMM kernel. Our TCA-SpMM dynamically allocates thread blocks to process multiple rows simultaneously and efficiently uses shared memory to reduce data movement. Performance results on sparse matrices from the Deep Learning Matrix Collection public dataset demonstrate that TCA-SpMM achieves up to 29.58× speedup over state-of-the-art SpMM implementations optimized with TCs.

APA, Harvard, Vancouver, ISO, and other styles

13

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

14

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

15

Brown, C. I., and R. B. Yates. "VLSI architecture for sparse matrix multiplication." Electronics Letters 32, no. 10 (1996): 891. http://dx.doi.org/10.1049/el:19960606.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

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

17

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

18

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

19

Dalton, Steven, Luke Olson, and Nathan Bell. "Optimizing Sparse Matrix—Matrix Multiplication for the GPU." ACM Transactions on Mathematical Software 41, no. 4 (October 26, 2015): 1–20. http://dx.doi.org/10.1145/2699470.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Wilkinson, Lucas, Kazem Cheshmi, and Maryam Mehri Dehnavi. "Register Tiling for Unstructured Sparsity in Neural Network Inference." Proceedings of the ACM on Programming Languages 7, PLDI (June 6, 2023): 1995–2020. http://dx.doi.org/10.1145/3591302.

Full text

Abstract:

Unstructured sparse neural networks are an important class of machine learning (ML) models, as they compact model size and reduce floating point operations. The execution time of these models is frequently dominated by the sparse matrix multiplication (SpMM) kernel, C = A × B , where A is a sparse matrix, and B and C are dense matrices. The unstructured sparsity pattern of matrices in pruned machine learning models along with their sparsity ratio has rendered useless the large class of libraries and systems that optimize sparse matrix multiplications. Reusing registers is particularly difficult because accesses to memory locations should be known statically. This paper proposes Sparse Register Tiling, a new technique composed of an unroll-and-sparse-jam transformation followed by data compression that is specifically tailored to sparsity patterns in ML matrices. Unroll-and-sparse-jam uses sparsity information to jam the code while improving register reuse. Sparse register tiling is evaluated across 2396 weight matrices from transformer and convolutional models with a sparsity range of 60-95% and provides an average speedup of 1.72× and 2.65× over MKL SpMM and dense matrix multiplication, respectively, on a multicore CPU processor. It also provides an end-to-end speedup of 2.12× for MobileNetV1 with 70% sparsity on an ARM processor commonly used in edge devices.

APA, Harvard, Vancouver, ISO, and other styles

21

Somasekhar, G., and K. Karthikeyan. "Fast Matrix Multiplication with Big Sparse Data." Cybernetics and Information Technologies 17, no. 1 (March 1, 2017): 16–30. http://dx.doi.org/10.1515/cait-2017-0002.

Full text

Abstract:

Abstract Big Data becameabuzz word nowadays due to the evolution of huge volumes of data beyond peta bytes. This article focuses on matrix multiplication with big sparse data. The proposed FASTsparse MULalgorithm outperforms the state-of-the-art big matrix multiplication approaches in sparse data scenario.

APA, Harvard, Vancouver, ISO, and other styles

22

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

23

Demirci, Gunduz Vehbi, and Cevdet Aykanat. "Scaling sparse matrix-matrix multiplication in the accumulo database." Distributed and Parallel Databases 38, no. 1 (January 28, 2019): 31–62. http://dx.doi.org/10.1007/s10619-019-07257-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

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

25

Liu, Junhong, Xin He, Weifeng Liu, and Guangming Tan. "Register-Aware Optimizations for Parallel Sparse Matrix–Matrix Multiplication." International Journal of Parallel Programming 47, no. 3 (January 1, 2019): 403–17. http://dx.doi.org/10.1007/s10766-018-0604-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Zachariadis, Orestis, Nitin Satpute, Juan Gómez-Luna, and Joaquín Olivares. "Accelerating sparse matrix–matrix multiplication with GPU Tensor Cores." Computers & Electrical Engineering 88 (December 2020): 106848. http://dx.doi.org/10.1016/j.compeleceng.2020.106848.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Akbudak, Kadir, Oguz Selvitopi, and Cevdet Aykanat. "Partitioning Models for Scaling Parallel Sparse Matrix-Matrix Multiplication." ACM Transactions on Parallel Computing 4, no. 3 (April 27, 2018): 1–34. http://dx.doi.org/10.1145/3155292.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

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

29

Lin, Chunxu, Wensheng Luo, Yixiang Fang, Chenhao Ma, Xilin Liu, and Yuchi Ma. "On Efficient Large Sparse Matrix Chain Multiplication." Proceedings of the ACM on Management of Data 2, no. 3 (May 29, 2024): 1–27. http://dx.doi.org/10.1145/3654959.

Full text

Abstract:

Sparse matrices are often used to model the interactions among different objects and they are prevalent in many areas including e-commerce, social network, and biology. As one of the fundamental matrix operations, the sparse matrix chain multiplication (SMCM) aims to efficiently multiply a chain of sparse matrices, which has found various real-world applications in areas like network analysis, data mining, and machine learning. The efficiency of SMCM largely hinges on the order of multiplying the matrices, which further relies on the accurate estimation of the sparsity values of intermediate matrices. Existing matrix sparsity estimators often struggle with large sparse matrices, because they suffer from the accuracy issue in both theory and practice. To enable efficient SMCM, in this paper we introduce a novel row-wise sparsity estimator (RS-estimator), a straightforward yet effective estimator that leverages matrix structural properties to achieve efficient, accurate, and theoretically guaranteed sparsity estimation. Based on the RS-estimator, we propose a novel ordering algorithm for determining a good order of efficient SMCM. We further develop an efficient parallel SMCM algorithm by effectively utilizing multiple CPU threads. We have conducted experiments by multiplying various chains of large sparse matrices extracted from five real-world large graph datasets, and the results demonstrate the effectiveness and efficiency of our proposed methods. In particular, our SMCM algorithm is up to three orders of magnitude faster than the state-of-the-art algorithms.

APA, Harvard, Vancouver, ISO, and other styles

30

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

31

Yavits, L., A. Morad, and R. Ginosar. "Sparse Matrix Multiplication On An Associative Processor." IEEE Transactions on Parallel and Distributed Systems 26, no. 11 (November 1, 2015): 3175–83. http://dx.doi.org/10.1109/tpds.2014.2370055.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

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

33

Borštnik, Urban, Joost VandeVondele, Valéry Weber, and Jürg Hutter. "Sparse matrix multiplication: The distributed block-compressed sparse row library." Parallel Computing 40, no. 5-6 (May 2014): 47–58. http://dx.doi.org/10.1016/j.parco.2014.03.012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Azad, Ariful, Grey Ballard, Aydin Buluç, James Demmel, Laura Grigori, Oded Schwartz, Sivan Toledo, and Samuel Williams. "Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication." SIAM Journal on Scientific Computing 38, no. 6 (January 2016): C624—C651. http://dx.doi.org/10.1137/15m104253x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Buluç, Aydin, and John R. Gilbert. "Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments." SIAM Journal on Scientific Computing 34, no. 4 (January 2012): C170—C191. http://dx.doi.org/10.1137/110848244.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Gremse, Felix, Andreas Höfter, Lars Ole Schwen, Fabian Kiessling, and Uwe Naumann. "GPU-Accelerated Sparse Matrix-Matrix Multiplication by Iterative Row Merging." SIAM Journal on Scientific Computing 37, no. 1 (January 2015): C54—C71. http://dx.doi.org/10.1137/130948811.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Lin, Colin Yu, Ngai Wong, and Hayden Kwok-Hay So. "Design space exploration for sparse matrix-matrix multiplication on FPGAs." International Journal of Circuit Theory and Applications 41, no. 2 (October 12, 2011): 205–19. http://dx.doi.org/10.1002/cta.796.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

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

39

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

40

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

41

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

42

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

43

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

44

Peng, Richard, and Santosh S. Vempala. "Solving Sparse Linear Systems Faster than Matrix Multiplication." Communications of the ACM 67, no. 7 (July 2024): 79–86. http://dx.doi.org/10.1145/3615679.

Full text

Abstract:

Can linear systems be solved faster than matrix multiplication? While there has been remarkable progress for the special cases of graph-structured linear systems, in the general setting, the bit complexity of solving an n × n linear system Ax = b is Õ ( n ω ), where ω is the matrix multiplication exponent. Improving on this has been an open problem even for sparse linear systems with poly( n ) condition number. In this paper, we present an algorithm that solves linear systems with sparse coefficient matrices asymptotically faster than matrix multiplication for any ω > 2. This speedup holds for any input matrix A with o ( n ω−1 / log (κ( A ))) non-zeros, where κ( A ) is the condition number of A . Our algorithm can be viewed as an efficient, randomized implementation of the block Krylov method via recursive low displacement rank factorization. It is inspired by an algorithm of Eberly et al. for inverting matrices over finite fields. In our analysis of numerical stability, we develop matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in the eigenvalues of semi-random matrices.

APA, Harvard, Vancouver, ISO, and other styles

45

Artemov, Anton G., and Emanuel H. Rubensson. "Sparse approximate matrix-matrix multiplication for density matrix purification with error control." Journal of Computational Physics 438 (August 2021): 110354. http://dx.doi.org/10.1016/j.jcp.2021.110354.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Deveci, Mehmet, Christian Trott, and Sivasankaran Rajamanickam. "Multithreaded sparse matrix-matrix multiplication for many-core and GPU architectures." Parallel Computing 78 (October 2018): 33–46. http://dx.doi.org/10.1016/j.parco.2018.06.009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Hoque, Mohammad Asadul, Md Rezaul Karim Raju, Christopher John Tymczak, Daniel Vrinceanu, and Kiran Chilakamarri. "Parallel sparse matrix-matrix multiplication: a scalable solution with 1D algorithm." International Journal of Computational Science and Engineering 11, no. 4 (2015): 391. http://dx.doi.org/10.1504/ijcse.2015.073498.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Akbudak, Kadir, and Cevdet Aykanat. "Exploiting Locality in Sparse Matrix-Matrix Multiplication on Many-Core Architectures." IEEE Transactions on Parallel and Distributed Systems 28, no. 8 (August 1, 2017): 2258–71. http://dx.doi.org/10.1109/tpds.2017.2656893.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Somasekhar, G., and K. Karthikeyan. "An Effective Compact Representation Model for Big Sparse Matrix Multiplication." International Journal of Engineering & Technology 7, no. 4.10 (October 2, 2018): 157. http://dx.doi.org/10.14419/ijet.v7i4.10.20827.

Full text

Abstract:

The importance of big data is increasing day by day motivating the researchers towards new inventions. Often, a small amount of data is needed to achieve a solution or to draw a conclusion. The new big data techniques stem from the necessity to retrieve, store and process the required data out of huge data volumes. The present paper focuses on dealing with sparse matrices which is fre-quently needed in many sparse big data applications nowadays. It applies compact representation techniques of sparse data and moulds the required data in the mapreducible format. Then the mapreduce strategy is used to get the results quickly which saves execution time and improves scalability. Finally we established that the new algorithm performs well in sparse big data scenario compared to the existing techniques in big data processing.

APA, Harvard, Vancouver, ISO, and other styles

50

Middendorf, Martin, Hartmut Schmeck, Heiko Schröder, and Gavin Turner. "Multiplication of Matrices With Different Sparseness Properties on Dynamically Reconfigurable Meshes." VLSI Design 9, no. 1 (January 1, 1999): 69–81. http://dx.doi.org/10.1155/1999/32697.

Full text

Abstract:

Algorithms for multiplying several types of sparse n x n-matrices on dynamically reconfigurable n x n-arrays are presented. For some classes of sparse matrices constant time algorithms are given, e.g., when the first matrix has at most kn elements in each column or in each row and the second matrix has at most kn nonzero elements in each row, where k is a constant. Moreover, O(kn ) algorithms are obtained for the case that one matrix is a general sparse matrix with at most kn nonzero elements and the other matrix has at most k nonzero elements in every row or in every column. Also a lower bound of Ω(Kn ) is proved for this and other cases which shows that the algorithms are close to the optimum.

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!