CS 598ANH : Calculus on Meshes
Fall 2005
University of Illinois at Urbana-Champaign, Department of Computer Science
Overview:
This course is an introduction to the
discretization of vector fields and differential forms on meshes (also
known as Discrete Exterior Calculus or DEC) and the applications of
such a discretization. We will do this with the aim of creating and
understanding computational methods for solving partial differential
equations that arise in mechanics and other applications. The
discretization will attempt to follow the smooth calculus on manifolds
which is the language of modern mechanics.
Homeworks:
- Homework 1
(POSTED : Sep 5, 2005; DUE : Sep 20, 2005, 10:45 am)
- Homework 2
(POSTED : Sep 20, 2005; DUE : Oct 4, 2005, 10:45 am)
- Homework 3
(POSTED : Oct 29, 2005; DUE : Nov 8, 2005, 10:45 am)
Data files for HW3:
- mesh_spec.mat for Matlab version 7.0 or newer. Be sure
to save it as a file with .mat extension.
- mesh_spec_v6.mat for Matlab version 6.5 or older.
Be sure to save it as a file with .mat extension.
- If you cannot load the above files please use the ASCII .txt files below. There are 3 files
you will need if you decide to use the ASCII files. Please try the above .mat files first:
ASCII vertex data
ASCII edge data
ASCII triangle data
- Homework 4 (POSTED (on class mailing list) : Nov 9, 2005; DUE : Nov 18, 10:45 am)
- Homework 5 (POSTED (on class mailing list) : Nov 28, 2005; DUE : Dec 8, 10:45 am)
Solutions:
- Solution to HW 1 : posted on class mailing list (October 25, 2005).
- Solution to HW 2 : posted on class mailing list (November 29, 2005).
- Solution to HW 3 : everyone did very well in this so consider your solution to
be the model solution.
Schedule, Papers, Resources:
Textbook/Papers:
There is no prescribed textbook for the discrete side
of things, although my Ph.D thesis
(
Discrete Exterior Calculus, Caltech, 2003) will be useful as a reference for that
part. For the smooth theory, there is an excellent reference book :
Manifolds, Tensor Analysis and Applications by Abraham, Marsden and
Ratiu. The draft 3rd edition is being made available online to this
class in return for finding and reporting typos. Instructions for
accessing the book will be announced in class. About two-thirds of the
class consists of presentations and discussions of papers. The list of
papers is given below.
Outline:
- Preliminaries, Basic real analysis and topology
- Smooth manifolds and Simplicial complexes
- Smooth vector fields, smooth tensors and smooth differential forms
- Discrete differential forms and Whitney forms
- Smooth and discrete exterior derivative, codifferential and Hodge star
- Smooth and discrete Laplace-Beltrami
- Smooth and discrete wedge product
- Smooth and discrete sharp and flat, contraction and Lie derivatives
The rest of the term will be presentations by students and in-class
discussions covering the topics given below. The presentations will be
based on papers that students will read and the list of papers is
given somewhere below on this page. The topics are :
- Computational electromagnetism
- Fluids mechanics
- Computer graphics applications, such as parametrization
- Combinatorial vector fields
- Mimetic methods
- Finite volume methods
- Higher order Whitney forms
- Differential complexes in numerical analysis
- Discrete Hodge theory
Workload:
There will be 2 written homeworks, 3 small programming
assignments and 1 or 2 presentations by each student (depends on
how many students are registered). The programming
assignments will be done in groups of 2.
Grading:
20% homework, 30% programming, 50% presentation. One late
homework or programming assignment will be allowed without penalty.
Reading list:
The presentations will be based on papers that students will read.
Here is a partial list of papers in the various topic areas. The
reference are given in BibTeX format (easiest for me to
copy paste, but probably tedious for you to parse).
- Computational electromagnetism
-
@article{Bossavit1988a,
Author = {Alain Bossavit},
Journal = {IEE Proceedings},
Month = {November},
Number = {8},
Pages = {493--500},
Title = {Whitney forms : a class of finite elements for
three-dimensional computations in electromagnetism},
Volume = {135, Part A},
Year = {1988}}
-
@article{Bossavit1999a,
Author = {Alain Bossavit},
Journal = {J. Japan Soc. Applied Electromagnetism and Mechanics},
Pages = {150--159},
Title = {Computational electromagnetism and geometry : building a
finite-dimensional ``{M}axwell's house'' (Part 1)},
Volume = {7},
Year = {1999}}
-
@article{Bossavit1999b,
Author = {Alain Bossavit},
Journal = {J. Japan Soc. Applied Electromagnetism and Mechanics},
Pages = {294--301},
Title = {Computational electromagnetism and geometry : building a
finite-dimensional ``{M}axwell's house'' (Part 2)},
Volume = {7},
Year = {1999}}
-
@article{Bossavit1999c,
Author = {Alain Bossavit},
Journal = {J. Japan Soc. Applied Electromagnetism and Mechanics},
Pages = {401--408},
Title = {Computational electromagnetism and geometry : building a
finite-dimensional ``{M}axwell's house'' (Part 3)},
Volume = {7},
Year = {1999}}
-
@article{Bossavit2000a,
Author = {Alain Bossavit},
Journal = {J. Japan Soc. Applied Electromagnetism and Mechanics},
Pages = {102--109},
Title = {Computational electromagnetism and geometry : building
a finite-dimensional ``{M}axwell's house'' (Part 4)},
Volume = {8},
Year = {2000}}
-
@article{Bossavit2000b,
Author = {Alain Bossavit},
Journal = {J. Japan Soc. Applied Electromagnetism and Mechanics},
Pages = {203--209},
Title = {Computational electromagnetism and geometry : building
a finite-dimensional ``{M}axwell's house'' (Part 5)},
Volume = {8},
Year = {2000}}
-
@article{Bossavit2000c,
Author = {Alain Bossavit},
Journal = {J. Japan Soc. Applied Electromagnetism and Mechanics},
Pages = {372--377},
Title = {Computational electromagnetism and geometry : building a
finite-dimensional ``{M}axwell's house'' (Part 6)},
Volume = {8},
Year = {2000}}
-
@article{BoKe1999,
Author = {Alain Bossavit and L. Kettunen},
Journal = {Int. J. Numer. Model.},
Pages = {129--142},
Title = {{Y}ee-like schemes on a tetrahedral mesh, with diagonal lumping},
Volume = {12},
Year = {1999}}
-
@article{BoKe2000,
Author = {Alain Bossavit and Lauri Kettunen},
Journal = {IEEE Trans. Mag.},
Month = {July},
Number = {4},
Pages = {861--867},
Title = {{Y}ee-like schemes on staggered cellular grids: a synthesis
between {FT} and {FEM} approaches},
Volume = {36},
Year = {2000}}
-
@unpublished{Bossavit2002a,
Author = {Alain Bossavit},
Title = {On ``generalized finite differences'' : a discretization
of electromagnetic problems},
Year = {2002}}
-
@incollection{Hiptmair2002a,
Author = {Ralf Hiptmair},
Booktitle = {Acta Numerica},
Pages = {237--339},
Publisher = {Cambridge University Press},
Title = {Finite elements in computational electromagnetism},
Year = {2002}}
- Fluids mechanics
-
@unpublished{ElToKaScDe2005,
Author = {Sharif Elcott and Yiying Tong and Eva Kanso and Peter
Schr\"oder and Mathieu Desbrun},
Title = {Stable, Circulation-Preserving, Simplicial Fluids},
Year = {2005}}
- Solid Mechanics
- @unpublished{ArFaWi2004b,
Author = {Douglas N. Arnold and Richard S. Falk and Ragnar Winther},
Keywords = {mixed finite element method, Hellinger-Reissner principle,
elasticity},
Title = {Differential complexes and stability of finite element
methods. II. The elasticity complex},
Url = {http://ima.umn.edu/{\~~}arnold/papers/elascomplexes2d.pdf},
Year = {2004}}
-
@article{LeMaOrWe2003,
Author = {Adrian Lew and Jerrold E. Marsden and Michael Ortiz and
Matthew West},
Journal = {Archive for Rational Mechanics And Analysis},
Pages = {85--146},
Title = {Asynchronous variational integrators},
Volume = {167},
Year = {2003}}
-
@article{CiOrSc2000,,
Author = {Fehmi Cirak and Michael Ortiz and Peter Schr\"oder},
Journal = {International Journal of Numerical Methods in Engineering},
Title = {Subdivision surfaces: a new paradigm for thin-shell finite
element analysis},
Year = {2000}}
- Computer graphics applications, such as parametrization
-
@inproceedings{GuYa2003,
Author = {Xianfeng Gu and Shing-Tung Yau},
Booktitle = {Eurographics Symposium on Geometry Processing},
Editor = {L. Kobbelt and P. Schr\"oder and H. Hoppe},
Publisher = {Eurographics},
Title = {Global Conformal Surface Parameterization},
Year = {2003}}
- @phdthesis{Gu2002,
Author = {Xianfeng Gu},
School = {Harvard University},
Title = {Parametrization for surfaces with arbitrary topology},
Year = {2002}}
- @article{GoGoTh2005,
Author = {S. J. Gortler and C. Gotsman and D. Thurston},
Journal = {Journal of CAGD (to appear)},
Title = {One-Forms on Meshes and Applications to 3D Mesh Parameterization},
Url = {http://www.cs.harvard.edu/{\~~}sjg/papers/tutte.pdf},
Year = {2005}}
-
@inproceedings{MeDeScBa2002,
Author = {Mark Meyer and Mathieu Desbrun and Peter Schr\"oder and
Alan H. Barr},
Booktitle = {International Workshop on Visualization and Mathematics,
VisMath},
Title = {Discrete differential-geometry operators for triangulated
2-manifolds},
Year = {2002}}
- Combinatorial vector fields
-
@article{Forman1998,
Author = {Forman, Robin},
Fjournal = {Mathematische Zeitschrift},
Journal = {Math. Z.},
Number = {4},
Pages = {629--681},
Title = {Combinatorial vector fields and dynamical systems},
Volume = {228},
- Mimetic methods
- @article{MaShSm2000,
Author = {Len G. Margolin and Mikhail Shashkov and Piotr K. Smolarkiewicz},
Fjournal = {Computer Methods in Applied Mechanics and Engineering},
Journal = {Comput. Methods Appl. Mech. Engrg.},
Number = {3-4},
Pages = {365--383},
Title = {A discrete operator calculus for finite difference
approximations},
Volume = {187},
Year = {2000}}
- @article{HySh1999,
Author = {Hyman, James M. and Shashkov, Mikhail},
Fjournal = {SIAM Journal on Numerical Analysis},
Journal = {SIAM J. Numer. Anal.},
Number = {3},
Pages = {788--818 (electronic)},
Title = {The orthogonal decomposition theorems for mimetic finite
difference methods},
Volume = {36},
Year = {1999}}
- @article{HySh1997b,
Author = {Hyman, James M. and Shashkov, Mikhail},
Fjournal = {Applied Numerical Mathematics. An IMACS Journal},
Journal = {Appl. Numer. Math.},
Number = {4},
Pages = {413--442},
Title = {Adjoint operators for the natural discretizations of the
divergence, gradient and curl on logically rectangular grids},
Volume = {25},
Year = {1997}}
- @article{HySh1997a,
Author = {Hyman, J. M. and Shashkov, M.},
Fjournal = {Computers \{\&} Mathematics with Applications. An
International Journal},
Journal = {Comput. Math. Appl.},
Number = {4},
Pages = {81--104},
Title = {Natural discretizations for the divergence, gradient, and curl
on logically rectangular grids},
Volume = {33},
Year = {1997}}
- Finite volume methods
-
@article{Nicolaides1992,
Author = {Nicolaides, R. A.},
Fjournal = {SIAM Journal on Numerical Analysis},
Journal = {SIAM J. Numer. Anal.},
Number = {1},
Pages = {32--56},
Title = {Direct discretization of planar div-curl problems},
Volume = {29},
Year = {1992}}
-
@phdthesis{Trapp2004,
Author = {Kathryn A. Trapp},
School = {Carnegie Mellon University, Department of Mathematics},
Title = {A class of compatible discretizations with applications to
div-curl systems},
Year = {2004}}
- @article{Mattiussi1997,
Author = {Claudio Mattiussi},
Journal = {Journal of Computational Physics},
Title = {An analysis of finite volume, finite element, and finite
difference methods using some concepts from algebraic topology},
Year = {1997}}
- Higher order Whitney forms
-
@article{Bossavit2002d,
Author = {Alain Bossavit},
Journal = {IEEE Trans. Mag.},
Month = {March},
Number = {2},
Pages = {341--344},
Title = {Generating {W}hitney forms of polynomial degree one and higher},
Volume = {38},
Year = {2002}}
-
@incollection{Hiptmair2001b,
Author = {R. Hiptmair},
Booktitle = {Geometric Methods for Computational Electromagnetics},
Chapter = {11},
Editor = {F. L. Teixeira},
Publisher = {EMW Publishing},
Title = {Higher order {W}hitney forms},
Year = {2001}}
- Differential complexes in numerical analysis
-
@unpublished{ArFaWi2004a,
Author = {Douglas N. Arnold and Richard S. Falk and Ragnar Winther},
Keywords = {mixed finite element method, de Rham complex, stability},
Title = {Differential complexes and stability of finite element
methods. I. The de Rham complex},
Url = {http://ima.umn.edu/{\~~}arnold/papers/nacomplexes.pdf},
Year = {2004}}
- Discrete Hodge theory
-
@article{Dodziuk1976,
Author = {Dodziuk, Jozef},
Journal = {Amer. J. Math.},
Number = {1},
Pages = {79--104},
Title = {Finite-difference approach to the {H}odge theory of harmonic
forms},
Volume = {98},
Year = {1976}}
- @article{Hiptmair2001,
Author = {Hiptmair, R.},
Fjournal = {Numerische Mathematik},
Journal = {Numer. Math.},
Number = {2},
Pages = {265--289},
Title = {Discrete {H}odge operators},
Volume = {90},
Year = {2001}}
- @incollection{Hiptmair2001a,
Author = {R. Hiptmair},
Booktitle = {Geometric Methods for Computational Electromagnetics},
Chapter = {10},
Editor = {F. L. Teixeira},
Publisher = {EMW Publishing},
Title = {Discrete {H}odge-operators: An algebraic perspective},
Year = {2001}}
- Mesh Generation and Quality
-
@inproceedings{AlCoYvDe2005,
Author = {Pierre Alliez and David Cohen-Steiner and Mariette Yvinec and
Mathieu Desbrun},
Booktitle = {Proceedings ACM SIGGRAPH},
Title = {Variational Tetrahedral Meshing},
Year = {2005}}
-
@inproceedings{AlCoYvDe2005,
Author = {Pierre Alliez and David Cohen-Steiner and Mariette Yvinec and
Mathieu Desbrun},
Booktitle = {Proceedings ACM SIGGRAPH},
Title = {Variational Tetrahedral Meshing},
Year = {2005}}
-
@inproceedings{Shewchuk2002a,
Author = {Jonathan R Shewchuck},
Booktitle = {Eleventh International Meshing Roundtable },
Title = {What Is a Good Linear Element? Interpolation, Conditioning, and
Quality Measures},
Year = {2002}}
-
@unpublished{Shewchuck2002,
Author = {Jonathan R Shewchuck},
Title = {What is a good linear finite element? {I}nterpolation, conditioning, anisotropy and quality measures},
Year = {2002}}
- Other
-
@article{Forman2002c,
Author = {Forman, Robin},
Fjournal = {International Journal of Mathematics},
Number = {4},
Pages = {333--368},
Title = {Combinatorial {N}ovikov-{M}orse theory},
Volume = {13},
Year = {2002}}
-
@article{PiPo1993,
Author = {Ulrich Pinkall and Konrad Polthier},
Journal = {Experimental Mathematics},
Number = {1},
Pages = {15-36},
Title = {Computing Discrete Minimal Surfaces and Their Conjugates},
Volume = {2},
Year = {1993}}
Page maintained by Anil N. Hirani.