# Solve system involving unordered triangular matrix

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!

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).