Given a system $Ax = b$, I'm coding a linear solver in Java that takes a triangular matrix $A$ (with 500 to 3,000 rows and columns) and a vector $b$ and solves for $x$. However, the rows and columns in $A$ are unordered and I'm looking for the quickest way to solve this system without pre-arranging such rows and columns to do back substitution. I have tried third party solvers but they are very slow for my application. What is the fastest way you guys know of for this special case? I don't think LU decomposition would help. Note: Matrix $A$ is sparse!
1 Answer
$\begingroup$
$\endgroup$
0
You say that $A$ is triangular. That means you don't have to decompose it into anything. It is already in $LU$ form where $L = I$ and $U = A$ (or vice versa, depending on whether $A$ is upper or lower triangular).
Or would be, I presume, if someone hadn't dropped the card deck.
I think your best bet is effectively to sort the rows based on index of the lowest non-zero column, thus converting into an actual upper triangular matrix. Once sorted, start with the last row, and back-substitute into previous rows. You might speed things up a bit by doing some of the substitution while you are sorting, but I don't think you will see more than minor gains this way. 3000 entries doesn't take long for a good sorting algorithms to handle.