Note: For the final assignment, you can do either this assignment or A5. Overall, you just need to be sure you completed A0 and A1, as well as 3 of the assignments A2–A6 (your choice which ones. See this Piazza post for more details.) Also, you cannot use late days on this assignment since it’s the last one.
Please implement the following routines in:
- projects/vector-field-decomposition/tree-cotree.[js|cpp]:
- buildPrimalSpanningTree
- inPrimalSpanningTree
- buildDualSpanningCotree
- inDualSpanningCotree
- buildGenerators
- projects/vector-field-decomposition/harmonic-bases.[js|cpp]:
- buildClosedPrimalOneForm
- compute
In addition, please implement either Hodge Decomposition, or Trivial Connections (on surfaces of genus 0):
Hodge Decomposition: Please implement the following routines in
- projects/vector-field-decomposition/hodge-decomposition.js:
- constructor
- computeExactComponent
- computeCoExactComponent
- 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:
- 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 submit all source files to Gradescope by 5:59pm ET on May 21, per the usual submission instructions.
Warning: You cannot use late days on this assignment!
The assignment is due on May 6, 2022 at 5:59:59pm Eastern (not at midnight!).