Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose a square, dense, symmetric matrix $A$ has been factorized into $L$ and $U$ components by performing a LU decomposition. Now let $B = A+\lambda I$. Is there any way to efficiently compute the LU decomposition of $B$ by reusing $L$ and $U$, avoiding the cost of a new decomposition?

If the cost of reusing $L$ and $U$ becomes too similar to the cost of recomputing the entire decomposition, would there be any other decomposition more suitable in this case?

Edit: I have found my question to be very similar to solving series of linear systems with diagonal perturbations. I am also trying to solve a series of linear systems where every system is in the form $(A+\lambda I)x=b$ where $\lambda$ is a real number and all $b$s are the same. However, unlike the aforementioned question, my matrices are always dense.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Such an efficient computation is unlikely. Suppose you can do it, with factors $U_\lambda$ and $L_\lambda$. Then by $\det(A+\lambda I)=\det U_\lambda\cdot\det L_\lambda$, you obtain the characteristic polynomial for free. Thus the cost of the calculation you are looking for cannot be smaller than the cost of the calculation of the characteristic polynomial.

For the latter problem, the best algorithm today is in $O(n^{7/2})$, if you employ standard multiplication of matrices (see the new edition of my book "Matrices ; theory and applications, section 3.10). It becomes $O(n^3)$ if you employ fast methods of multiplication (strictly better than Strassen's), but this is only theoritical, since fast matrix multiplaction is recursive, and extremely uncomfortable (if not impossible) to code.

share|improve this answer

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.