Revised Schedule
- Milestone 1(April 22nd): Finish gradient normalization
- Milestone 2(April 26th): Have a working simple parallelized linear solver
- Milestone 3(May 3rd): Optimize linear solver
- Milestone 4(May 9th): Finish up all of coding and work on write up/presentation
Progress
We have kept mostly up to schedule so far. We first read the research paper outlining the heat method for calculating geodesic distance. Then we spent time understanding the starter code which has a sequential implementation of the heat method. At this point we had a decent idea of where and how we wanted to parallelize matrix construction and gradient normalization, but had yet to dive into the hardest part of the project: implementing a parallel linear solver. We finished the matrix construction and we also finished the gradient normalization, albeit with a few small bugs we are currently dealing with. Meanwhile, we have also been looking into how to approach the main task of creating a parallel sparse linear solver (for symmetric positive-definite systems). We have been learning from a research paper that discusses a parallel iterative solution method for this and plan to begin implementation as soon as we fix the bugs.
All in all, we are mostly on track, save the bugs we are currently fixing. The nice to haves are looking like a long shot but the deliverables/final goals are still attainable and will stay the same.
Results
We don’t have any preliminary results because the main bottleneck is still in place and we are still touching up on small bugs in the task of normalizing the gradient.
Demo
For the demo, we plan on showing graphs on the speedup achieved from our implementation relative to the provided sequential implementation. We will go into depth on how the different areas of the algorithm we parallelized affected the speedup of the program.
Refrences
Crane, Keenan. Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow. Rep. Caltech, n.d. Web.
Heath, Michael. Heat PARALLEL DIRECT METHODS FOR SPARSE LINEAR SYSTEMS. University of Illinois, n.d. Web.