CS 3200 - Introduction to Scientific Computing, Spring 2012
Welcome to the CS 3200 - Scientific Computation class webpage. Here you will find the latest class information, assignments, handouts, and other useful information.
Scientific Computation - CS 3200 will present scientific computation relevant to computational science and engineering, with an emphasis on the process of modeling, simulation, visualization and evaluation. Possible topics related to the four areas include: (modeling) continuous and statistical modeling; (simulation) solving and linear and non-linear systems, interpolation and approximation, numerical differential equations; (visualization) scalar and vector field visualization techniques; (evaluation) connection of results back to case-studies of interest from areas such as physics, biology, etc. Basic knowledge of programming, matrix operations, and calculus.
Class Personnel:
Instructor:
Chris Johnson
Email: crj at sci dot utah dot edu
Office: WEB 3850
Office Hours: MW Noon - 1:00 p.m. and by appointment
Email: crj at sci dot utah dot edu
Office: WEB 3850
Office Hours: MW Noon - 1:00 p.m. and by appointment
TA: Alex Stuart
Email: alex at cs dot utah dot edu
Office: MEB 3115
Office Hours: T, TH 2:00 - 3:00 p.m.
Email: alex at cs dot utah dot edu
Office: MEB 3115
Office Hours: T, TH 2:00 - 3:00 p.m.
TA: Chris Gritton
Email: Chris.Gritton at utah dot edu
Office: CADE Lab
Office Hours: M, W 12:00 - 1:00 p.m.
Email: Chris.Gritton at utah dot edu
Office: CADE Lab
Office Hours: M, W 12:00 - 1:00 p.m.
TA: Raghav Aggarwal
Email: raghav.aggarwal at utah dot edu
Office: TBA
Office Hours: TBA
Email: raghav.aggarwal at utah dot edu
Office: TBA
Office Hours: TBA
Course Mechanics and Resources:
- Course Syllabus
- Time and Place: 1:25 - 2:45 p.m. Mondays and Wednesdays in WEB L103
- Class Email List: You must subscribe to the CS 3200 class email list (cs3200@list.eng.utah.edu). To subscribe to the CS 3200 email list, send email to sympa@list.eng.utah.edu with the subject line of "subscribe cs3200 Your-Email-Address-Here".
- Asking Questions: For questions for the instructors of TA, please send email to: teach-cs3200@list.eng.utah.edu.
- College of Engineering Guidelines
- Web Handin for assignment submission
- Data Directory
- Code Directory
Class Schedule:
SCI Institute Distinguished Lecture Schedule
- Usually occur on Friday at 2:00 pm in WEB 3760
- Most up to date scheduling information
| Date | Speaker |
|---|---|
| Jan 20 | Gene Myers - Janelia Howard Hughes Medical Institute Research Campus |
| Jan 27 | Scott Delp - Stanford University |
| Feb 10 | Jack Dongarra - University of Tennessee/ORNL |
| Feb 24 | David Lipman - NIH National Center for Biotechnology Information (NCBI) - Postponed until next year. |
| Mar 2 | Stephen Smith - Stanford University |
| Mar 23 | Heinz-Otto Peitgen - Fraunhofer MEVIS - Institute for Medical Image Computing |
| Apr 6 | Ben Santer - LLNL |
| Apr 13 | Fran Berman - Rensseaer Polytechnic Institute |
SCI Institute Image Lunch
- Usually occur on Monday at 12:30pm in WEB 3760
- Most up to date scheduling information
SCI Institute VisLunch
- Usually occur on Friday at 12:00pm in WEB 3760
- 'Official' VisLunch Spring 2012 Schedule
- Most up to date scheduling information
References and On-Line Resources:
Because there does not exist a single book that covers all the materials we will cover in this class, we will use a combination of class notes, class lecture slides, and books and other references. Here is a list of those additional books and on-line resources that cover many of the topics covered in CS 3200.
Books:
- Numerical Computing with Matlab This book is a very nice overview of numerical analysis with several examples using Matlab. The book is available for free on-line. The Matlab codes used in the book are also available on-line.
- Scientific Computing: An Introductory Survey, Second Edition by Michael T. Heath, published by McGraw-Hill, New York, 2002.
- Guide To Scientific Computing, Second Edition by Peter R. Turner, published by CRC Press, 2000.
- Introduction to Computational Science: Modeling and Simulation for the Sciences by Angela B. Shiflet and George Shiflet, Princeton University Press, 2006.
- Scientific Computing with MATLAB by Alfio Quarteroni and Fausto Saleri, Springer, 2003.
- MATLAB Guide by Desmond J. Higham and Nicholas J. Higham, SIAM Press, 2005.
- Mastering MATLAB 7 by Duane C. Hanselman and Bruce L. Littlefield, Prentice Hall, 2004.
- Octave - an open source, freely available alternative to Matlab
- The Visualization Handbook. edited by Charles Hansen and Chris Johnson, Academic Press, 2004.
- Visualization Toolkit 4th Edition by Will Schroeder, Ken Martin and Bill Lorenson, Kitware, 2006.
- The Nature of Mathematical Modeling by Neil Gershenfeld, Cambridge University Press, 1998.
- Python Scripting for Computational Science by Hans Petter Langtangen, Springer, 2004.
- Python Essential Reference (3rd Edition) by David M. Beazley, Sams, 2006.
- SCIRun Software System: A scientific problem solving environment for modeling, simulation and visualization developed by the Scientific Computing and Imaging Institute at the University of Utah.
- Links to Scientific Computing Software collected by Michael Heath of UIUC.
- Links to large integer arithmetic packages
- Parallel Scientific Computing in C++ and MPI: A Seamless Approach to Parallel Algorithms and their Implementation by George Em Karniadakis and Robert M. Kirby, Cambridge University Press, 2003.
- Scientific Parallel Computing by L. Ridgway Scott, Terry Clark, Babak Bagheri, Princeton University Press, 2005.
- Introduction to High-Performance Scientific Computing by Lloyd D. Fosdick, Elizabeth R. Jessup, Carolyn J. C. Schauble, and Gitta Domik, MIT Press, 1996.
Tools:
gnuplot
- gnuplot homepage: http://www.gnuplot.info
- Documentation on gnuplot site includes FAQ, manual (comprehensive reference, but no tutorial), and reference card: http://www.gnuplot.info/documentation.html
- Gnuplot Not So Frequently Asked Questions shows lots of examples. Great resource to start from: http://t16web.lanl.gov/Kawano/gnuplot/index-e.html
- Brief tutorial developed by IBM: http://www.ibm.com/developerworks/library/l-gnuplot/
MATLAB
- Look at the Plot Catalog in MATLAB to view the various types of plots, or see the online documentation here: http://www.mathworks.com/access/helpdesk/help/techdoc/creating_plots/f9-53405.html
- Tutorials from MathWorks (developer of MATLAB), with links to other tutorials: http://www.mathworks.com/academia/student_center/tutorials/launchpad.html
- Users Guide (command, language, and object reference): http://www.mathworks.com/access/helpdesk/help/techdoc/matlab_product_page.html
- Good tutorial on the basics of matrix and vector operations and programming (very little on plotting): http://amath.colorado.edu/computing/Matlab/Tutorial/
- Tutorial focused on plotting basics: http://www.engin.umich.edu/group/ctm/extras/plot.html
SciPy
- http://www.enthought.com/products/epd.php
- SciPy tutorial: http://www.scipy.org/SciPy_Tutorial
- NumPy tutorial: http://www.scipy.org/Tentative_NumPy_Tutorial
- matplotlib tutorial (2D plots): http://matplotlib.sourceforge.net/users/pyplot_tutorial.html
- mlab documentation (3D plots): http://code.enthought.com/projects/mayavi/docs/development/html/mayavi/mlab.html
- Python documentation: http://www.python.org/doc/
Enthought Python Distribution (EPD), which includes the NumPy, SciPy, matplotlib, mlab, Mayavi2, and other libraries, plus useful tools such as the IPython interpreter shell (with features such as code completion). Free for academic use.
Tutorials (some slightly out of date):
Mathematical Topics
General Resources
- Online numerical analysis text covering a variety of topics: https://ece.uwaterloo.ca/˜dwharder/NumericalAnalysis/Contents/
- Another set of numerical analysis notes with a wealth of other resources: http://numericalmethods.eng.usf.edu/
- Extensive collection of applets for scientific computing concepts and methods: http://www.cse.illinois.edu/iem/
Fundamentals
Random Numbers
- Wikipedia overview of random number generation: http://en.wikipedia.org/wiki/Random_number_generator
- Site providing an RNG, formerly using lava lamps: http://www.lavarnd.org/what/index.html
- Overview of RNG capabilities in MATLAB
- Reference material for the C libraries rand function
Errors
- Some disasters attributable to bad numerical computing
- Tool for analyzing IEEE-754 floating-point numbers
- The double pendulum - an example of a chaotic system
- Online numerical analysis text covering absolute vs. relative error and issues with floating-point representation in the first two chapters:
- https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/Contents/
- Topics from a set of numerical analysis notes with other resources: Measuring errors — http://numericalmethods.eng.usf.edu/mws/gen/01aae/mws_gen_aae_spe_measuringerror.pdf
- Round-off and truncation error — http://numericalmethods.eng.usf.edu/mws/gen/01aae/mws_gen_aae_spe_sourcesoferror.pdf
Floating-point representation — http://numericalmethods.eng.usf.edu/mws/gen/01aae/mws_gen_aae_spe_floatingpoint.pdf
Vector and Matrix Basics
- BLAS - Basic Linear Algebra Subprograms
- MITs OpenCourseWare project—video lectures, assignments with solutions, and other materials for their Linear Algebra course: http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/
- Extensive online linear algebra notes with many examples, starting with linear systems, vectors, and matrices: http://tutorial.math.lamar.edu/classes/linalg/linalg.aspx
Interpolation
- An applet illustrating the benefit of using splines instead of a single polynomial: http://terpconnect.umd.edu/˜petersd/interp.html
- A more full-featured applet, with a wider range of interpolations methods but a little harder to use: http://www.isaacdooley.com/java/ctd/index.html
- Direct interpolation (linear, quadratic, cubic) — http://numericalmethods.eng.usf.edu/mws/gen/05inp/mws_gen_inp_txt_direct.pdf
- Lagrange interpolation — http://numericalmethods.eng.usf.edu/mws/gen/05inp/mws_gen_inp_txt_lagrange.pdf
- Spline interpolation — http://numericalmethods.eng.usf.edu/mws/gen/05inp/mws_gen_inp_txt_spline.pdf
Topics from a set of numerical analysis notes with other resources:
Numerical Solution Techniques
Forward Euler
- Brief explanation of Forward Euler and other numerical methods for solving ODEs, with a MATLAB example: http://www.mccormick.northwestern.edu/docs/efirst/ode.pdf
- In-depth notes on Forward Euler. Focuses more on mathematical than computational issues, but includes pseudocode: http://tutorial.math.lamar.edu/Classes/DE/EulersMethod.aspx
Monte Carlo
- Demo of computing π by a Monte Carlo approximation: http://polymer.bu.edu/java/java/montepi/
- Links to more examples of finding π by using Monte Carlo approximations: http://math.fullerton.edu/mathews/n2003/montecarlopi/MonteCarloPiBib/Links/MonteCarloPiBib_lnk_1.html
- Another set of overview slides for Monte Carlo integration, with sample code in C (skip to page 5 for the relevant part): http://www.sph.umich.edu/csg/abecasis/class/2006/615.22.pdf
- Notes on both the theoretical basis and practical issues of Monte Carlo integration, by a student here at the UofU SoC: http://www.cs.utah.edu/˜edwards/research/mcIntegration.pdf
- Brief overview, with a finance example: http://www.brighton-webs.co.uk/montecarlo/concept.asp
- Detailed treatment of the mathematical background, but from a scientific computing perspective: http://www.cs.nyu.edu/courses/fall06/G22.2112-001/MonteCarlo.pdf
Numerical Integration
Topics from a set of numerical analysis notes with other resources:
- Trapezoidal rule — http://numericalmethods.eng.usf.edu/mws/gen/07int/mws_gen_int_txt_trapcontinuous.pdf
- Simpson's rule — http://numericalmethods.eng.usf.edu/mws/gen/07int/mws_gen_int_txt_simpson13.pdf
- Gaussian quadrature — http://numericalmethods.eng.usf.edu/mws/gen/07int/mws_gen_int_txt_gaussquadrature.pdf
- Another set of numerical analysis slides, including other topics besides integration: http://homedir.jct.ac.il/˜naiman/nm/nm-slides-color.pdf#page=082
1D Finite Difference Method; Heat Equation
- Notes on the 1D heat equation and the finite difference method: http://web.cecs.pdx.edu/˜gerry/class/ME448/codes/FDheat.pdf
- Another set of notes, with MATLAB examples: http://www.math.umd.edu/undergraduate/schol/matlab/pde.html
- Notes and other resources on the finite difference method, for the ODE case: http://numericalmethods.eng.usf.edu/mws/gen/08ode/mws_gen_ode_spe_finitedif.pdf
2D Finite Difference Method; Poisson's Equation
- Notes and MATLAB examples on applying the finite difference method, for Poissons equation: http://www.mathematik.uni-stuttgart.de/ians/nmh/teaching/projects/schmid/finite_difference_method.shtml
Iterative Solvers
- Jacobi and Gauss-Seidel examples from the online chapters of a linear algebra text: http://college.cengage.com/mathematics/larson/elementary_linear/5e/students/ch08-10/chap_10_2.pdf
- Another resource for the mathematical background, with pseudocode: http://netlib.org/linalg/html_templates/node9.html
- A good online text for iterative methods (see Chapter 4 for Jacobi, Gauss-Seidel, and SOR): http://www-users.cs.umn.edu/˜saad/IterMethBook_2ndEd.pdf
- Nice applet illustrating the Jacobi, Gauss-Seidel, and SOR methods: http://faculty.pepperdine.edu/dstrong/Java/IterativeMethods/
Steepest Descent and Conjugate Gradient Method
- Shewchuks introduction to steepest descent and conjugate gradient: http://www.cs.cmu.edu/˜quake-papers/painless-conjugate-gradient.pdf
- Another set of slides on CG, with information on preconditioners: http://www.stanford.edu/class/ee364b/lectures/conj_grad_slides.pdf
- A good online text for iterative methods (see section 5.3 for steepest descent and 6.7 for CG): http://www-users.cs.umn.edu/˜saad/IterMethBook_2ndEd.pdf
- Applets illustrating the steepest descent and CG methods: http://www.cse.illinois.edu/iem/optimization/SteepestDescent/
- http://www.cse.illinois.edu/iem/optimization/ConjugateGradient/
Scientific Visualization
Meshing
- Wikipedia overview of quadtrees (very basic): http://en.wikipedia.org/wiki/Quadtree
- Jonathan Shewchuk – Triangle (C). Mesh generation tool freely available for non-commercial use. http://www.cs.cmu.edu/˜quake/triangle.html
- Jonathan Shewchuk – ShowMe (C). Mesh visualization tool freely available for non-commercial use: http://www.cs.cmu.edu/˜quake/showme.html
- Another look at meshing, from a topological viewpoint: http://www.cs.mtu.edu/˜shene/COURSES/cs3621/SLIDES/Mesh.pdf
- Notes on the point in polygon problem, with C and FORTRAN code: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
Delaunay Triangulation and Voronoi Diagrams
- Jonathan Shewchuk – Triangle (C). Mesh generation tool freely available for non-commercial use: http://www.cs.cmu.edu/˜quake/triangle.html
- Jonathan Shewchuk – ShowMe (C). Mesh visualization tool freely available for non-commercial use: http://www.cs.cmu.edu/˜quake/showme.html
- Python – scikits.delaunay (not available on the CADE lab Python installations): http://scikits.appspot.com/delaunay
- Wikipedia overview of Voronoi diagrams: http://en.wikipedia.org/wiki/Voronoi_diagram
- Another illustration of Voronoi diagrams and Delaunay triangulation: http://www.comp.lancs.ac.uk/˜kristof/research/notes/voronoi/
- QHull – Another set of tools for computing Delaunay triangulations, Voronoi diagrams, and convex hulls: http://www.qhull.org/
- Two libraries with properties, algorithms, and representations for Delaunay triangulations and Voronoi diagrams: http://www.cgal.org/ http://www.algorithmic-solutions.info/leda_guide/geometryalgorithms.html
- Neat Java applet visualizing the construction of a convex hull in 2D or 3D: http://www.cse.unsw.edu.au/˜lambert/java/3d/hull.html
- Repository of links to a variety of computational geometry algorithms, including Delaunay triangulations, Voronoi diagrams, and convex hulls: http://www.cs.sunysb.edu/˜algorith/major_section/1.6.shtml
- Mathematical and formal material on Delaunay triangulations, from an online chapter of a computational geometry text: http://www.cs.uu.nl/geobook/interpolation.pdf
Points Inside Triangles
- Another look at the same-side and barycentric approaches, with pseudocode for each: http://www.blackpawn.com/texts/pointinpoly/default.html
Scalar Field Visualization
- Wikipedia overview of scalar fields: http://en.wikipedia.org/wiki/Scalar_field
- Wikipedia overview of octrees (very basic): http://en.wikipedia.org/wiki/Octree
- Another introduction to the marching cubes algorithm: http://users.polytech.unice.fr/˜lingrand/MarchingCubes/accueil.html
- Overview and C code for marching cubes: http://paulbourke.net/geometry/polygonise/
- A Survey of Octree Volume Rendering Methods, including the min-max flavor. Can’t access directly via URL; Google “survey octree volume rendering methods”, first result points to correct PDF (as of December 22, 2011). Wikipedia overviews of binary space partitioning and another data structure used in visualization, the kd-tree: http://en.wikipedia.org/wiki/Binary_space_partitioning http://en.wikipedia.org/wiki/Kd-tree
Volume Rendering
- Wikipedia overview of volume rendering and various related topics (ray casting, splatting, texture mapping): http://en.wikipedia.org/wiki/Volume_rendering
- http://en.wikipedia.org/wiki/Volume_ray_casting
- http://en.wikipedia.org/wiki/Texture_splatting
- http://en.wikipedia.org/wiki/Texture_mapping
- Extensive background material on volume rendering (nothing on transfer functions though): http://www.byclb.com/TR/Tutorials/volume_rendering/Index.aspx
- Volume rendering tutorial (specifically on ray casting), with examples and code: Basics – http://graphicsrunner.blogspot.com/2009/01/volume-rendering-101.html
- Transfer functions –
- Optimization – http://graphicsrunner.blogspot.com/2009/02/volume-rendering-201-optimizations.html
- Older but still useful material on the ray casting approach, with theory, examples, and pseudocode: http://web.cs.wpi.edu/˜matt/courses/cs563/talks/powwie/p1/ray-cast.htm
Vector Field Visualization
- Wikipedia overview giving mathematical background on advection: http://en.wikipedia.org/wiki/Advection
- Wikipedia overview of metaballs: http://en.wikipedia.org/wiki/Metaballs
- Resources for image-based flow visualization: http://www.win.tue.nl/˜vanwijk/ibfv/ibfv.exe
- Mathematical background and a basic applet illustrating the differences among streamlines, streaklines, and pathlines: http://web.mit.edu/fluids-modules/www/potential_flows/LecturesHTML/lec02/tutorial/tutorial-spsl.html
- Examples and background for many flow visualization techniques: Home page – http://www.zhanpingliu.org/Research/FlowVis/FlowVis.htm
- Line intregral convolution – http://www.zhanpingliu.org/research/flowvis/LIC/LIC.htm
- Many other examples there, including streamlines, streaklines, etc. Series of tutorial videos on visualizing volume data (both scalar and vector). Specific to MATLAB, but illustrates useful concepts for any platform. http://blogs.mathworks.com/videos/2009/10/23/basics-volume-visualization-19-defining-scalar-and-vector-fields/
People:
Here are some links to some of the mathematicians, computer scientists, scientists, and engineers that we will mention during the course:
Disability Notice:
The University of Utah seeks to provide equal access to its programs, services and activities for people with disabilities. If you will need accommodations in the class, reasonable prior notice needs to be given to the Center for Disability Services, 162 Olpin Union Building, 581-5020 (V/TDD). CDS will work with you and the instructor to make arrangements for accommodations. All written information in this course can be made available in alternative format with prior notification to the Center for Disability Services.