1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Wolfy Feb 6 '16 at 18:29
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Adrian Feb 6 '16 at 20:08
  • $\begingroup$ Is there a particular method you would recommend using? $\endgroup$ – Wolfy Feb 6 '16 at 20:57
  • $\begingroup$ @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. $\endgroup$ – Algebraic Pavel Feb 8 '16 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.