NSD Schedule 2022 Spring 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.
For questions about the course, please send me an email with
the subject line starting with [nsdcourse]
.
Week 
Date 
Subject 
Comments 

1 
2/14 
Introduction and Unit 1: Fundamental Engineering 
hw #1 
2 
2/21 
Unit 2: Python and Numpy 
proposal open 
3 
2/28 
No meeting (228 memorial) 

4 
3/7 
Unit 3: C++ and Computer Architecture 
hw #2 
5 
3/14 
Unit 4: Matrix Operations 

6 
3/21 
Unit 5: Cache Optimization 
hw #3 
7 
3/28 
Unit 6: SIMD (Vector Processing) 

8 
4/4 
No meeting (children’s day) 
proposal due 
9 
4/11 
Midterm examination 

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

12 
5/2 
Unit 9: Modern C++ 
hw #5 
13 
5/9 
Unit 10: C++ and C for Python 
Zoom online only 
14 
5/16 
Unit 11: Array Code in C++ 
Zoom online only; hw #6 
15 
5/23 
Unit 12: Advanced Python 
Zoom online only 
16 
5/30 
Project presentation #1 
Zoom online only 
17 
6/6 
Project presentation #2 
Zoom online only 
18 
6/13 
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 (22sp) 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 22sp).
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