3
$\begingroup$

Let $A$ be an arbitrary real square matrix. Does there exist an $\mathcal O(n^3)$ algorithm for deciding whether there exists a permutation matrix $P$, lower unit triangular matrix $L$, upper unit triangular matrix $U$, and block-diagonal matrix $D$ with $1\times1$ and $2\times2$ blocks such that:

$$P A P^T = LDU$$

The motivation for this problem comes from the fact that almost all matrices admit such a decomposition[1], including all symmetric ones[2]. In spite of that, there exist matrices for which such a decomposition fails to exist. Take the non-singular matrix $\begin{pmatrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{pmatrix}$ for example.

The computation model is BSS.

[1] - This follows from the existence theorem for LU decomposition.

[2] - This follows from the existence of LDL algorithms like Bunch-Parlett and Bunch-Kaufman.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I think is such an algorithm for the case where $A$ is a diagonally dominant M–matrix (the residual doubt is merely that I have not bothered to check the Blum-Shub-Smale part). See section 3 of Barreras, A. and Peña, J. M. "Accurate and efficient LDU decomposition of diagonally dominant M-matrices." Elect. J. Lin. Alg. 25, 153 (2012).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Cool. I'll take a look $\endgroup$
    – wlad
    Commented Dec 16, 2020 at 13:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .