# LU decomposition with pivoting

I have to solve system of linear algebraic equations $AX=B$, where $A$ is a two-dimensional matrix with all elements of main diagonal equal to zero.

How to solve this problem? Iterational methods are not applied in this case.

One way is LU Decomposition method with reordering rows of $A$ to get entries in the main diagonal that are not zero, using permutation matrix. How can we quickly reorder the rows of the matrix or find the permutation matrix?

Note that the matrix dimensions are large and I have to write a program to solve SLAE in C# language, so I do not need any Matlab or Mathematica functions. Thanks!

-

Construct a bipartite graph with $n$ vertices on each side $x_i,y_j$. Connect $x_i$ to $y_j$ if $A_{ij} \neq 0$. A maximum matching in this graph, if it involves all the vertices, gives you a permutation $\pi$ such that $A_{i\pi(i)} \neq 0$ for all $i$.