Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it a "standard" Math/Numerical-Analysis hack to add a relatively small number e.g. 1*10E-5 to the diagonal of a squared matrix to ensure LU Decomposition (or whichever decomposition algorithm is applicable)? As opposed to "partially/totally pivoting"?

[Edit] The problem: I am computing the regressors for a statistical regression model, and the constraints are that we can no longer bring in any open source software. Hence I am drawing on my undergrad courses in Linear Algebra and Numerical Methods to implement the solution.

I am currently using Croute's LU Decomposition algorithm (http://en.wikipedia.org/wiki/Crout_matrix_decomposition) with partial pivoting on the rows.

share|improve this question
    
I would say that one is instructive to teaching, while the other is instructive to solving. –  Amzoti Mar 11 '13 at 15:08
    
I'm a programmer and only concerned with solving :) –  Reuben Peter-Paul Mar 11 '13 at 15:09
2  
This sounds like a really bad idea. Take the matrix $\begin{bmatrix}0&1\\1&0\end{bmatrix}$ and compare the LU decompositions you get with pivoting and with your approach without pivoting. –  Rahul Mar 11 '13 at 15:19
    
I agree @RahulNarain, I also fear the negative effects that such a hack has on the model itself. –  Reuben Peter-Paul Mar 11 '13 at 15:27
    
Also consider $\begin{bmatrix}-10^{-5}&1\\1&-10^{-5}\end{bmatrix}$... –  Rahul Mar 11 '13 at 16:10
add comment

2 Answers

up vote 2 down vote accepted

For the LU decomposition to happen, you need the leading principal minors of every order to be non zero.

Since the eighenvalues of the matrix $A$ are really close to the ones of the matrix $B = A+\alpha I$ for $\alpha$ close to $0$, using $B$ instead of $A$ as a first step in the decomposition, helps preventing errors at a minimum cost.

share|improve this answer
add comment

It has been my experience that solving problems using numerical methods always brings into focus the great difficulties with having general solutions that always work.

It seems that the problems always have pathological tendencies that make the solver not work in all cases.

This requires that our methods have all the tricks we can muster in the toolbox in order to handle all of these pathological cases.

Although I agree that pivoting it likely best, there may be instances where both are required in order to solve a particular problem.

This indeed is the danger with all of the math SW we see out there because one has to have some level of understanding of what can and does go wrong.

I am not sure if this answer is satisfying.

Regards

share|improve this answer
    
Thank you for your answer @amzoti. –  Reuben Peter-Paul Mar 12 '13 at 14:46
    
@ReubenPeter-Paul: You are very welcome. Always remember, the best libraries have anticipated as many of the pathological things that can happen and can account for them without operator intervention! Regards –  Amzoti Mar 12 '13 at 14:47
    
Great advice, Amzoti! –  amWhy Apr 21 '13 at 0:28
    
@amWhy: thank you my friend! –  Amzoti Apr 21 '13 at 0:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.