I'm trying to find an efficient way to solve a system of equations given by $STx = b$ where $S, T$ are N by N matrices that have a given LU decomposition for each. I believe the most efficient approach is as follows:
$$P_{S}Tx = P_{S}b $$ $$ L_{S}U_{S}Tx = P_{S}b \text{, Let } z = Tx$$ $$ L_{S}U_{S}z = P_{S}b \text{, Let } y = U_{S}z $$ $$L_{S}y = P_{S}b $$
Now $ L_{S}y = P_{S}b $ can be solved, and then $y$ and $z$ can be solved for. After that the linear system $z = Tx$ can be solved. I'm wondering if this is a correct approach (even if its not optimal), its been a while since I've done linear algebra and I'm not sure if I can substitute variables and solve as I did.
First, rewrite the system as $$ P_{S}L_{S}U_{S}P_{T}L_{T}U_{T}x=b $$ where $A=P_{A}L_{A}U_{A}$ is the PLU factorization of a matrix $A$. It follows that $$ x=U_{T}^{-1}(L_{T}^{-1}(P_{T}^{\intercal}(U_{S}^{-1}(L_{S}^{-1}(P_{S}^{\intercal}b))))). $$ In the above, the order of operations is important for computation. First, note that permutations can be performed in $O(N)$ time. Moreover, given a lower or upper triangular matrix $A$ and a vector of compatible size $v$, $A^{-1}v$ can be computed inexpensively ($O(N^2)$ FLOPs) using either forward or backward substitution.
Of course, you should not materialize the inverses $L^{-1}$ or $U^{-1}$.