This software was developed for and by the students in CS 615, Numerical Methods for Partial Differential Equations in the Spring semester of 2000. Its goal is to implement the finite element method in two dimensions. It is written in Scheme, and uses some features of Gambit-C, the Scheme->C compiler written by Marc Feeley. It uses Meroon, developed by Christian Queinnec, as its object system. (The version of Meroon we used is available here.) The last two files are the files used to build this index page.

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 software is relatively fast. For example, the sparse-matrix/vector multiply code runs in 10 cycles per flop on our Compaq DS20 clone (dual 500 MHz 21264s with 4 megabyte caches) after compiling the C code generated by Gambit-C with gcc-2.95.1 with the options "-mcpu=ev6 -O2 -mieee -fPIC -fno-math-errno". The -fno-math-errno option, backported from the development compiler, causes the compiler to not set ERRNO if sqrt returns a NaN. The same code written in C , with the same matrix structure, the same compiler, and the same compiler options, has exactly the same performance.

Note added later in course: Jason Gower wrote code to number the vertices, and hence the linear elements, along a space-filling curve. The new connectivity pattern is in connectivity2.gz. With this connectivity pattern, the scheme code runs in 8.25 cycles/flop, which is again just as fast as the C version.

Note: The performance of the code changes daily. Final results will be posted at the end of the course.

The code is coming along nicely and passes the tests in final-tests.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 now 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 now 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.

A gzipped tarball of all the sources can be found here. A short article describing the process of software development can be found here.

meroon.tgz

Changelog

all.scm

• Pervasive macros:
  • (FLOAT . rest)
  • (FIX . rest)
• Includes:
  • utilities.scm
  • random.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
  • obstacle.scm
  • parabolic.scm
  • mmoc.scm
  • polygon.scm

utilities.scm

• Generic functions:
  • (check-same-class (x Object) y)
• Functions:
  • (reverse-append! xrev y)
  • (keep p l)
  • (map1 f l)
  • (map2 f l1 l2)
  • (mappend1 f l)
  • (reduce-from-left op id l)
  • (reduce-from-right op id l)
  • (vector-for-each-1 proc v)
  • (vector-for-each-with-index-1 proc v)

random.scm

• Other objects:
  • seed-set!
  • seed-ref
  • random

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
  • 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:
  • (initialize! (op Matrix-operator))
• Functions:
  • (Operator-apply op v)
• Other objects:
  • identity-operator

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:
  • Sparse-vector-zero
• 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-dot-product p1 p2)
  • (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.) (x-min +inf.) (y-max -inf.) (y-min +inf.))
  • (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:
  • Triangulation-sort!

geometry-code.scm

• Generic functions:
  • (refine (o))
• 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)
• Other objects:
  • coarse-square-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)

linear-elements-code.scm

• Classes:
  • Finite-element-operator
  • Linear-finite-element-operator
• Generic functions:
  • (Edge-midpoint (e))
  • (Triangle-stiffness (t Triangle) as m)
  • (Triangle-transport (t Triangle) bs m)
  • (Triangle-mass (t Triangle) cs m)
  • (Edge-boundary-term (e Edge) gamma m)
  • (Triangle-interior-integral (t Triangle) fs 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))
  • (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:
  • left-gauss-point
  • right-gauss-point

problem-descriptions.scm

• Classes:
  • Problem-data

conjugate-gradient.scm

• Classes:
  • Conjugate-gradient-data
• 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 Sparse-matrix-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))

intergrid.scm

• Functions:
  • (coarse<-fine coarse-space fine-space)
  • (projector->injector m)

multigrid.scm

• Classes:
  • Multigrid-data
• Generic functions:
  • (MG-solver (data))
  • (MG-build-data (data) coarse-triangulation number-of-refinements)
  • (MG-add-operator-and-rhs-information! (multigrid-data) problem-data)
  • (MG-propagate-level-information! (multigrid-data))
  • (MG-add-solver-information! (multigrid-data) smoother-maker smoother-name r m1 m2 p)
