1
$\begingroup$

For $A=LU$, or $A=LDL^T$ factorization, bandwidth is preserved when there is no pivoting. This is true even for indefinite A, see question. However, when there is pivoting band structure is destroyed, so fill-ins can occur outside the band. I am curious if there is any pivoting that can still preserve sparsity for the factors within some bounds.

$\endgroup$
2
$\begingroup$

The commonly-used partial pivoting strategy (selecting the pivot as the maximum coefficient in the current column) can be used for band matrices. If the lower bandwidth of the original matrix A is defined as kl and the upper bandwidth as ku, the factors L and U will have bandwidths kl+1 and ku+kl, respectively. This result is shown in section 4.3.3 of Matrix Computations, by Golub and Van Loan.

This method is implemented in Lapack routine dgbtrf. The details of the implementation are discussed here: http://www.netlib.org/lapack/lawnspdf/lawn21.pdf

$\endgroup$

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.