Phorgy Phynance

A Note on Discrete Helmholtz Decomposition

with one comment

The following is a note I sent to my PhD advisor, Professor Weng Cho Chew, on September 13, 2011 after a discussion over dinner as he was headed back to UIUC from a 4-year stint as the Dean of Engineering at the University of Hong Kong.

Decomposing Finite Dimensional Inner Product Spaces

Given finite-dimensional inner product spaces U, V  and a linear map A:U\to V, the adjoint map A^\dagger: V\to U is the unique linear map satisfying the property

\langle Au,v\rangle = \langle u,A^\dagger v\rangle

for all u\in U and v\in V.

In this section, we show that V can be decomposed into two orthogonal subspaces

V = \text{im} A\oplus \text{ker} A^\dagger

This is a fairly simple exercise as any finite-dimensional inner product space can be decomposed into a subspace and its orthogonal complement, i.e.

V = \text{im} A \oplus (\text{im} A)^\perp.

The only thing to show is that (\text{im} A)^\perp = \text{ker} A^\dagger.

To do this, note whenever v\in (\text{im} A)^\perp, then

\langle A u, v\rangle = \langle u,A^\dagger v\rangle = 0

for all u\in U. Thus, v is also in \text{ker} A^\dagger, i.e. (\text{im} A)^\perp \subset \text{ker} A^\dagger. Similarly, whenever v\in\text{ker} A^\dagger, then

\langle u,A^\dagger v\rangle = \langle A u, v\rangle = 0

for all u\in U. Thus, v is also in  (\text{im} A)^\perp, i.e. \text{ker} A^\dagger \subset (\text{im} A)^\perp. Since both (\text{im} A)^\perp \subset \text{ker} A^\dagger and \text{ker} A^\dagger \subset (\text{im} A)^\perp, it follows that (\text{im} A)^\perp = \text{ker} A^\dagger.

Hodge-Helmholtz Decomposition

Given finite-dimensional inner product spaces U, V ,W  and linear maps A:U\to V, B:V\to W such that B\circ A = 0, we wish to show that the inner product space V may be decomposed into three orthogonal subspaces

V = \text{im} A\oplus\text{im} B^\dagger\oplus\text{ker} \Delta,

where \Delta = A\circ A^\dagger + B^\dagger\circ B.

To show this, note that if v\in\text{ker}\Delta, then

\langle \Delta v,v\rangle = \langle A^\dagger v,A^\dagger v\rangle + \langle B v, B v\rangle = 0,

but this implies v\in \text{ker} A^\dagger and v\in\text{ker} B. Conversely, if v\in \text{ker} A^\dagger and v\in\text{ker} B, then v  is trivially in \text{ker}\Delta. In other words,

\text{ker} \Delta = \text{ker} A^\dagger \cap \text{ker} B.

Finally, since B\circ A = 0, we also have A^\dagger\circ B^\dagger = 0. Consequently, when v\in\text{im} B^\dagger, then v\in\text{ker} A^\dagger so

\text{im} B^\dagger \subset \text{ker} A^\dagger.

Applying the decomposition from the previous section twice, we conclude that

V = \text{im} A\oplus \text{ker} A^\dagger

and since \text{im} B^\dagger\subset \text{ker} A^\dagger, it follows that

\text{ker} A^\dagger = \text{im} B^\dagger\oplus \text{ker}A^\dagger\cap\text{ker} B

which may be expressed simply as

\text{ker} A^\dagger = \text{im} B^\dagger \oplus \text{ker} \Delta.

Putting this together we see the desired Hodge-Helmholtz decomposition

V = \text{im} A\oplus\text{im} B^\dagger\oplus\text{ker}\Delta.

Computational Electromagnetics

The preceding discussion is quite general and holds for any finite-dimensional inner product spaces U, V, W and any linear maps A:U\to V, B:V\to W satisfying B\circ A = 0. In this section, we specialize to computational electromagnetics.

Consider a discretization of a surface S consisting of N_0 vertices, N_1 directed edges, and N_2 oriented triangular faces. If we associate a degree of freedom to each vertex, the span of these degrees of freedom form an N_0-dimensional vector space V_0. Associating a degree of freedom to each directed edge forms an N_1-dimensional vector space V_1 and associating a degree of freedom to each oriented face forms an N_2-dimensional vector space V_2. For concreteness, vectors in V_0 will be expanded via

\begin{aligned}\phi = \sum_{i=1}^{N_0} \phi_i \mathbf{v}_i \in V_0,\end{aligned}

where \phi_i denotes the degree of freedom on the ith vertex, vectors in V_1 will be expanded via

\begin{aligned}\alpha = \sum_{i=1}^{N_1} \alpha_i \mathbf{e}_i\in V_1,\end{aligned}

where \alpha_i denotes the degree of freedom on the ith directed edge, and vectors in V_2 will be expanded via

\begin{aligned}\beta = \sum_{i=1}^{N_2} \beta_i \mathbf{f}_i\in V_2,\end{aligned}

where \beta_i denotes the degree of freedom on the ith oriented face.

