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

• 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