# Is there an upper bound for fill-ins for indefinite triangular factorization?

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.

## 1 Answer

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