When doing LU decomposition, the algorithm will break down if any of the diagonal element $x_{ii}$ is zero. Therefore, we can use pivoting on the matrix such that $x_{ii}$ is no longer zero. That is, instead of looking at the $x_{ii}$ we look at another element $x$ in the matrix.

One problem with LU decomposition is that when our matrix $A$ is sparse, we would like to keep the sparsity pattern of $A$, something that will not happen when we do LU decomposition. Therefore, we can use incomplete LU decomposition, where if $x_{ij}$ of $A$ is zero, we also skip $x_{ij}$ of $L$ or $U$ depending on where $x_{ij}$ is in $A$.

My question is: will we do pivoting for incomplete LU decomposition? If we do, how do we do it? If we don’t, how do we make sure that our algorithm doesn't break?

  • $\begingroup$ This may be rather a question for Scientific Computing SE, scicomp.stackexchange.com $\endgroup$ – Joce Feb 14 at 16:14
  • $\begingroup$ I am not a specialist but I would say yes. You would perform it the same way as for a dense matrix, choosing the pivot among the nonzero elements and performing elimination only on the nonzero elements. It can probably break, but not with a worse probability than without pivoting (just a guess). $\endgroup$ – Yves Daoust Feb 14 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.