Symmetric factorizations

PDF
$$ %% Sets and functions %% \newcommand{\set}[1]{\{ #1 \}} \newcommand{\Set}[1]{\left \{ #1 \right\}} \renewcommand{\emptyset}{\varnothing} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Rn}{\mathbb{R}^n} \newcommand{\Rm}{\mathbb{R}^m} \newcommand{\C}{\mathbb{C}} \newcommand{\F}{\mathbb{F}} %% Linear algebra %% \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\Abs}[1]{\left\lvert #1 \right\rvert} \newcommand{\inner}[2]{\langle #1, #2 \rangle} \newcommand{\Inner}[2]{\left\langle #1, #2 \right\rangle} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\Norm}[1]{\left\lVert #1 \right\rVert} \newcommand{\tp}{{\top}} \newcommand{\trans}{{\top}} \newcommand{\span}{\operatorname{span}} \newcommand{\im}{\operatorname{im}} \newcommand{\ker}{\operatorname{ker}} \newcommand{\rank}{\operatorname{rank}} \newcommand{\proj}{\operatorname{proj}} \newcommand{\proj}[1]{\mathop{\mathrm{proj}_{#1}}} \newcommand{\refl}{\operatorname{refl}} \newcommand{\refl}[1]{\mathop{\mathrm{refl}_{#1}}} \newcommand{\K}{\mathcal{K}} \newcommand{\L}{\mathcal{L}} \renewcommand{\epsilon}{\varepsilon} \newcommand{\conj}{\overline} \newcommand{\sign}{\operatorname{sign}} %% Colours %% \definecolor{cblue}{RGB}{31, 119, 180} \definecolor{corange}{RGB}{255, 127, 14} \definecolor{cgreen}{RGB}{44, 160, 44} \definecolor{cred}{RGB}{214, 39, 40} \definecolor{cpurple}{RGB}{148, 103, 189} \definecolor{cbrown}{RGB}{140, 86, 75} \definecolor{cpink}{RGB}{227, 119, 194} \definecolor{cgrey}{RGB}{127, 127, 127} \definecolor{cyellow}{RGB}{188, 189, 34} \definecolor{cteal}{RGB}{23, 190, 207} $$

The LDL* factorization

Let $A \in \C^{n \times n}$ and suppose that its first $n-1$ leading principal minors are nonzero. Then $A$ has a unique LU factorization $A = LU$, and moreover $u_{11}, \dots, u_{n-1,\,n-1}$ are nonzero (being the pivots in the LU factorization). As a result, $A$ has a unique LDU factorization $A = LD\hat{U}$, where $L \in \C^{n \times n}$ is unit lower triangular, $D \in \C^{n \times n}$ is diagonal, and $\hat{U} \in \C^{n \times n}$ is unit upper triangular; given by the unique factorization of $U$ as $U = D \hat{U}$. When $A$ is also self-adjoint, we must have $\hat{U} = L^*$, in which case this factorization is called the LDL* factorization (or LDLT factorization if $A$ is real).

Given a self-adjoint $A \in \C^{n \times n}$, we can also derive the LDL* factorization directly: if $$ A = \begin{bmatrix} \alpha & c^* \\ c & B \end{bmatrix} $$ for some $\alpha \in \C$ (in fact, $\alpha \in \R$ since $A$ is self-adjoint), $c \in \C^{n-1}$, and $B \in \C^{(n-1) \times (n-1)}$, then $$ A = \begin{bmatrix} 1 & \vphantom{\frac{c^*}{\alpha}} \\ \frac{c}{\alpha} & I \end{bmatrix} \begin{bmatrix} \alpha & \vphantom{\frac{c^*}{\alpha}} \\ \vphantom{\frac{c}{\alpha}} & B - \frac{cc^*}{\alpha} \end{bmatrix} \begin{bmatrix} 1 & \frac{c^*}{\alpha} \\ \vphantom{\frac{c}{\alpha}} & I \end{bmatrix}, $$ and if $L’ D’ (L’)^*$ is the LDL* factorization of the Schur complement $A’ = B - \frac{cc^*}{\alpha}$, then $$ A = \underbrace{\begin{bmatrix} 1 & \vphantom{\frac{c^*}{\alpha}} \\ \frac{c}{\alpha} & L' \end{bmatrix}}_L \underbrace{\begin{bmatrix} \alpha & \vphantom{\frac{c^*}{\alpha}} \\ \vphantom{\frac{c}{\alpha}} & D' \end{bmatrix}}_D \underbrace{\begin{bmatrix} 1 & \frac{c^*}{\alpha} \\ \vphantom{\frac{c}{\alpha}} & (L')^* \end{bmatrix}}_{L^*} $$ is the LDL* factorization of $A$.

Diagonal pivoting methods

Let $A \in \C^{n \times n}$ be self-adjoint. Just as an LU factorization may fail to exist because of a zero pivot, an LDL* factorization may fail to exist as well. To obtain a nonzero pivot while preserving the symmetry of $A$, we can interchange two rows of $A$ along with the corresponding columns (illustrated below), which amounts to replacing $A$ with $P_1 A P_1^*$ for some permutation matrix $P_1$. $$ \begin{bmatrix} & 1 & \\ 1 & & \\ & & 1 \end{bmatrix} \begin{bmatrix} 0 & a_{12} & a_{13} \\ a_{21} & {\color{cblue} a_{22}} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \begin{bmatrix} & 1 & \\ 1 & & \\ & & 1 \end{bmatrix} = \begin{bmatrix} {\color{cblue} a_{22}} & a_{21} & a_{23} \\ a_{12} & 0 & a_{13} \\ a_{32} & a_{31} & a_{33} \end{bmatrix} $$ However, using a symmetric interchange as such, pivots can only be selected from the diagonal entries of $A$, which could all be zero despite the matrix itself being nonzero. To remedy this, we can use a permutation to move a nonzero off-diagonal entry at position $(i, j)$ to position $(2, 1)$ (illustrated below), which allows us to then perform a $2 \times 2$ block elimination step. $$ \begin{bmatrix} & 1 & \\ & & 1 \\ 1 & & \end{bmatrix} \begin{bmatrix} 0 & a_{12} & a_{13} \\ a_{21} & 0 & a_{23} \\ a_{31} & {\color{cblue} a_{32}} & 0 \end{bmatrix} \begin{bmatrix} & & 1 \\ 1 & & \\ & 1 & \end{bmatrix} = \begin{bmatrix} 0 & a_{23} & a_{21} \\ {\color{cblue} a_{32}} & 0 & a_{31} \\ a_{12} & a_{13} & 0 \end{bmatrix} $$ In general, if $A$ is nonzero, there exists a permutation matrix $P_1$ such that $$ P_1 A P_1^* = \begin{bmatrix} E & C^* \\ C & B \end{bmatrix}, $$ where the pivot $E \in \C^{s \times s}$ is invertible and $s \in \set{1, 2}$, $C \in \C^{(n-s) \times s}$, and $B \in \C^{(n-s) \times (n-s)}$. We then have $$ P_1 A P_1^* = \begin{bmatrix} I & \\ CE^{-1} & I \end{bmatrix} \begin{bmatrix} E & \\ & B - CE^{-1}C^* \end{bmatrix} \begin{bmatrix} I & E^{-1} C^* \\ & I \end{bmatrix}. $$ Continuing symmetric elimination with the Schur complement $A’ = B - CE^{-1}C^*$, we ultimately produce a factorization of the form $PAP^* = LDL^*$, where $P$ is a permutation matrix, $L$ is unit lower triangular, and $D$ is self-adjoint quasi-diagonal (block diagonal with $1 \times 1$ or $2 \times 2$ blocks).

The Bunch–Parlett factorization

Let $\mu_0 := \max_{i,j} \, \abs{a_{ij}} = \norm{A}_{1,\infty}$ and $\mu_1 := \max_{i} \, \abs{a_{ii}}$. The Bunch–Parlett factorization is a diagonal pivoting method that uses a $1 \times 1$ pivot with $\abs{e_{11}} = \mu_1$ whenever $\mu_1 \geq \alpha \mu_0$ and a $2 \times 2$ pivot with $\abs{e_{21}} = \mu_0$ otherwise, where $\alpha \in (0, 1)$ is a constant chosen to minimize an upper bound for $\mu_0' := \max_{i,j} \, \abs{a_{ij}'} = \norm{A'}_{1, \infty}$.

Namely, for a $1 \times 1$ pivot, we have $$ \begin{align*} \mu_0' &\leq \norm{B}_{1,\infty} + \norm{C}_{1,\infty} \norm{E^{-1}}_{\infty,1} \norm{C^*}_{1,\infty} \\ &\leq \mu_0 + \mu_0 \cdot \frac{1}{\mu_1} \cdot \mu_0 \\ &\leq \left(1 + \frac{1}{\alpha}\right) \mu_0, \end{align*} $$ and for a $2 \times 2$ pivot, we have $$ \begin{align*} \mu_0' &\leq \norm{B}_{1,\infty} + \norm{C}_{1,\infty} \norm{E^{-1}}_{\infty,1} \norm{C^*}_{1,\infty} \\ &\leq \mu_0 + \mu_0 \cdot \frac{2(\mu_0 + \mu_1)}{\abs{\det(E)}} \cdot \mu_0 \\ &\leq \mu_0 + \mu_0 \cdot \frac{2(\mu_0 + \mu_1)}{\mu_0^2 - \mu_1^2} \cdot \mu_0 \\ &< \left(1 + \frac{2}{1-\alpha} \right) \mu_0. \end{align*} $$ To choose $\alpha$, we equate the growth factor $(1 + \frac{1}{\alpha})^2$ for two $1 \times 1$ pivots to the growth factor $1 + \frac{2}{1-\alpha}$ for one $2 \times 2$ pivot, which yields $\alpha = \frac{1 + \sqrt{17}}{8} \approx 0.640$.

The Cholesky factorization

Let $A \in \C^{n \times n}$ be (self-adjoint) positive definite. Then $A$ has a unique LDL* factorization $A = LDL^*$ since its principal submatrices are also positive definite, and moreover $D = (L^{-1}) A (L^{-1})^*$ is positive definite. As a result, $A$ has a unique Cholesky factorization $A = \tilde{L} \tilde{L}^*$, where $\tilde{L} \in \C^{n \times n}$ is lower triangular with positive diagonal entries, given by $\tilde{L} = L \sqrt{D}$.

Given a positive definite $A \in \C^{n \times n}$, we can also derive the Cholesky factorization directly: if $$ A = \begin{bmatrix} \alpha & c^* \\ c & B \end{bmatrix} $$ for some $\alpha \in \C$ (in fact, $\alpha \in \R_{> 0}$ since $A$ is positive definite), $c \in \C^{n-1}$, and $B \in \C^{(n-1) \times (n-1)}$, then $$ A = \begin{bmatrix} \sqrt{\alpha} & \vphantom{\frac{c^*}{\sqrt{\alpha}}} \\ \frac{c}{\sqrt{\alpha}} & I \end{bmatrix} \begin{bmatrix} 1 & \vphantom{\frac{c^*}{\sqrt{\alpha}}} \\ \vphantom{\frac{c}{\sqrt{\alpha}}} & B - \frac{cc^*}{\alpha} \end{bmatrix} \begin{bmatrix} \sqrt{\alpha} & \frac{c^*}{\sqrt{\alpha}} \\ \vphantom{\frac{c}{\sqrt{\alpha}}} & I \end{bmatrix}, $$ and if $\tilde{L}' (\tilde{L}')^*$ is the Cholesky factorization of the Schur complement $A’ = B - \frac{cc^*}{\alpha}$, then $$ A = \underbrace{\begin{bmatrix} \sqrt{\alpha} & \vphantom{\frac{c^*}{\sqrt{\alpha}}} \\ \frac{c}{\sqrt{\alpha}} & \tilde{L}' \end{bmatrix}}_{\tilde{L}} \underbrace{\begin{bmatrix} \sqrt{\alpha} & \frac{c^*}{\sqrt{\alpha}} \\ \vphantom{\frac{c}{\sqrt{\alpha}}} & (\tilde{L}')^* \end{bmatrix}}_{\tilde{L}^*} $$ is the Cholesky factorization of $A$.

Previous

Last updated on 2025-06-17