9
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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