I would like to find an algorithm for obtaining all ergodic components of a finite Markov chain with discrete time defined by its transition matrix (i.e. ergodic subchains into which the given chain is being decomposed).
Certainly, the task can easily be solved by calculation of adjacency matrix of the digraph corresponding to the chain and consequent calculation of reachability matrix of this digraph. But this way is computationally very cost. Maybe, does there exist more efficient algorithm?
On
Let me give an answer in a different direction: Your problem is to find the terminal strongly connected components. The complexity of this problem is not bad for any sense of bad used in computer science, but I understand that you want the most efficient algorithm. Try to look into computer science literature, in particular search on graphs.
I'm not an expert on this kind of complexity theory, and the distinctions can be subtle, but I think you will have to live with something akin to linear in the size of the state space.
This is an explanation of Thomas's comment, but too long for a comment:
Each strongly connected component of the transition graph that has no exit edges supports a unique stationary distribution which is ergodic. On the other hand, every stationary distribution is supported on the union of such strongly connected components (transient components have no stationary weight), and conditioning a stationary distribution on being in a single component again gives a stationary distribution. So, every stationary distribution can be written as a convex combination of the ergodic distributions supported at strongly connected components with no exit edges.
Therefore, you only need to find the strongly connected components, and for each component the unique stationary distribution supported at that component.