Here and there I have been reading that row interchanges make LU decomposition more stable, but I haven't been able to find an explanation why it's really necessary.Are there any circumstances where row interchages is a waste of processing time and what are the cases when it's absolutely essential?

A text book example. Try to get LU on the following 2x2 matrix a, a(1,1) = eps, a(1,2) = 1, a(2,1) = 1, a(2,2) = 1,WITHOUT pivoting, in computer. The eps is as small as 1.0E-20. After you decomp, try to recover a. Do you succeed?Most of the time, you probably LU on matrices of which diagonal elements dominate others.If you know this is all you're going to do, then go for it.If you have to automate your code so that it works for general non-singular matrices, do pivoting or partial pivoting, unless youdon't mind waking up in the middle of the night.

Your example is indeed a problematic one, since I would have to divide 1 by 1.0e-20 in the first operation.But what if all of my matrices where symmetrical and constructed in such a way that element at a(1, 1) is actually the largest one and:1) a(1,1) > a(2,2) > a(3,3) ....and 2) a(1, 1) > a(2, 1) > a(3 , 1) ..... a(2, 2) > a(3, 2) > a(4, 2) ... Cholesky decomposition would be really quick ands easy here, but the matrix is not always positive definite. I am wondering if a light version of LU decomposition would be safe to use here.Thanks.

I am a postgraduate student. I study "MSc RISK MANAGEMENT & FINANCIAL SERVICES", I have some strong educational background in the trading and use of financial derivatives. I need some good idea for a dissertation that will combine financial risk management techniques, with the uses in financial institutions, banks, intermediaries, hedge funds etc.I am particullary interested in the uptodate key sector aspects.

The serious problem was not the division. It was the floating point arithmetic that makes 1.0E+20 - 1 = 1.0E+20.From what you said, I'm not even sure if LU is safe, because you can't guarantee (numerical) non-singularity.(Also the diagonal dominance is typically done in absolute value.)What's the typical size of your matrices?

From memory, the pivoting does not change the complexity of the algorithm, which is proportional to n^3, hence it's difficult to see that an unstable 'optimised' code thatwill work in some cases is preferable to something that's stable and of the complexity?

The matrix size will be from 5x5 to 9x9. The smallest (absolute) element is going to be roughtly 1.0e-7.QuoteFrom memory, the pivoting does not change the complexity of the algorithmThis is a very interesting comment, but it's not very intuitive. Is this really the case?

Yes, it is intuitive.The maths to calculate the L and U in a decomposition as A = LU is quitesimple (Crout's algorithm). A nice description can be found in Numerical Recipes.It's also quite simple to count the number of operations, which will be proportional to n^3. The pivoting does not impact this, but it does makethe algorithm stable, for the reasons described in NR.There is a slightly more advanced treatment (and more on the complexityissues) in 'Introduction to Algorithms by Cormen and Rivest.The impact of the pivoting is to decompose as LU = PA, where P is a matrixof one's and zero's (a permutation matrix), rather than LU = A.Hope this is useful.