5
$\begingroup$

In George, Liu, and Ng's book Computer Solutions of Sparse Linear Systems, it has been shown that bandwidth of $A$ is equal to bandwidth of its factors in $LL^T$.(section 4.3) However, I guess this is proven only for $LL^T$ factorization for positive definite matrices. Is there a similar proof for indefinite matrices for factors in $LDL^T$, where $D$ is a block-diagonal matrix with at most $2\times 2$ blocks and assuming that such a factorization exists?

$\endgroup$

1 Answer 1

1
$\begingroup$

It is generally true for the $LU$ factorization of any matrix that the bandwidth of the factors equals the bandwidth of the original matrix. In fact, the result is stronger: that the skyline of the factors is contained in the skyline of the original matrix. This is actually not all that difficult to see if you consider the steps one has to take to compute the $LU$ factorization, which are equivalent to the first half of Gaussian elimination.

So if you ask for an $LDL^T$ factorization of a symmetric and possibly indefinite matrix $A$: Your $LU$ factors are $LD^{1/2}$ and $D^{1/2}L^T$ for which the bandwidth is at most that of the original matrix $A$. Consequently, the same can be said about the matrix $L$ as well.

$\endgroup$
5
  • 1
    $\begingroup$ Quick remark though: for an indefinite matrix the $LU$ or $LDL^T$ factorization could be unstable without some form of pivoting, and pivoting destroys the band structure. $\endgroup$ Nov 27, 2014 at 9:51
  • $\begingroup$ @FedericoPoloni: So are you saying that when there is pivoting we cannot say anything about the bandwidth of the factor? $\endgroup$
    – Armut
    Dec 3, 2014 at 21:51
  • 1
    $\begingroup$ @Armut Yes. Pivoting will usually enlarge the bandwidth of $A$ (and so that of $L$). It is easy to find examples when this happens. $\endgroup$ Dec 4, 2014 at 6:45
  • 1
    $\begingroup$ @Armut: The reason being that pivoting is equivalent to applying a permutation to the matrix rows and columns. Permuting it destroys a banded structure. $\endgroup$ Dec 5, 2014 at 2:35
  • $\begingroup$ Based on Wolfgang's and @Federico's comments, the answer is 'yes' if there is no pivoting and 'no', or 'not necessarily' if there is pivoting. I added a related question to find out if it is possible to preserve sparsity within some bounds when there is pivoting. $\endgroup$
    – Armut
    Jul 11, 2018 at 16:09

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.