Inconsistent Results Between Lu Decomposition In R And Python

I have the following matrix A in R: # [,1] [,2] [,3] [,4] # [1,] -1.1527778 0.4444444 0.375 0.3333333 # [2,] 0.5555556 -1.4888889 0.600 0.3333333 # [

Solution 1:

It is embarrassing to realize 1.5 years later that my original answer is not fully correct. While it correctly pointed out that the rank-deficiency of A in the question is the cause, it is incorrect to attribute this as the root cause. The real issue is the non-unique choice of pivot, which could happen (although less likely) even if A is full-rank. Given that this post has been viewed 700+ times and has a score of 6, I might have misled many readers. SORRY!

I posted Write a trackable R function that mimics LAPACK's dgetrf for LU factorization and answered it just now. The question contains a LU function for LU factorization without pivoting, and the answer contains two functions LUP and LUP2 for a version with row pivoting that are consistent with LAPACK's dgetrf, which underlies the dense method of Matrix::lu and R base function solve. In particular, the LUP2 function allows one to track the factorization step by step. I will use this function here for investigation.

---

So you are factorization the transpose of A.

From the output of R and Python we see that they yield identical 1st pivot -1.1527778 and 2nd pivot -1.2746988, while the 3rd pivot differs. So there is definitely something interesting happening when the factorization has done the first two columns / rows and proceeds to the the 3rd column / row. Let's pause R's LU factorization at this point:

oo <- LUP2(t(A), to = 2)
#           [,1]       [,2]       [,3]       [,4]#[1,] -1.1527778  0.5555556  0.6250000  0.6666667#[2,] -0.3855422 -1.2746988  0.6409639  0.9236948#[3,] -0.3253012 -0.6124764 -1.2291115  0.9826087#[4,] -0.2891566 -0.3875236  1.2291115 -0.9826087#attr(,"to")#[1] 2#attr(,"pivot")#[1] 1 2 3 4

At this point, the Gaussian elimination has reduced t(A) to

getU(oo)
#           [,1][,2][,3][,4]
#[1,] -1.15277780.55555560.62500000.6666667
#[2,]0.0000000 -1.27469880.64096390.9236948
#[3,]0.00000000.0000000 -1.22911150.9826087
#[4,]0.00000000.00000001.2291115 -0.9826087#attr(,"to")
#[1]2

Wow, we see something really interesting now: the 3rd and 4th rows only differ by a sign change. Then the Gaussian elimination is not unique, because either -1.2291115 or 1.2291115 can be a pivot as they have the same absolute value.

Clearly, R has chosen -1.2291115 as the pivot, but Python has chosen 1.2291115 as the pivot. A row exchange between 3rd and 4th rows will happen in Python. In your question, you didn't report what permutation index Python gives you, but it should 1, 2, 4, 3, instead of the 1, 2, 3, 4 in R.

---

Either way, the U factor ends up with a row of zeros in the bottom, so that t(A) or A is not full-rank. If you want to see a more consistent behavior between two software, you'd better try a full-rank matrix. In that case, it is less likely that you will have more than one choices for a pivot during LU factorization. You can generate a random full-rank matrix in R by

A <- matrix(runif(16), 4, 4)