Gauss-Siedel method is an iterative method to solve matrix equations of the form A.x = b, that proves to be useful in certain scenarios. The convergence criterion of this iterative method is that it needs to be diagonal dominant, i.e., | a_ii | > | a_ij | for all distinct pairs of (i,j). One can use elementary row swapping operations to rearrange the rows of matrix A, so that the dominant term in each row is at the diagonal position.
In the presented function, the Gauss-Siedel solver has called another function to rearrange the rows. The algorithm to rearrange is -
1. Create an empty graph G
2. Create a set I of vertices numbered from 1 to n
3. Create a set J of vertices numbered from 1 to n
4. For each row i, find the column j that holds the dominant term in that row. Add a directed edge from i in I to j in J.
5. We now need to select a mapping from I to J that is one-one and onto. This is can be represented in the form of a standard problem in the field of data structures and algorithms called bipartite matching.
6. A standard way to solve the problem of bipartite matching is to use the Ford-Fulkerson algorithm. In this algorithm,
a. create two vertices s and t
b. create edges with capacity 1 from s to each vertex in I
c. create edges with capacity 1 from each vertex in J to t
d. find maximum possible flow from s to t
7. If max flow out of s is n, then convergence criterion is met. For each edge form i in I to j in J, that carries a non-zero flow, put copy values of row i in original matrix to row j in new matrix.
P.S. : I failed to realize that a row can have at most one dominant term, while writing the code. This probably makes things simpler, and can be solved without Ford-Fulkerson algorithm. But this algorithm is more elegant (not the most efficient though) since it automatically answers the question if convergence is possible.
Thanks to Karl Ezra Pilario for his code on Ford Fulkerson Algorithm that has been edited and used in these functions.
Souritra Garai (2023). Rearranging Rows for Gauss - Seidel Method (https://www.mathworks.com/matlabcentral/fileexchange/78571-rearranging-rows-for-gauss-seidel-method), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform CompatibilityWindows macOS Linux
Inspired by: Ford-Fulkerson Algorithm for Max Flow Problem
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!