NSD Schedule 2022 Autumn NYCU#
The course introduces the art of building numerical software, i.e., computer programs applying numerical methods for solving mathematical, scientific, or engineering problems. We will be using Python, C++ and other tools (e.g., bash, git, make, etc.) to learn the modern development processes. This is a practical course for making software. The grade composition is: homework 30%, midterm exam 30%, and term project 40%.
Practical skills can only be acquired by practicing, and that is why the project you are requested to define and implement takes 40%. If you are not familiar with selflearning, it will be difficult for you, so I would like to offer additional help. One of the help is the sciwork community. It is set up to help people who want to write scientific code. I understand that it may be difficult for you to initiate a project alone. You might not know exactly where to start or how to effectively discuss. The community is a place you can ask for help. Please join the discord server https://discord.gg/6MAkFrD and follow the rules. (If you simply want to make friends who care about numerical software, welcome too.)
The second thing I would like you to know is the practicing homework assignment (number 0). You are required to submit homework assignments using both GitHub PR and E3. I created the homework #0 to help you practice the use of GitHub, and a demonstration is provided at https://github.com/yungyuc/nsdhw_22au/pull/1. Should you have any questions, file an issue on GitHub, send an email to the grader or me, or send a message in the private telegram chatroom. (Preference is in that order and do not send homework assignments to the sciwork community.)
Should you have any questions about the course, please send me an email with the subject line starting with [nsdcourse]
. Email is a
great tool for serious discussions. Please use more of it.
Week 
Date 
Subject 
Comments 

1 
9/12 
hw #1 

2 
9/19 
Unit 1: Fundamental Engineering 
proposal open 
3 
9/26 
Unit 2: Python and Numpy 

4 
10/3 
Unit 3: C++ and Computer Architecture 
hw #2 
5 
10/10 
No meeting (national day) 

6 
10/17 
Unit 4: Matrix Operations 

7 
10/24 
Unit 5: Cache Optimization 
hw #3 
8 
10/31 
Unit 6: SIMD (Vector Processing) 
proposal due 
9 
11/7 
Midterm examination 

10 
11/14 
Unit 7: Memory Management 
hw #4 
11 
11/21 
Unit 8: Ownership and Smart Pointers 

12 
11/28 
Unit 9: Modern C++ 
hw #5 
13 
12/5 
Unit 10: C++ and C for Python 

14 
12/12 
Unit 11: Array Code in C++ 
hw #6 
15 
12/19 
Unit 12: Advanced Python 

16 
12/26 
Project presentation 

17 
1/2 
No meeting (new year) 