• Methods:
  • (MG-solver (data Multigrid-data))
  • (MG-build-data (data Multigrid-data) coarse-triangulation number-of-refinements)
  • (MG-add-operator-and-rhs-information! (multigrid-data Multigrid-data) problem-data)
  • (MG-propagate-level-information! (multigrid-data Multigrid-data))
  • (MG-add-solver-information! (multigrid-data Multigrid-data) smoother-maker smoother-name r m1 m2 p)
• Functions:
  • (MG-step data smoothers! m1 m2 p k z0 rhs)

parabolic.scm

• Functions:
  • (parabolic-equation-solution a c f g gamma u0 fes T n backward-difference-steps)

mmoc.scm

• Functions:
  • (add-displaced-capacity-terms! rhs u characteristic-bases capacity)
  • (cu-at-displaced-edge-midpoints c u characteristic-bases)
  • (calculate-characteristic-bases triangulation flow)
  • (Point-in-triangle? p t)
  • (solve-transport-problem c a b u0 f delta-t space N)

obstacle.scm

• Classes:
  • Obstacle-multigrid-data
  • Obstacle-problem-data
• Methods:
  • (MG-solver (data Obstacle-multigrid-data))
  • (MG-build-data (data Obstacle-multigrid-data) coarse-triangulation number-of-refinements)
  • (MG-add-operator-and-rhs-information! (multigrid-data Obstacle-multigrid-data) problem-data)
  • (MG-propagate-level-information! (multigrid-data Obstacle-multigrid-data))
  • (MG-add-solver-information! (multigrid-data Obstacle-multigrid-data) smoother-maker smoother-name r m1 m2 p)
• Functions:
  • (Obstacle-MG-step data smoothers! m1 m2 p k z0 rhs obstacle)

polygon.scm

• Classes:
  • Polygon-vertex
• Functions:
  • (next-polygon-vertex v)
  • (previous-polygon-vertex v)
  • (Triangulation<-points l)

final-tests.scm

• Functions:
  • (run-test check solver-thunk)
  • (run-multigrid-tests tests)
  • (run-cg-tests tests)
• Other objects:
  • number-of-refinements
  • mg-data
  • t
  • fes
  • cg-data
  • fine-t
  • fine-fes
  • L2-inner-product-operator
  • H1-inner-product-operator
  • coarse->fine-operator
  • symmetric-tests
  • nonsymmetric-tests
• Includes:
  • points.scm

final-tests-obstacle.scm

• Functions:
  • (run-test check solver-thunk)
  • (run-multigrid-tests tests)
• Other objects:
  • number-of-refinements
  • fine-mg-data
  • mg-data
  • t
  • fes
  • fine-t
  • fine-fes
  • L2-inner-product-operator
  • H1-inner-product-operator
  • coarse->fine-operator
  • symmetric-tests
• Includes:
  • points.scm

test.scm

• Functions:
  • (iter i)
• Other objects:
  • t
  • fes
  • m
  • vec1
  • result
  • check
• Includes:
  • points.scm

test-parabolic.scm

• Functions:
  • (u t p)
  • (test-solution)
• Other objects:
  • a
  • c
  • f
  • g
  • gamma
  • u0
  • N
  • T
  • K
  • delta-t
  • triangulation
  • fes
  • L2-inner-product-operator
  • stopping-criterion
• Includes:
  • points.scm

test-mmoc.scm

• Functions:
  • (square x)
• Other objects:
  • triangulation
  • space
  • u
  • L2-inner-product-operator
  • H1-inner-product-operator
  • solution
  • difference
  • L2-error
  • H1-error
• Includes:
  • points.scm

tex.scm

• Generic functions:
  • (->texdraw (p))
• 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-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:
  • html:degree
• 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
  • 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)
  • (make-page all-forms)
  • (display-page page)
  • (build-index)
• Other objects:
  • input-files
  • categories
• Includes:
  • html-lib.scm