Wikipedia:Reference desk/Archives/Computing/2020 August 22

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 22

any reason that array based sparse matrix will be slower than linkedlist sparse matrix?

Hi there, Is there a reason that a sparse matrix represented by an array of a linked list will exhibit a faster performance than a sparse array representation of a matrix? --Exx8 (talk) 18:40, 22 August 2020 (UTC)

This depends both on the specifics of in particular the sparse array representation, for which there are many options, and the specific matrix operations being performed.  --Lambiam 21:29, 22 August 2020 (UTC)

sparse matrix multiplication.--Exx8 (talk) 07:08, 23 August 2020 (UTC)

Let $R_{i}(M)$ denote the set of column indices $j$ such that $M_{i,j}\neq 0$, and let similarly $C_{i}(M)$ denote the set of row indices $i$ such that $M_{i,j}\neq 0$. (So $j\in C_{i}$ iff $i\in R_{j}$.) If $C=AB$, then $C_{i,j}={\Sigma }_{k}A_{i,k}B_{k,j}$. Random access of elements in sparse representation, as seemingly required, is expensive, but note that $k$ can be restricted to the intersection of $R_{i}(A)$ and $C_{j}(B)$. If $A$ is represented as a collection of sparse row vectors and $B$ as a collection of sparse column vectors,, it is cheap to find the values of $k$ that contribute to the sum.

One can use linked lists to represent the sparse row and column vectors; if doubly linked, insertion is easier, but for matrix multiplication that is not an important issue.  --Lambiam 10:24, 23 August 2020 (UTC)