I have a similarity matrix which is symmetric and sparse. How can I parallelize the computation of the eigenvalues of this matrix in MATLAB?
MathWorks doesn't think this is a good idea. Their basic defense for not multithreading
eigs is that the MATLAB sparse matrix-vector products will not significantly benefit from multithreading. I recommend that you look into some of the libraries discussed in another answer on scicomp if you are interested in computing eigenvalues more efficiently.
The power method requires a matrix-vector product at every iteration, which can be executed in parallel. If you are using a distributed computer, you can explicity allocate the vector and a certain number of rows of the matrix to each processor and calculate a portion of the resulting vector (this is called row-wise decomposition). These partial results can be combined into a single result using an all-gather operation. Alternatively, if you are using a symmetric computer, Matlab's Parallel Computing Toolbox has a parallel-for loop operation which can allow you do do this wihout altering your sequential code too much.
The inverse method requires a linear system of equations to be solved. Again, you can implement virtually any linear system solver method that you want in parallel. If you choose to use the conjugate gradient method, it too requires a matrix-vector product at every iteration, which can be executed in parallel using Matlab's PCT's parallel for-loop operation.