For the purposes of solving linear equations, is there a fast decomposition that works for all Hermitian matrices?

Question

Let $A$ be an arbitrary Hermitian matrix. Is there a way of efficiently factorizing $A$ for the purposes of solving $Ax = b$ for arbitrary $b$?

There are two decompositions I'm aware of that nearly solve this problem. One decomposition is the LDL decomposition (a variant of Cholesky) which exists for some (most?) Hermitian matrices. The problem with LDL is that it doesn't exist for all Hermitian matrices. The next decomposition that I've considered is the LU decomposition with pivoting -- while indeed this works for all Hermitian matrices, it's twice as slow as LDL.

The variant of LDL with some pivoting described here doesn't work for the matrix $\begin{pmatrix}0 & 1 \\ 1 & 0 \end{pmatrix}$. Essentially, it proposes decomposing $A$ into $P LDL^T P^T$ where $P$ is a permutation matrix, which doesn't work for any nonsingular matrix with $0$s throughout its diagonal. (EDIT: In light of the answer, it's possible that I've misunderstood this paper.)

I'm aware that Scipy (and therefore LAPACK) does its LDL decomposition with pivoting. But I don't know what kind of speed penalty this entails.

So does there exist a matrix decomposition that applies to all Hermitian matrices but which is twice as fast as LU?

Answer 1

From my comments: LDL variants that implement symmetric pivoting and avoid issues with zero diagonals have been invented in the 1970s: Bunch-Kaufman pivoting, Aasen's method for LTL factorization (the T stands for tridiagonal). This is discussed in detail in Section 4.4 of Golub-Van Loan Matrix Computations 4th ed, which starts precisely with your example $\begin{bmatrix}0 & 1\\ 1 & 0\end{bmatrix}$, but with $\varepsilon$ instead of zeros to spice things up. Scipy/Lapack use these variants, which cost $\frac13 n^3$ (half as much as LU, as requested).