Math 625: Spring 2011
Computational Mathematics and C Programming

Course information

Course Description

This is a hands-on computational mathematics course with emphasis on programming in C. The goal is quickly to impart the necessary algorithmic and programming skills to enable the students build moderate- to large-scale application programs and gain a mastery of the C programming language in the context of scientific computing.

Some programming knowledge is assumed. A substantial part of the course will consists of introduction to C with special emphasis on common idioms used in scientific computing. Through the semester the students will gradually build their own computing library and will successively apply it to solve increasingly complex computational projects.

Prerequisites: Math 221 (linear algebra), Math 251 (multivariable calculus)

Syllabus

• Dynamic memory allocation for vectors and matrices
• Linear system and the LU decomposition of matrices
• Haar wavelets applied to the image processing and compression
  • Assorted images for testing
• Minimizing functions of n variables with Nelder-Mead downhill simplex algorithm
  • See Nelder-Mead algorithm for a pretty good description of the algorithm. It is written with the help of Nelder himself.
  • Here is the rank-vertices.c program that I described in class. It is a stand-alone program to test your rank_vertices() function. Fill the blanks in it with your rank_vertices(), compile and run. If your rank_vertices() has problems, you will see diagnostics, otherwise the program silently terminates.
• Analyzing statically indeterminate 2D trusses via minimization of energy. See Math 625: Trusses for details.
• Using the Triangle utility to triangulate a polygonal domain.

  Triangle is installed as a Unix library on the department's machines. To link with your programs, do:

      cc ... your *.o files ... -ltriangle -lm
  

  Here is the stand-alone demo program triangle-demo2.c that I showed you in class.

  Note 1: If you have a Linux machine, you may copy the library to your machine. Here is how:

  1. Copy /usr/local/stow/triangle-1.6/lib/libtriangle.a from the department's machines to the directory /usr/local/lib/ on your machine. (Make that directory if it does not exist.)
  2. Copy /usr/local/stow/triangle-1.6/include/triangle.h from the department's machines to the directory /usr/local/include/ on your machine. (Make that directory if it does not exist.)
  3. This installs Triangle as a Unix library on your machine. Use it in the same way as shown above.
  Alternatively, you may copy the files triangle.c and triangle.h to your project directory and compile and link with your program like any other C code but I like the library method better.

  Note 2: Unfortunately, parts of triangle.c are quite hacky and do not conform to any C standard. Consequently "gcc -Wall -pedantic -std=c89" issues quite a few warnings. Let's hope that these are not fatal. Fixing the problems calls for a major effort which I am not getting into right now.

  Note 3: If you are using triangle as a library, then enter its header as #include <triangle.h>. If you are compiling explicitly with triangle.c and triangle.h, then enter the header as #include "triangle.h".

• Integration over a triangulated mesh

  We use the quadrature method described in the articles:

  1. Mark A. Taylor, Beth A. Wingate, and Len P. Bos. Several new quadrature formulas for polynomial integration in the triangle, arXiv, 2007.
  2. Mark A. Taylor, Beth A. Wingate, and Len P. Bos. A cardinal function algorithm for computing multivariate quadrature points. SIAM Journal on Numerical Analysis, 45(1) 2007, 193–205.

  I have wrapped their quadrature data into a C program in the files twb-quad.c and twb-quad.h. The documentation is in the file twb-quad.h.

  Here is the stand-alone demo program twb-quad-demo.c that I showed you in class.

• Using the UMFPACK library to solve large linear systems with sparse coefficients

  Umfpack is installed as a Unix library on the department's machines. To link with your programs, do:

      cc ... your *.o files ... -lumfpack -lamd -lm
  

  Note 1: The compressed archive file umfpack-4.4.tar.gz contains a copy of the department's installation. If you have a Linux machine, you may unpack the file as follows:

  1. Download the file umfpack-4.4.tar.gz noded above to your machine.
  2. Go the the /usr/local directory on your machine.
  3. Unpack the archive by typing: tar xfz /path/to/umfpack-4.4.tar.gz

  This will unpack the archive into the directories /usr/local/lib and /usr/local/include on your machine. You will need to be superuser to do that last step.

  That finishes the installation. Use it as you would on the department's machines.

  Note 2: Umfpack has quite a few header files, 33 to be exact, all of which are accessed through the “master” header umfpack.h. I have bundled all the header files into the subdirectory /usr/local/include/umfpack. Consequently, include the main header file in your program as: #include <umfpack/umfpack.h>.

  Umfpack comes with two manuals: QuickStart.pdf and UserGuide.pdf. You will find them in the directory /usr/local/stow/umfpack-4.4/share/doc/umfpack on the department's machines.

  Here are the demo files umfpack-demo1.c, umfpack-demo2.c, umfpack-demo3.c, that I showed you in class.

• A finite element solver for elliptic partial differential equations on irregular 2D domains with mixed Dirichlet and Neumann boundary conditions

  To apply prescribed Neumann boundary conditions, we need to integrate on the domain's boundary. Here are Gaussian quadrature tables for this purpose: gauss-quad.h, gauss-quad.c, and here is the demo program that I showed in class: gauss-quad-demo.c.

Textbook

There is no textbook which covers the selection of topics planned for this course. I will provide plenty of reading material from various sources throughout the semester. Students are expected to take detailed notes.

Recommended reading: The C Programming Language by Brian Kernighan and Dennis Ritchie.

It would be a good idea to go over the book's errata collected in the book's website and insert fixes in the book.

You will find much interesting information about the book at http://cm.bell-labs.com/cm/cs/cbook.

Grading method

I will collect and grade the weekly programming assignments. Course grade will be based on cumulative performance on these assignments.

Sample image filtered with Haar wavelets

The original 256×256 image was transformed via Haar wavelets. Then the least significant coefficients were dropped and the image was reconstructed with the remaining coefficients. The relative L² errors of truncation in the three reconstructed images are 2, 3, and 6 percent. The information from the original image retained are 10%, 5%, and 1%, respectively.

Original image	...with 10% of the original information
...with 5% of the original information	...with 1% of the original information

The Official UMBC Honors Code

By enrolling in this course, each student assumes the responsibilities of an active participant in UMBC's scholarly community in which everyone's academic work and behavior are held to the highest standards of honesty. Cheating, fabrication, plagiarism, and helping others to commit these acts are all forms of academic dishonesty, and they are wrong. Academic misconduct could result in disciplinary action that may include, but is not limited to, suspension or dismissal.

For detailed policies on academic integrity consult:

Undergraduate students:

Undergraduate Student Academic Conduct Policy

Graduate students:

Policy and Procedures for Student Academic Misconduct

Author: Rouben Rostamian