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
$\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$
  • 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$ – Federico Poloni Nov 27 '14 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 '14 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$ – Federico Poloni Dec 4 '14 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$ – Wolfgang Bangerth Dec 5 '14 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 '18 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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