Content deleted Content added
HerrHartmuth (talk | contribs) m added interwiki links |
HerrHartmuth (talk | contribs) m added a specific name for a phenomenon |
||
Line 4:
One then solves <math>Ly = b</math>, <math>Ux = y</math>, which can be done efficiently because the matrices are triangular.
For a typical sparse matrix, the LU factors can be much less sparse than the original matrix — a phenomenon called ''fill-in''.
The memory requirements for using a direct solver can then become a bottleneck in solving linear systems. One can combat this problem by using fill-reducing reorderings of the matrix's unknowns, such as the [[Cuthill-McKee algorithm|Cuthill-McKee ordering]]. An incomplete factorization instead seeks triangular matrices ''L'', ''U'' such that <math>A \approx LU</math> rather than <math>A = LU</math>. Solving for <math>LUx = b</math> can be done quickly but does not yield the exact solution to <math>Ax = b</math>. So, we instead use the matrix <math>M = LU</math> as a preconditioner in another iterative solution algorithm such as the [[conjugate gradient method]] or [[GMRES]].
| |||