title: Fast sparse matrix multiplication
body: <p>for class I have to write my own linear equation solver for sparse matrices.
  I am free to use any type of data structure for sparse matrices and I have to implement several solves, including conjuguate gradient.</p>
  
  <p>I was wondering if there is a famous way to store sparse matrices such that multiplication with a vector is relatively fast.</p>
  
  <p>Right now my sparse matrices are basically implemented a wrapped <code>std::map&lt; std::pair&lt;int, int&gt;, double&gt;</code> which stores the data, if any. This transforms the multiplication of a matrix with from vector to a O(n²) complexity to a O(n²log(n)) as I have to perform look-up for each matrix elements.
  I've looked into the Yale Sparse matrix format and it seems that retrieval of an element is also in O(log(n)) so I'm not sure if it would be much faster.</p>
  
  <p>For reference I have a 800x800 matrix that is populated with 5000 entries. It takes roughly to 450 seconds solve such a system with the conjugate gradient method.</p>
  
  <p>Do you think it's possible to do it much quicker with another data structure?</p>
  
  <p>thanks!</p>