Wikipedia:Reference desk/Archives/Computing/2020 August 22
Computing desk | ||
---|---|---|
< August 21 | << Jul | August | Sep >> | August 23 > |
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
editany reason that array based sparse matrix will be slower than linkedlist sparse matrix?
editHi 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 denote the set of column indices such that , and let similarly denote the set of row indices such that . (So iff .) If , then . Random access of elements in sparse representation, as seemingly required, is expensive, but note that can be restricted to the intersection of and . If is represented as a collection of sparse row vectors and as a collection of sparse column vectors,, it is cheap to find the values of 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)
- sparse matrix multiplication.--Exx8 (talk) 07:08, 23 August 2020 (UTC)