18 
1/9 
To be planned 
Term Project#
The course requires students to develop a software system of a hybrid system of C++11 (modern C++) and Python for a numerical, scientific, or engineering problem. Everyone needs to individually write a proposal, develop the code, and present the project to the class at the end of the course. The grading guidelines are described in Practical Project.
The software needs to be opensource, hosted on github.com, and executable on Ubuntu 20.04 LTS on 64bit x86 through command line. Building the software should use a single command.
The project proposal should be submit through the homework repository. Please follow Proposal Template (22au) and make it work like a specification, which is used to discuss what you want to do and how you will do it. You may also reference a sample project proposal: SimpleArray for MultiDimensional Field (a Sample Project Proposal for 22au).
With your proposal, I can help you manage the development through discussions (at which you should be proactive). A plan will not be be 100% accurate and you should modify it as you go. Use pull requests to keep the proposal uptodate.
You should write prototype code for your project with the proposal. The initial work will help you understand more about what to do. It is difficult to write a proposal without prototyping.
Some possible topics are listed in what follows. They are of real use cases for a project modmesh. You may use a topic derived from them, but also encouraged to come up with an original one.
Contiguous Array#
Multidimensional arrays of fundamental types and struct are a building block for numerical code. It may be as simple as a pointer to a contiguous memory buffer, or welldesigned metadata with the memory buffer. While a mere pointer works well with onedimensional arrays, calculating the pointer offset for multidimensional arrays makes the code for numerical calculation cryptic and hard to maintain. It is very helpful to wrap the multidimensional index calculation in a library.
A handy multidimensional array library should provide the following features:
No more runtime overhead than the calculation of the pointer offset.
Allow safe sharing of the memory buffer to other library and language in the same process. This feature is the socalled zerocopy. Sharing the buffer with other process using OSprovided shared memory should not be forbidden.
Support both fundamental types as well as composite types (struct).
Columnar Array#
There are generally two ways to implement arrays of composite types. One is to pack the composite data and use an array for them, i.e., the socalled array of struct (AoS):
struct Data
{
int m_field1;
double m_field2;
};
SimpleArray<Data> data_array;
The other is to organize arrays of fundamental types, i.e., the socalled struct of arrays (SoA) or the columnar arrays:
struct StructOfArray
{
SimpleArray<int32_t> m_field1;
SimpleArray<double> m_field2;
};
In the columnar array, if the fields are considered as the “rows” in a twodimensional array, the data organization is like the “columnmajor” format. This is why we use the term “columnar” to describe this kinds of data structure. The columnar array (SoA) may provide better cache locality than AoS, especially when there are many fields. For example, if there are 8 fields of doubleprecision floating point, each “row” will totally occupy a cache line of 64 bytes.
Note
The columnar array is usually twodimensional and works like a table.
The requirements of the columnar array library:
A single class template can create the columnar array.
Automatic generate a rowaccessor. The rowaccessor works as a handle (or cursor) over all rows in the array.
References
Graph Partitioning#
Numerical solution of partial differential equations (PDEs) depends on discretization of space. The entities describing the discretized space is called grid or mesh. The mesh can be broadly categorized into structured and unstructured mesh. The latter is more flexible than the former.
The unstructured mesh allows free connectivity, which enables flexible distribution of data for parallel computing. The connectivity between mesh elements can be represented as a graph, and the graph is used for partitioning. The graphpartitioning problem is useful to minimizing the communication between submesh.
The graph partitioning code should support:
Extract a graph from a two or threedimensional unstructured mesh of mixed elements.
Find the subgraphs whose edges across each other are minimized.
Use the subgraphs to decompose the original mesh into interconnected sub meshes.
RTree Search Engine#
Rtree is an index to speed up searches in space. It is usually referred to as a spatial index or just a tree. In onedimensional space, a common search tree may be used because it may use a single key for search. In multipledimensional space, there are intrinsically multiple keys, so the search tree needs to accommodate the dimensionality. Data structures of the similar purpose include kd tree, quadtree, etc.
The requirements of an implementation of the RTree search engine are:
It works in two or threedimensional space and may index point, line, surface, or volume.
Allow dynamic update of elements.
Allow access elements using a serial (integer) identifier.
Support ranged search of the geometrical entities.
References
Voronoi Diagram#
The Voronoi diagram is a decomposition of a region that any point in a subregion is closest to the site of the subregion. A classical example is to determine the service areas of each branch of a reseller chain. Our interest of this problem is to discretize space for mesh generation. It can be used to create triangular mesh in the Delaunay triangulation.
The requirements of the Voronoi diagram code are:
Given geometrical entities in two or threedimensional space, find the Voronoi diagram.
The data structure allows accessing the geometrical entities and the Voronoi diagram using a serial (integer) number. The index access implies the entities and the Voronoi diagram are associated with each other.
Fast searching for nearby entities is supported with a spatial index.
Parametric Description of Curved Geometry#
To describe the smooth geometry of an object in space, Bezier curves are usually used. The spatial discretization may be applied on the objects for numerical calculation.
The requirements of the Bezier code:
Computation mesh can be generated against the curved objects in two or threedimensional space.
The mesh can be associated with the curved geometry, preferably with serial (integer) identifiers.
Boolean Operations on Polygons#
In Euclidean space we are interested in finding the Boolean, i.e., AND, OR, NOT, XOR, of polygons. The polygonal Boolean operations are useful when we want to extract geometrical properties of the graphics. In twodimensional space we deal with polygons. In threedimensional space it is polyhedra.
References