Comment Comment by jacobolus For example, you factorize A into LU, so that you have LUx = b.Now you can let Ux = y, solve the system Ly = b for y, then solve Ux = y for x.Solving each triangular system is fast: O(n^2).If you need to do this with a different b, you can do it again, and you already have A factorized, which was the expensive part, i.e. O(n^3).(Depending on the type of problem, you might want to factorize the original matrix in a different way, e.g. QR or Cholesky or whatever.) parent jacobolus 10 years ago
Now you can let Ux = y, solve the system Ly = b for y, then solve Ux = y for x.
Solving each triangular system is fast: O(n^2).
If you need to do this with a different b, you can do it again, and you already have A factorized, which was the expensive part, i.e. O(n^3).
(Depending on the type of problem, you might want to factorize the original matrix in a different way, e.g. QR or Cholesky or whatever.)