To turn V_0, V_1, and V_2 into inner product spaces, we need to define three respective inner products. This can be done by defining three sets of basis functions B_0, B_1, and B_2. B_0 and B_2 take values defined at vertices and faces, respectively, and maps these to functions defined over each face. Similarly, B_1 takes values defined along each edge and maps these to vector fields defined over each face.

The basis functions linearly turn vectors in V_0, V_1, and V_2 into functions and vector fields defined over the surface  via

\begin{aligned}\phi = \sum_{i=1}^{N_0} \phi_i \mathbf{v}_i\quad\implies\quad B_0(\phi) = \sum_{i=1}^{N_0} \phi_i B_0(\mathbf{v}_i),\end{aligned}

\begin{aligned}\alpha = \sum_{i=1}^{N_1} \alpha_i \mathbf{e_i} \quad\implies\quad B_1(\alpha) = \sum_{i=1}^{N_1} \alpha_i B_1(\mathbf{e}_i),\end{aligned}

and

\begin{aligned}\beta = \sum_{i=1}^{N_2} \beta_i \mathbf{f}_i \quad\implies\quad B_2(\beta) = \sum_{i=1}^{N_2} \beta_i B_2(\mathbf{f}_i).\end{aligned}

The inner products may then be defined in terms of basis functions via

\begin{aligned}(M_0)_{i,j} = \langle\mathbf{v}_i,\mathbf{v}_j\rangle_0 = \int_S B_0(\mathbf{v}_i) B_0(\mathbf{v}_j) dA,\end{aligned}

\begin{aligned}(M_1)_{i,j} = \langle\mathbf{e}_i,\mathbf{e}_j\rangle_1 = \int_S B_1(\mathbf{e}_i)\cdot B_1(\mathbf{e}_j) dA,\end{aligned}

and

\begin{aligned}(M_2)_{i,j} = \langle \mathbf{f}_i,\mathbf{f}_j\rangle_2 = \int_S B_2(\mathbf{f}_i) B_2(\mathbf{f}_j) dA.\end{aligned}

Letting [\phi], [\alpha], and [\beta] denote column matrix representations of vectors in V_0, V_1, and ,V_2 the inner products may be expressed in terms of matrix-vector products via

\langle \phi,\phi'\rangle_0 = [\phi]^t [M_0] [\phi'],

\langle \alpha,\alpha'\rangle_1 = [\alpha]^t [M_1] [\alpha'],

and

\langle \beta,\beta'\rangle_2 = [\beta]^t [M_2] [\beta'].

The matrix-vector representation is helpful for explicitly expressing the adjoint of a linear map A:V_0\to V_1 via

\langle A\phi,\alpha\rangle_1 = [\phi]^t[M_0]\left([M_0]^{-1} [A]^t [M_1] \right) [\alpha] = [\phi]^t [M_0] [A^\dagger] [\alpha] = \langle \phi,A^\dagger \alpha\rangle_0

so that

[A^\dagger] = [M_0]^{-1} [A]^t [M_1].

Similarly, the adjoint of a linear map B:V_1\to V_2 may be represented in matrix form via

[B^\dagger] = [M_1]^{-1} [B]^t [M_2].

In computational electromagnetics, a fundamental linear map is the exterior derivative, which will be denoted d_i:V_i\to V_{i+1} for i = 0,1. Since V_0, V_1, and V_2 are finite dimensional, d_i has a sparse matrix representation [d_i].

For the sake of interpretation, the matrix [d_0] may be thought of as the gradient along the respective directed edge, [d_1] may be thought of as the curl of the edge vector field around each oriented face, [d_1^\dagger] may be thought of as the transverse gradient[1] across each directed edge, and [d_0^\dagger] may be thought of as the divergence of the edge vector field.

Critically note,

[d_1][d_0] = 0.

As a result, we have the inner product space of edge vector fields V_1 decomposes into

V_1 = \text{im} d_0\oplus \text{im} d_1^\dagger\oplus \text{ker} \Delta,

where \Delta = d_0\circ d_0^\dagger + d_1^\dagger\circ d_1. In other words, any edge vector v\in V_1 may be expressed as

v = d_0\phi + d_1^\dagger\beta + h

for some \phi\in V_0, \beta\in V_2, and h\in \text{ker} \Delta. The above may be thought of as a discrete version of Hodge-Helmholtz decomposition for computational electromagnetics.

References

This note is an informal (and quickly drafted) document intended to help explain Hodge-Helmholtz decomposition in computational electromagnetics. No claim of any original content is intended and a proper literature search was not performed. For pointers to some related material with more complete references, see the following:


[1] If the degree of freedom associated to an oriented face is interpreted as the magnitude of vector normal to the face,  may be thought of as the curl of this normal vector field along the directed edge.

Written by Eric

March 17, 2012 at 6:36 pm

Posted in Uncategorized

One Response

Subscribe to comments with RSS.

  1. […] of the edge vector field around each oriented face,  may be thought of as the transverse gradient[1] across each directed edge, and  may be thought of as the divergence of the edge vector […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: