How to interchange rows in iterative methods for solving linear system?

Question

In all resources about iterative methods (e.g. Jacobi method) there's information that if there are zeros on main diagonal, rows or columns must be interchanged, but what exact algorithm should be used for that? The naive method of finding row with maximum element and interchanging it, won't always work, right?

Answer 1

In full generality, this is the problem of finding a perfect matching in a bipartite graph. Here, the graph has two parts $R$ and $C$ of size $n$ corresponding to the rows and columns, with an edge from $i\in R$ to $j\in C$ if $A_{ij} \ne 0$.

We can find a perfect matching, assuming it exists, using the Ford-Fulkerson algorithm on this graph. Most sources on Ford-Fulkerson solve the equivalent maximum-flow problem, and many assume that the graph is weighted and we want the maximum-weight matching. But you can find a description of the unweighted matching problem on http://www.geeksforgeeks.org/maximum-bipartite-matching/, which shouldn't be too far removed from the matrix setting (especially since they store the bipartite graph as an adjacency matrix anyway).