Software for Numerical Methods for Partial Differential Equations
This software was developed for and by the students in CS 615, Numerical Methods for
Partial Differential Equations in 2000, 2003, 2005, 2008, 2010, 2012, and now 2014. Its goal is to implement the
finite element method in two dimensions. It is written in Scheme, and uses some features of
Gambit,
the Scheme->C compiler written by Marc Feeley. It uses Meroon, developed by Christian Queinnec, as its
object system.
Note:
This software is a work in progress. While much of it works as intended, much of it has not yet even
been tested.
The code is coming along nicely and passes the tests in final-tests.scm and test-parabolic.scm.
Note that with the infrastructure that we have built, it is trivial to compute
things like the L2 and H1 norms of the error.
Timing and accuracy results are available for the multigrid code applied
to problems of varying difficulty in the file mg-results.
Some results on bigger problems can be found in mg-results2.
Timing and accuracy results are available for the conjugate-gradient code applied
to problems of varying difficulty in the file cg-results.
The file parabolic.scm contains a solver for parabolic differential equations,
and the file mmoc.scm contains a solver for
transport-dominated diffusion problems. The last two files on this page were used to produce this HTML file.
A gzipped tarball of all the sources can be found here. A short article describing the process of software
development can be found here.
Changelog
all.scm
- Includes:
- utilities.scm
- sort.scm
- linear-algebra.scm
- sparse-linear-algebra.scm
- points.scm
- geometry.scm
- geometry-code.scm
- linear-elements.scm
- linear-elements-code.scm
- problem-descriptions.scm
- conjugate-gradient.scm
- intergrid.scm
- multigrid.scm
- parabolic.scm
- dirichlet.scm
utilities.scm
- Generic functions:
- (check-same-class (x Object) y)
- Functions:
- (reverse-append! xrev y)
- (keep p l)
- (mappend1 f l)
- (reduce-from-left op id l)
- (reduce-from-right op id l)
- (vector-for-each f v1 #!optional (v2 c#absent-object) #!rest vs)
- (vector-for-each-with-index f v1 #!optional (v2 c#absent-object) #!rest vs)
- (vector-map f v1 #!optional (v2 c#absent-object) #!rest vs)
- (unique equal l)
- (unique-with-count equal l)
- Other objects:
sort.scm
- Functions:
- (sorted? seq less?)
- (merge a b less?)
- (merge! a b less?)
- (sort! seq less?)
- (sort seq less?)
linear-algebra.scm
- Classes:
- Operator
- Blocked-vector
- Matrix-operator
- Generic functions:
- (Vector-add (x) y)
- (Vector-subtract (x) y)
- (Vector-scale x (y))
- (Vector-*axpy a (x) y)
- (Vector-copy (x))
- (Lattice-max (x) y)
- (Lattice-min (x) y)
- (Vector-dimension (x))
- (Vector-zero (x))
- (Vector-dot-product (x) y)
- (Vector-inner-product (x) (operator Operator) y)
- (Vector-L2-norm (x))
- (Vector-Linf-norm (x))
- (Vector-L1-norm (x))
- (Operator-compose (op1 Operator) (op2 Operator))
- (Operator-adjoint (op Operator))
- (Operator->identity (op Operator))
- Methods:
- (Vector-add (x Blocked-vector) y)
- (Vector-subtract (x Blocked-vector) y)
- (Vector-scale a (x Blocked-vector))
- (Vector-*axpy a (x Blocked-vector) y)
- (Vector-copy (x Blocked-vector))
- (Vector-zero (x Blocked-vector))
- (Lattice-max (x Blocked-vector) y)
- (Lattice-min (x Blocked-vector) y)
- (initialize! (op Matrix-operator))
- Functions:
- Other objects:
sparse-linear-algebra.scm
- Classes:
- Sparse-matrix
- Sparse-matrix-operator
- Operator-with-matrix-implementation
- Methods:
- (check-same-class (m Sparse-matrix) n)
- (Vector-add (m Sparse-matrix) n)
- (Vector-subtract (m Sparse-matrix) n)
- (Vector-scale a (m Sparse-matrix))
- (Vector-*axpy a (m Sparse-matrix) n)
- (Operator-adjoint (m Sparse-matrix))
- (Operator-compose (m Sparse-matrix) (n Sparse-matrix))
- (initialize! (m Sparse-matrix-operator))
- (->Sparse-matrix (m Sparse-matrix-operator))
- (->Sparse-matrix-operator (m Sparse-matrix))
- (Vector-add (m Sparse-matrix-operator) n)
- (Vector-subtract (m Sparse-matrix-operator) n)
- (Vector-scale a (m Sparse-matrix-operator))
- (Vector-*axpy a (m Sparse-matrix-operator) n)
- (Vector-Linf-norm (m Sparse-matrix-operator))
- (Operator->identity (m Sparse-matrix-operator))
- (Operator-compose (op1 Sparse-matrix-operator) (op2 Sparse-matrix-operator))
- (Operator-adjoint (m Sparse-matrix-operator))
- Functions:
- (Sparse-vector-add x-entries y-entries)
- (Sparse-vector-subtract x-entries y-entries)
- (Sparse-vector-scale x y-entries)
- (Sparse-vector-*axpy a x-entries y-entries)
- (Sparse-matrix-operator-increment-entry m i j value)
- Other objects:
- Local macros:
- (make-Entry index coefficient)
- (Entry-index e)
- (Entry-coefficient e)
- (add-to-entry-list e l)
- (setup-indices)
points.scm
- Functions:
- (make-Point x y)
- (Point-x p)
- (Point-y p)
- (Point-x-set! p val)
- (Point-y-set! p val)
- (Point? p)
- (Point-add p1 p2)
- (Point-subtract p1 p2)
- (Point-scale x p)
- (Point-*axpy a p1 p2)
- (Point-dot-product p1 p2)
- (Point-cross-product p1 p2)
- (Point-counter-clockwise? p1 p2 p3)
- (Point-L2-norm p)
- (Point-zero)
geometry.scm
- Classes:
- Vertex
- Boundary-vertex
- Edge
- Boundary-edge
- Triangle
- Triangulation
- Curved-edge
- Triangle-with-curved-side
- Methods:
- (initialize! (t Triangulation))
- Functions:
- (Vertex-for-each-edge proc v)
- (Vertex-edges<-list l)
- (Vertex-edges->list e)
- (Vertex-edges-length v)
- (Vertex-contains-edge? v e)
- (Boundary-vertex-for-each-boundary-edge proc v)
- (Boundary-vertex-boundary-edges<-list l)
- (Boundary-vertex-boundary-edges->list e)
- (Boundary-vertex-boundary-edges-length v)
- (Boundary-vertex-contains-boundary-edge? v e)
- (Edge-for-each-vertex proc e)
- (Edge-contains-vertex? e v)
- (Edge-length e)
- (Triangle-for-each-vertex proc t)
- (Triangle-for-each-edge proc t)
- (Triangle-contains-vertex? t v)
- (Triangle-contains-edge? t e)
- (Triangle-area t)
- (make-limits #!optional (x-max -inf.0) (x-min +inf.0) (y-max -inf.0) (y-min +inf.0))
- (x-min limits)
- (x-min-set! limits val)
- (x-max limits)
- (x-max-set! limits val)
- (y-min limits)
- (y-min-set! limits val)
- (y-max limits)
- (y-max-set! limits val)
- (Triangulation-Hilbert-curve-sort! t)
- (Triangulation-z-curve-sort! t)
- (Triangulation-Gray-code-curve-sort! t)
- (Triangulation-Sierpinski-curve-sort! t)
- (Triangulation-lexicographical-sort! t)
- (Triangulation-vertices<-list l)
- (Triangulation-vertices->list v)
- (Triangulation-vertices-length t)
- (Triangulation-boundary-vertices<-list l)
- (Triangulation-boundary-vertices->list v)
- (Triangulation-boundary-vertices-length t)
- (Triangulation-edges<-list l)
- (Triangulation-edges->list e)
- (Triangulation-edges-length t)
- (Triangulation-boundary-edges<-list l)
- (Triangulation-boundary-edges->list e)
- (Triangulation-boundary-edges-length t)
- (Triangulation-triangles<-list l)
- (Triangulation-triangles->list t)
- (Triangulation-triangles-length t)
- (Triangulation-for-each-vertex proc t)
- (Triangulation-for-each-edge proc t)
- (Triangulation-for-each-triangle proc t)
- (Triangulation-for-each-boundary-vertex proc t)
- (Triangulation-for-each-boundary-edge proc t)
- Other objects:
geometry-code.scm
- Generic functions:
- Methods:
- (refine (v Vertex))
- (refine (v Boundary-vertex))
- (refine (e Edge))
- (refine (e Boundary-edge))
- (refine (t Triangle))
- (refine (t Triangulation))
- Functions:
- (Triangulation-consistent? t)
- (lists->Triangulation coordinates elements)
- Other objects:
- coarse-square-triangulation
- coarse-L-triangulation
linear-elements.scm
- Classes:
- Element
- Linear-element
- Finite-element-space
- Linear-finite-element-space
- Finite-element-vector
- Linear-finite-element-vector
- Methods:
- (initialize! (e Element))
- (initialize! (v Finite-element-vector))
- (Vector-dimension (x Finite-element-vector))
- (check-same-class (x Finite-element-vector) y)
- (Vector-add (x Finite-element-vector) y)
- (Vector-subtract (x Finite-element-vector) y)
- (Vector-scale x (y Finite-element-vector))
- (Vector-*axpy a (x Finite-element-vector) y)
- (Vector-dot-product (x Finite-element-vector) y)
- (Vector-zero (x Finite-element-vector))
- (Vector-copy (x Finite-element-vector))
- (Lattice-min (x Linear-finite-element-vector) y)
- (Lattice-max (x Linear-finite-element-vector) y)
- Functions:
- (Neighbors->list n)
- (Neighbors<-list l)
- (Neighbors-ref n i)
- (Neighbors-set! n i val)
- (Neighbors-length n)
- (Finite-element-space-elements->list e)
- (Finite-element-space-elements<-list l)
- (Finite-element-space-neighbors->list e)
- (Finite-element-space-neighbors<-list l)
- (Finite-element-space-neighbors-length space)
- (interpolate-procedure->Linear-finite-element-vector u fes)
linear-elements-code.scm
- Classes:
- Finite-element-operator
- Linear-finite-element-operator
- Generic functions:
- (evaluate-barycentric f coordinates (simplex))
- (evaluate-barycentric-triangle (f) coordinates triangle)
- (evaluate-barycentric-edge (f) coordinates edge)
- (Edge-midpoint (e))
- (Triangle-stiffness (t Triangle) a m)
- (Triangle-transport (t Triangle) b m)
- (Triangle-mass (t Triangle) c m)
- (Edge-boundary-term (e Edge) gamma m)
- (Triangle-interior-integral (t Triangle) f data)
- (Edge-boundary-integral (e Edge) g data)
- Methods:
- (initialize! (o Linear-finite-element-operator))
- (->Linear-finite-element-operator (space Linear-finite-element-space))
- (check-same-class (m Linear-finite-element-operator) n)
- (Vector-add (m Linear-finite-element-operator) n)
- (Vector-subtract (m Linear-finite-element-operator) n)
- (Vector-scale a (m Linear-finite-element-operator))
- (Vector-*axpy a (m Linear-finite-element-operator) n)
- (Vector-Linf-norm (m Operator-with-matrix-implementation))
- (Operator-compose (op1 Linear-finite-element-operator) (op2 Linear-finite-element-operator op2))
- (Operator->identity (m Linear-finite-element-operator))
- (Operator-adjoint (m Linear-finite-element-operator))
- (evaluate-barycentric f coordinates (triangle Triangle))
- (evaluate-barycentric-triangle (f Linear-finite-element-vector) coordinates triangle)
- (evaluate-barycentric f coordinates (edge Edge))
- (evaluate-barycentric-edge (f Linear-finite-element-vector) coordinates edge)
- (Edge-midpoint (e Edge))
- Functions:
- (Triangulation->Linear-finite-element-space t)
- (wrap-matrix-implementation-in-linear-finite-element-operator matrix domain-space range-space)
- (grad-phi p1 p2 p3)
- (add-stiffness-terms! m a)
- (add-transport-terms! m b)
- (add-mass-terms! m c)
- (add-boundary-terms! m gamma)
- (add-interior-integral-terms! v f)
- (add-boundary-integral-terms! v g)
- Other objects:
- make-barycentric
- barycentric-1/2-1/2-0
- barycentric-1/2-0-1/2
- barycentric-0-1/2-1/2
- barycentric-coordinate
- barycentric-dimension
- left-gauss-point
- right-gauss-point
problem-descriptions.scm
conjugate-gradient.scm
- Classes:
- Generic functions:
- (diagonal-preconditioner (m))
- (gauss-seidel-smoother! (m))
- (richardson-smoother! (m))
- (jacobi-smoother! (m))
- (gauss-seidel-preconditioner (m))
- Methods:
- (diagonal-preconditioner (m Sparse-matrix-operator))
- (diagonal-preconditioner (m Linear-finite-element-operator))
- (gauss-seidel-smoother! (m Linear-finite-element-operator))
- (richardson-smoother! (m Sparse-matrix-operator))
- (richardson-smoother! (m Linear-finite-element-operator))
- (jacobi-smoother! (m Sparse-matrix-operator))
- (jacobi-smoother! (m Linear-finite-element-operator))
- (gauss-seidel-preconditioner (m Linear-finite-element-operator))
- Functions:
- (CG-build-data triangulation space)
- (CG-add-operator-and-rhs-information! cg-data problem-data)
- (CG-add-solver-information! cg-data preconditioner-operator preconditioner-description iteration-limit residual-limit)
- (conjugate-gradient A b stop-iterations? #!optional (preconditioner identity-operator))
- (Sparse-matrix-operator-gauss-seidel-smoother! m #!optional (boundary-index? (lambda (i) #f)))
intergrid.scm
- Functions:
- (coarse<-fine coarse-space fine-space)
- (projector->injector m)
multigrid.scm
- Classes:
- Generic functions:
- (MG-solver (data) right-hand-sides)
- (MG-add-solver-information! (multigrid-data) smoother-name r m1 m2 p)
- Methods:
- (MG-solver (data Multigrid-data) right-hand-sides)
- (MG-add-solver-information! (multigrid-data Multigrid-data) smoother-name r m1 m2 p)
- Functions:
- (Triangulation->refined-triangulations coarse-triangulation number-of-refinements)
- (triangulations->linear-finite-element-spaces triangulations)
- (linear-finite-element-spaces->projectors spaces)
- (projectors->injectors projectors)
- (most-refined-operator->all-refined-operators operator projectors injectors)
- (most-refined-rhs->all-refined-rhs rhs projectors)
- (build-operator a c gamma fes)
- (build-rhs f g fes)
- (make-smoothers operators smoother-maker)
- (MG-step data m1 m2 p k z0 rhs)
dirichlet.scm
- Classes:
- Dirichlet-linear-finite-element-operator
- Methods:
- (initialize! (o Dirichlet-linear-finite-element-operator))
- (->Dirichlet-linear-finite-element-operator (o Linear-finite-element-operator))
- (gauss-seidel-smoother! (m Dirichlet-linear-finite-element-operator))
- Functions:
- (->Dirichlet-linear-finite-element-vector! v)
- (Dirichlet-linear-finite-element-vector? v)
- (CG-add-Dirichlet-operator-and-rhs-information! cg-data problem-data)
parabolic.scm
- Functions:
- (parabolic-equation-solution a c f g gamma u0 fes T n backward-difference-steps)
mmoc.scm
- Functions:
- (solve-transport-problem capacity a b c u0 f delta-t space N)
polygon.scm
- Classes:
- Functions:
- (next-polygon-vertex v)
- (previous-polygon-vertex v)
- (Triangulation<-points l)
pgm.scm
- Classes:
- Functions:
- (read-pgm file)
- (write-pgm image file #!optional force-ascii)
final-tests.scm
- Functions:
- (run-test check solver-thunk)
- (run-multigrid-tests tests)
- (run-cg-tests tests)
- Other objects:
- number-of-refinements
- triangulations
- spaces
- projectors
- injectors
- fes
- t
- cg-data
- fine-t
- fine-fes
- L2-inner-product-operator
- H1-inner-product-operator
- coarse->fine-operator
- dirichlet-tests
- symmetric-tests
- nonsymmetric-tests
- Includes:
test-dirichlet.scm
- Functions:
- (show-boundary-coefficients v)
- (show-class object)
- (run-test check solver-thunk)
- (run-multigrid-tests tests)
- (run-cg-tests tests)
- Other objects:
- number-of-refinements
- triangulations
- spaces
- projectors
- injectors
- fes
- t
- cg-data
- fine-t
- fine-fes
- L2-inner-product-operator
- H1-inner-product-operator
- coarse->fine-operator
- pi
- symmetric-tests
- Includes:
test-parabolic.scm
- Functions:
- (test-solution initial-triangulation initial-number-of-timesteps number-of-refinements)
- Other objects:
- a
- c
- gamma
- u
- f
- g
- u0
- description
- test-data
- T
- K
- Includes:
test-mmoc.scm
- Functions:
- Other objects:
- triangulation
- space
- u
- L2-inner-product-operator
- H1-inner-product-operator
- solution
- difference
- L2-error
- H1-error
- Includes:
symbolic.scm
- Functions:
- (formula? str)
- (expression str i)
- (term str i)
- (factor str i)
- (get-symbol str i)
- (get-number str i)
- (differentiate parse-tree variable)
- (simplify parse-tree)
- (append-symbols . args)
- (floatify parse-tree)
- Other objects:
tex.scm
- Generic functions:
- Methods:
- (->texdraw (e Edge))
- (->texdraw (e Curved-edge))
- Functions:
- (printable x)
- (texdraw-text text location)
- (Triangulation-edges->texdraw t)
- (Triangulation-triangles->texdraw t #!optional (label-vertices? #t))
- (draw-triangulation-debug-diagram t name)
- (draw-linear-finite-element-vector-debug-diagram v name)
html-lib.scm
- Functions:
- (html->string x)
- (html-display x . possible-port)
- (<unprotected> . args)
- (html-parse-args form-name end-tag? attribute-alist single-attribute-alist args)
- (html-build-form tag-name attribute-alist single-attribute-alist args start-newline? end-tag-start-newline? end-tag?)
- Other objects:
- Local macros:
- (define-tag . args)
- (define-input-tag)
- HTML tags:
- a
- abbr
- acronym
- address
- applet
- area
- b
- base
- basefont
- bdo
- big
- blockquote
- body
- br
- button
- caption
- center
- cite
- code
- col
- colgroup
- dd
- del
- dfn
- dir
- div
- dl
- dt
- em
- field-set
- font
- form
- frame
- frameset
- h1
- h2
- h3
- h4
- h5
- h6
- head
- hr
- html
- i
- iframe
- img
- ins
- isindex
- kbd
- label
- legend
- li
- link
- map
- menu
- meta
- noframes
- noscript
- object
- ol
- optgroup
- option
- p
- param
- plaintext
- pre
- q
- s
- samp
- script
- select
- small
- span
- strike
- strong
- style
- sub
- sup
- table
- td
- textarea
- tfoot
- th
- thead
- title
- tr
- tt
- u
- ul
- var
describe.scm
- Functions:
- (display-objects title os)
- (all-null? l)
- (category-name c)
- (category-recognizer c)
- (category-extractor c)
- (get-forms)
- (base-dir . url)
- (software-dir . url)
- (make-page all-forms)
- (display-page page)
- (build-index)
- Other objects:
- input-files
- categories
- *base*
- Includes: