# Assignment 6 [Coding]: Vector Field Decomposition and Design (Due 5/14)

Warning: You cannot use late days on this assignment since it’s the last one.

Please implement the following routines in:

1. projects/vector-field-decomposition/tree-cotree.js:
1. buildPrimalSpanningTree
2. inPrimalSpanningTree
3. buildDualSpanningCotree
4. inDualSpanningCotree
5. buildGenerators
2. projects/vector-field-decomposition/harmonic-bases.js:
1. buildClosedPrimalOneForm
2. compute

In addition, please implement either Hodge Decomposition, or Trivial Connections (on surfaces of genus 0):

Hodge Decomposition: Please implement the following routines in

1. projects/vector-field-decomposition/hodge-decomposition.js:
1. constructor
2. computeExactComponent
3. computeCoExactComponent
4. computeHarmonicComponent

Trivial Connections on Surfaces of Genus 0: Please implement computeConnections in projects/direction-field-design/trivial-connections.js. This file has function signatures for trivial connections on arbitrary surfaces, but for this assignment we are only requiring you to compute the connection form on simply-connected surfaces where you don’t have to worry about the period matrix. You are, of course, welcome to implement the general algorithm if you would like to!

Notes:

• I made some changes to the tests for this assignment, and to the trivial connections viewer. You should update the following files before starting the assignment:
• tests/vector-field-decomposition/test.html
• tests/vector-field-decomposition/test.js
• tests/direction-field-design/sphere.js
• tests/direction-field-design/test.html
• tests/direction-field-design/test.js
• projects/direction-field-design/index.html
• Recall that homology generators are a set of loops which somehow describe all of the interesting loops on a surface. For example, here are the two homology generators for the torus.
• Your buildGenerators function should implement the Tree-Cotree algorithm, which is Algorithm 5 of section 8.2 of the notes.
• In tree-cotree.js the trees are stored using the dictionaries vertexParent and faceParent. You should store the primal spanning tree by storing the parent of vertex v in vertexParent[v]. The root should be its own parent. Similarly, you should store the dual spanning cotree by storing the parent of face f in faceParent[f].
• The Tree Cotree algorithm finds homology generators on the dual mesh. That is to say, you should take each dual edge which is not in either spanning tree, and form a loop by following its endpoint back up the dual cotree until they meet at the root of the dual cotree. Even though we’re thinking of these homology generators as loops on the dual mesh, we still store them as lists of ordinary halfedges, since edges in the dual mesh are in 1-1 correspondence with edges in the primal graph.
• buildClosedPrimalOneForm should use a homology generator to construct a closed primal 1-form as described in section 8.22 of the notes.
• The compute function in HarmonicBases should compute a harmonic basis using Algorithm 6 in section 8.2 of the notes. If you choose to implement Hodge decomposition for the assignment, you are welcome to use your Hodge decomposition code to solve for $d\alpha$. Otherwise, you can just ignore the hodgeDecomposition parameter and directly solve the linear system $\Delta \alpha = \delta \omega$ to find $\alpha$. (Recall that $\delta$ is the codifferential, which we talked a lot about in the Discrete Exterior Calculus assignment).

Notes (Hodge Decomposition):

• The procedure for Hodge Decomposition is given as Algorithm 3 in section 8.1 of the Notes.
• Note that the SparseMatrix class has an invertDiagonal function that you can use to invert diagonal matrices.
• For computeCoExactComponent, you should compute the coexact component $\delta \beta$ of a differential form $\omega$ by solving the equation $d\delta \beta = d\omega$. As stated in the notes, the most convenient way of doing this is to define a dual 0-form $\tilde \beta := *\beta$, and then to solve $d*d \tilde \beta = d \omega$. Then you can compute $\delta \beta$ using the fact that $\delta \beta = *d*\beta = *d\tilde\beta$. When doing these computations, you should keep tract of whether your forms are primal forms or dual forms, recalling that hodge stars take you from primal forms to dual forms, and hodge star inverses take you from dual forms to primal forms. (THis is discussed in detail in section 8.1.3 of the notes.
• Note that the 2-form Laplacian B is not necessarily positive definite, so you should use an LU solver instead of a Cholesky solver when solving systems involving B.

Notes (Trivial Connections):

• The trivial-connection-js file is structured for implementing the full trivial connections algorithm on arbitrary surfaces. Since that’s tricky, we’re only requiring that you compute connections on topological spheres. You should implement this in the computeConnections() function, and it should pass the tests labeled “computeConnections on a sphere”.
• Even though we’re working with spheres, it is still helpful to use the formulation of Trivial connections given in section 8.4.1 of the notes. In particular, you should solve the optimization problem given in Exercise 8.21.
• On a sphere, there are no harmonic 1-forms, so the $\gamma$ part of your Hodge decomposition will always be 0. Furthermore, the sphere has no homology generators, so the problem simplifies to $\min_{\delta \beta} \;\|\delta\beta\|^2\;\text{s.t.}\; d\delta\beta = u$
• Following the notes, we observe that the constraint $d\delta\beta = u$ determines $\beta$ up to a constant, and that constant is annihilated by $\delta$. So you can find the connection 1-form $\delta \beta$ with a single linear solve.

Submission Instructions
Please rename all js files you edited to be txt files and put them in a single zip file called solution.zip. This file and your solution to the written exercises should be submitted together in a single email to Geometry.Collective@gmail.com with the subject line DDG19A6.

Warning: You cannot use late days on this assignment since it’s the last one.

## 13 thoughts on “Assignment 6 [Coding]: Vector Field Decomposition and Design (Due 5/14)”

1. Emma Liu says:

Will you still have office hours the last week of classes?

1. Mark says:

I will still have office hours for the next 2 Mondays

2. Mark says:

The buildGenerators function in TreeCotree should clear the list of generators before it does anything. My tests run buildGenerators multiple times, so if you don’t clear the list of generators you might wind up listing the generators multiple times.

3. leohuang says:

How can I use the code I wrote for DEC in previous homework in hodge-decomposition.
I just called DEC.something and it seems that the code is not linked and does not work.

1. Mark says:

You should be able to use DEC in hodge-decomposition.js. If you email me your code I can take a look.

4. For build Primal SpanningTree, what exactly is the parent of a vertex? Does it mean to the edge connected to that vertex in the spanning Tree?

5. yujiew says:

Hi, I cannot pass the test for vector-field-decomposition when computing the coexact component $\beta$.

In the test.js file, there is one line of code which causes the failure:
let d = hodgeDecomposition.d0T.timesDense(hodgeDecomposition.hodge1.timesDense(my_coexact_component));

It seems that the test function is trying to perform the following computation $d_0^T\star_1\beta$.

According to the equation above used in the test, $d_0^T$ has a dimension $V \times E$, $\star_1$ has a dimension $E \times E$ which requires a coexact component with a dimension $E \times 1$. However, by definition $d_1 \star_1^{-1}d_1^T\star_2 \beta = d_1 w$ should have a dimention $F \times 1$.

I checked my implementation and my output obtained from $\beta = \star_2^{-1}\tilde{\beta}$ did have a dimension $F \times 1$, which matched the definition in the textbook. Did I miss something when calculating the Hodge decomposition?

1. Mark says:

$\beta$ should be $F \times 1$, but computeCoExactComponent is supposed to return $\delta\beta$, which is a 1-form and should thus be $E \times 1$.

6. My buildDealSpanningCotree function times out on checking connectivity. Will this count against my grade? I’m certain that my function is right because it’s the exact same as my primalSpanningTree function with very tiny modifications. Also, will this affect my ability to test my buildGenerators function?