How to solve a positive semidefinite system in general

Question

I was trying to solve a markov system over a graph transition process
and basically it is reduced into solving $Ax=x$ which is to solve $(A-I) x = 0$
where $A$ is the transition matrix being real symmetric. So we can have assumption that A is at least positive-semidefinite
I know how to solve a strictly positive definite system by algorithms such as Cholesky Decomposition or Conjugate Gradient method.
But I do not have assumption that A is non-singular. However, I do know that this is a sparse matrix. So here comes my question.
How do I generally solve an positive-semidefinite system? By solving I means to find an arbitrary solution or find the whole kernel of it.
p.s. I would like to avoid something like naive Gauss Jordan method because it is not time efficient.

Answer 1

What you are trying to do, is saerching for the eigenvector, that has the eigenvalue of 1. This makes $A-I$ singular. You could use an iterative approach to solve for all eigenvalues at the same time (Langzos method, MATLAB can do this via eigs) and discard all other eigenvalues. Similarly, you could use (since you know, where one eigenvalues must lie) inverse iteration. By this, you use an iterative approach with $(A-I)^{-1}$. But since that matrix does not exist, you could use $(A-0.9I)^{-1}$. This will (hopefully) give a non-singular matrix and will converge fast towards your eigenvector.