I'm writing a program, and I want to decompose the matrix $A$ into the product of a lower triangular matrix $L$ and an upper triangular matrix $U$. So I am performing an $LU$ decomposition.

But there are also $PA = LU$ decompositions in which you must interchange rows to get things to work out. I do not want to do this, and I want to quit the program if this is necessary.

So my question is: Given a matrix $A$, how can I (quickly/efficiently) determine whether the $LU$ decomposition requires pivoting? I have searched online and cannot find anything.


| cite | improve this question | | | | |

In a numeric case, i.e. $A \in \mathbb{R}^{n \times n}$, you never need pivoting on a computer. That is because you only need to use pivoting if you get zeros in places where you don't want them. However, with real numbers and finite precision on computers, you will never see a true zero, you will only see something like $1e-19$. Of course, you might still not want to divide by that, but formally, pivoting is not necessary.
If you want to handle real matrices, I would suggest reading up on them. The usual algorithms use pivoting even when not needed, to keep the result more stable (again, while you could in theory divide by something like $1e-19$ without pivoting, you really don't want to...).

Now assume you are in a case where we have exact precision, e.g. $A \in F^{n \times n}$ where $F$ is a finite field. Here, I think the computational fastest way is to really run the LU-algorithm and quit once pivoting gets necessary. Even things like eigenvalues, minimal polynomial, etc. usually take longer to compute than an LU decomposition; in fact computing such a decomposition is the first step in many algorithms. What you can do, if you don't already, is first compute only $L$, that might speed your things up a little bit.

| cite | improve this answer | | | | |
  • $\begingroup$ @Rahul Depends on the implementation. Some systems not only store the value of a number but also the information that some numbers are the same. As soon as you have some noise from previous computations (e.g. divisions, which happen quite often in LU decomposition), the chance to get true zeros gets quite low and we can't really rely on it anymore. $\endgroup$ – Dirk Apr 25 '19 at 9:56

Your Answer

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