# Sparse Matrix or Dense Matrix

My task is to implement the inner product and vector triad forms for a dense $A$ in single and double precision. I have successfully implemented the inner product and vector triad form although, I am not sure if by the way I make a dense matrix $A$ if it is in fact Dense or Sparse.

What I did was essentially just make the matrix $A$ to take in random numbers from 0 to 5. I was told that a Dense matrix is simply a matrix with mostly nonzeros which sounds rather arbitrary to me. Here is the matrix $A$ I created:

$$A = \begin{pmatrix} 3 & 3 & 2 & 4 & 0 & 3 & 2 & 1 & 1 & 4\\ 1 & 1 & 3 & 0 & 3 & 3 & 0 & 1 & 4 & 2\\ 2 & 2 & 2 & 3 & 0 & 3 & 4 & 2 & 4 &4 \\ 1& 2 & 0 & 4 & 0 & 0 & 4 & 0 & 2 & 4\\ 3& 1 & 0 & 1 & 1 & 1 & 4 & 2 & 0 &1 \\ 0 & 4 & 4 & 0 & 4 & 0 & 2 & 1 & 3 &4 \\ 4 & 0 & 4 & 0 & 1 & 2 & 2 & 3 & 0 &4 \\ 4 & 0 & 0 & 4 & 2 & 4 & 2 & 4 & 1 &4 \\ 1& 4 & 3 & 0 & 2 & 1 & 4 &4 & 2 &0 \\ 3& 3 & 1 & 0 & 0 & 2 & 0 & 1 & 3 & 1 \end{pmatrix}$$

Is this matrix Dense?

## 1 Answer

Although there is no "exact" definition, this matrix is certainly dense. The idea of distinguishing sparse/dense matrices refers usually to the fact that if we have only a few non-zero entries, it does not make sense to save the whole matrix (e.g. as an array) in the memory but rather find a less space consuming representation (e.g. a list) which could even allow faster operations than on an array.

• I see I understand, so I assume we use link lists to save memory? I assume that may also make it $O(n)$ rather than the typical $O(n^2)$? I am using C++ to do the implementations just as a side note – Wolfy Feb 6 '16 at 18:29
• Yes, linked lists are one option. And yes, you're right, many sparse matrices have only $O(n)$ entries, some even just $O(n \log n)$. – Adrian Feb 6 '16 at 20:08
• Is there a particular method you would recommend using? – Wolfy Feb 6 '16 at 20:57
• @MorganWeiss What do you mean by a method? To store a sparse matrix? Have a look here. In practice, I saw mostly the coordinate format and compressed sparse row/column formats. Linked lists are not used very much. – Algebraic Pavel Feb 8 '16 at 12:16