Cholesky factorization of an arrowhead matrix
The arrowhead example highlights why permutations are crucial when performing factorizations of sparse matrices. The example is from the book Convex Optimization by Stephen Boyd and Lieven Vandenberghe.
We start by defining two arrowhead matrices. One with the arrow pointing towards the top left (\(A_l\)) and one pointing towards the bottom right \((A_r)\)
\[ A_l = \begin{bmatrix} 1 & u^\top\\ u & \text{diag}(d) \end{bmatrix}, \quad A_r = \begin{bmatrix} \text{diag}(d) & u\\ u^\top & 1 \end{bmatrix}, \]where \(\text{diag}(d) \in \mathbb{R}^{n\times n}\) is a positive diagonal matrix and \(u \in \mathbb{R}^n\). In the case where \(u^\top\text{diag}(d)^{-1}u < 1\) the matrix is positive definite and a Cholesky factorization exist. For the left pointing arrowhead matrix the Cholesky factorization can be computed as
\[ A_l = \begin{bmatrix} 1 & u^\top\\ u & \text{diag}(d) \end{bmatrix} = \begin{bmatrix} 1 & 0\\ u & L \end{bmatrix} \begin{bmatrix} 1 & u^\top\\ 0 & L^\top \end{bmatrix}. \]Unfortunately looking at the bottom right block one find that \(LL^\top = \text{diag}(d) - uu^\top\). In general \(uu^\top\) will be dense meaning that \(L\) will also be a dense matrix. Visually we can represent the Cholesky factorization of the left pointing arrowhead matrix as 
Surprisingly, the right pointing arrowhead matrix (which is simply a permutation of the left pointing arrowhead matrix) have a sparse Cholesky
\[ \begin{bmatrix} \text{diag}(d) & u\\ u^\top & 1 \end{bmatrix} = \begin{bmatrix} \text{diag}(d)^{1/2} & 0\\ u^\top \text{diag}(d)^{-1/2} & \sqrt{1 - u^\top \text{diag}(d)^{-1}u} \end{bmatrix} \begin{bmatrix} \text{diag}(d)^{1/2} & \text{diag}(d)^{-1/2}u\\ 0 & \sqrt{1 - u^\top \text{diag}(d)^{-1}u} \end{bmatrix}. \]Note that the above also shows why the constraint of \(u^\top\text{diag}(d)^{-1}u < 1\) was imposed earlier. We can similarly visualize the factorization as
Some Code
In most sparse linear algebra libraries the permutation of rows and columns happens automatically. To illustrate this a short example in Julia is given. We note here that the underlying sparse linear algebra library used in Julia is SuiteSparse (wrapped in SparseArrays.jl).
We start by setting up the problem as
using LinearAlgebra
using SparseArrays
n = 5
u = rand(n)
d = n./rand(n)
D = sparse(1:n,1:n,d)
Al = [1 u'; u D]
Ar = [D u; u' 1]
# Checking if Al and Ar are positive definite
u'*(D\u)0.1581857727942345
Fl_dense = cholesky(Matrix(Al))6×6 LinearAlgebra.LowerTriangular{Float64, Matrix{Float64}}:
1.0 ⋅ ⋅ ⋅ ⋅ ⋅
0.153143 2.26883 ⋅ ⋅ ⋅ ⋅
0.817509 -0.0551806 3.28754 ⋅ ⋅ ⋅
0.295787 -0.0199652 -0.0738882 3.73591 ⋅ ⋅
0.160635 -0.0108426 -0.0401269 -0.0135697 3.67376 ⋅
0.743808 -0.0502059 -0.185805 -0.0628335 -0.0349327 2.39629Now computing the dense factorization of the right pointing arrowhead matrix (which is expected to be sparse)
Fr_dense = cholesky(Matrix(Ar))6×6 LinearAlgebra.LowerTriangular{Float64, Matrix{Float64}}:
2.274 ⋅ ⋅ ⋅ ⋅ ⋅
0.0 3.38811 ⋅ ⋅ ⋅ ⋅
0.0 0.0 3.74838 ⋅ ⋅ ⋅
0.0 0.0 0.0 3.67753 ⋅ ⋅
0.0 0.0 0.0 0.0 2.51747 ⋅
0.0673452 0.241288 0.0789107 0.0436801 0.295459 0.917504In both case our expectations are verified.
We now redo the computations using a sparse factorization
Fl = cholesky(Al)6×6 SparseArrays.SparseMatrixCSC{Float64, Int64} with 11 stored entries:
2.51747 ⋅ ⋅ ⋅ ⋅ ⋅
⋅ 3.67753 ⋅ ⋅ ⋅ ⋅
⋅ ⋅ 3.74838 ⋅ ⋅ ⋅
⋅ ⋅ ⋅ 3.38811 ⋅ ⋅
⋅ ⋅ ⋅ ⋅ 2.274 ⋅
0.295459 0.0436801 0.0789107 0.241288 0.0673452 0.917504Fr = cholesky(Ar)6×6 SparseArrays.SparseMatrixCSC{Float64, Int64} with 11 stored entries:
2.51747 ⋅ ⋅ ⋅ ⋅ ⋅
⋅ 3.67753 ⋅ ⋅ ⋅ ⋅
⋅ ⋅ 3.74838 ⋅ ⋅ ⋅
⋅ ⋅ ⋅ 3.38811 ⋅ ⋅
⋅ ⋅ ⋅ ⋅ 2.274 ⋅
0.295459 0.0436801 0.0789107 0.241288 0.0673452 0.917504Notably the sparse factorization is in both cases found. The reason here being the permutations (which can be extracted from the factorizations using .p)
show(stdout, "text/plain", Fl.p)
show(stdout, "text/plain", Fr.p)6-element Vector{Int64}:
6
5
4
3
2
1
6-element Vector{Int64}:
5
4
3
2
1
6Notice that the permutation heuristic in this case also end up reversing the entries of the diagonal matrix. However, the same final permutation is found for both the left and right pointing arrowhead matrices.
show(stdout, "text/plain", Al[Fl.p,Fl.p])6×6 SparseArrays.SparseMatrixCSC{Float64, Int64} with 16 stored entries:
6.33766 ⋅ ⋅ ⋅ ⋅ 0.743808
⋅ 13.5242 ⋅ ⋅ ⋅ 0.160635
⋅ ⋅ 14.0504 ⋅ ⋅ 0.295787
⋅ ⋅ ⋅ 11.4793 ⋅ 0.817509
⋅ ⋅ ⋅ ⋅ 5.17105 0.153143
0.743808 0.160635 0.295787 0.817509 0.153143 1.0show(stdout, "text/plain", Ar[Fr.p,Fr.p])6×6 SparseArrays.SparseMatrixCSC{Float64, Int64} with 16 stored entries:
6.33766 ⋅ ⋅ ⋅ ⋅ 0.743808
⋅ 13.5242 ⋅ ⋅ ⋅ 0.160635
⋅ ⋅ 14.0504 ⋅ ⋅ 0.295787
⋅ ⋅ ⋅ 11.4793 ⋅ 0.817509
⋅ ⋅ ⋅ ⋅ 5.17105 0.153143
0.743808 0.160635 0.295787 0.817509 0.153143 1.0