Spring 2017 Syllabus

This course concerns scientific libraries as the most effective form of communication for advances in scientific computation. We will learn how to design, implement, test, distribute, and maintain a numerical library for finite element (FEM) computation written in a higher level languages, such as C, Fortran, and Python. Emphasis will be placed solving practical computational problems and providing insight to the user on code accuracy, performance, and tradeoffs. We will also cover basic techniques of algorithm design and implementation, architectural optimization, source management, configuration and build tools, documentation, i/o, and visualization.

Students will learn to write software as a library developer, meaning that they will construct software usable by others. This is a crucial skill for modern computational science, which needs an understandable (modular, hierarchical), extensible, maintainable infrastructure.

Instructor | Matthew G. Knepley |

Class times | 1pm to 1:50pm on Monday, Wednesday, & Friday |

Location | Duncan Hall 1075 |

A course overview and grading policy are available in accordance with Rice academic policy.

Most class time will be occupied by collaborative learning, question and answer time, and group activity. Class notes for CAAM 519 provide background material for this course.

The mathematics textbook to rule them all for FEM is

- The Mathematical Theory of Finite Element Methods by Susanne Brenner and L. Ridgway Scott (Springer) ISBN-10: 0387759336

but some other books which could supplement your reading are

- Numerical Methods for Nonlinear Partial Differential Equations by Sören Bartels (Springer) ISBN-10: 3319137964
- Understanding And Implementing the Finite Element Method by Mark S. Gockenbach (SIAM) ISBN-10: 0898716144
- Finite Elements and Fast Iterative Solvers: with Applications in Incompressible Fluid Dynamics by Howard C. Elman, David J. Silvester, and Andrew J. Wathen (Oxford). ISBN-10: 0198528671

The following books are foundational for the software construction, however we will not follow them in any way, and they are intended for reference and outside reading.

- The C Programming Language (2nd Edition) by Brian W. Kernighan and Dennis M. Ritchie (Prentice Hall) ISBN-10: 0131103628.
- The PETSc Manual, S. Balay, S. Abhyankar, M. Adams, J. Brown, P. Brune, K. Buschelman, V. Eijkhout, W. Gropp, D. Kaushik, M. Knepley, L. Curfman McInnes, K. Rupp, B. Smith, and H. Zhang, ANL-95/11 Rev 3.5, 2015.
- LaTex Companion (Tools and Techniques for Computer Type Setting), 2nd ed., by Frank Mittelbach, Michel Goossens, Johannes Braams, David Carlisle, and Chris Rowley (Addison Wesley Professional) ISBN-10: 0201362996.

The paper is the perfect vehicle for mathematical communication, but not for communication of results in scientific computing. In this arena, it is the numerical library. I will discuss the creation of software libraries.

I will also the three parts of the course, and the associated programming project for each.

Online resources

- Run-time extensibility and librarization of simulation software, Jed Brown, Matthew G. Knepley, and Barry F. Smith, IEEE CSE, 17(1), 38-45, 2015.
- Short talk on Library development

I am out of town.

I go over simple PDE formulations and the finite element method.

Online resources

- From Euler, Ritz, and Galerkin to Modern Computing, Martin Gander, SIAM Review, 54(4), 627–666, 2012.

Read up on FIAT.

Online resources

- Online documentation for FIAT, as part of the FEniCS Project
- Algorithm 839: FIAT, a new paradigm for computing finite element basis functions, ACM TOMS, 30(4), 502–516, 2004. [Compendia]
- Automated generation and symbolic manipulation of tensor product finite elements, SIAM SISC, 38(5), S25–S47, 2016. [arXiv]

I introduce the FIAT and FInAT packages and the computational approach to element development.

I describe the first programming project.

I introduce the Plex framework for mesh representation (see Chapter 7 in CAAM 519 book).

We look at residual calculation on an element, and pointwise physics functions.

Online resources

- Achieving High Performance with Unified Residual Evaluation
- Finite Element Integration on GPUs
- Finite Element Integration with Quadrature on the GPU
- MOOSE: A parallel computational framework for coupled systems of nonlinear equations

We look at residual calculation over a domain.

We discuss progress on the first programming project.

We look at Jacobian calculation over an element.

We discuss handling boundary conditions with PetscSection (see Chapter 7.2.2 in the CAAM 519 book).

We assemble full solutions and local solutions with boundary values.

Students present their first programming project for a new element.

Students present their first programming project for a new element.

We create SNES ex12 from scratch.

We create SNES ex12 from scratch.

We create SNES ex12 from scratch.

I introduce vectorization and technologies for enabling it.

I describe the second programming project.

We discuss vectorization of finite element integrals.

Online resources

- Finite Element Integration with Quadrature on the GPU
- OpenCL is an open standard for SIMT programming, used extensively by ViennaCL and PyOpenCL
- CUDA is the SIMT programming system from Nvidia, which is easily used through PyCUDA
- ISPC is a compiler that inserts Intel intrinsics (also look at non-temporal stores)
- LIBXSMM is a library with Intel JIT compilation for small, dense or sparse matrix multiplications, and small convolutions.
- Example PETSc integration using OpenCL

We run some experiments.

I am out of town.

I am out of town.

I am out of town.

I describe cache tiling (also loop tiling) and show code for this in PETSc.

Online resources

- Loopy, an iteration layout engine, from Andreas Klockner
- The STENCIL computation in the Parboil benchmarks from UIUC shows off cache tiling
- Another approach to this is cache oblivious algorithms, originated by Harald Prokop in his MS thesis, where stuff is recursively chopped up until it fits in cache.

Students present their second programming project on vectorization.

Students present their second programming project on vectorization.

We examine the irregular evaluation needed for particle methods, and look at the design of DMSwarm.

We discuss

- Poisson with a nonlinear boundary condition
- Variable-viscosity Stokes and Navier-Stokes
- Helmholtz
- Magneto-hydrodynamics
- Magama dynamics

We choose formulations for the third programming project, and divide into groups.

We discuss how to design multigrid preconditioners

We discuss the paper by Diskin, Thomas, and Mineck on debugging a multigrid implementation.

Online resources

- On Quantitative Analysis Methods for Multigrid Solutions, SIAM SISC, 27(1), 108–129, 2005.

We discuss parallel considerations when preconditioning.

We discuss the paper review by Dave May illustrating common pitfalls in FEM programming. We also discuss solver issues for group projects.

Online resources

- Interactive comment on “ELEFANT: a user-friendly multipurpose geodynamics code”, Solid Earth Discussions, 6, C877–C893, 2014.

I discuss the PETSc profiling interface.

We discuss how to extract actionable information from complex, practical codes, rather than toy problems. Also, we discuss work-precision discrimination.

I am out of town.

I am out of town.

I am out of town.

Student groups present their third programming project.

Student groups present their third programming project.

We discuss class accomplishments and possible improvements.