@article{Macdonald/Brandman/Ruuth:eigen,
author = {Macdonald, Colin B. and Brandman, Jeremy and Ruuth, Steven J.},
title = {Solving eigenvalue problems on curved surfaces
using the {C}losest {P}oint {M}ethod},
year = {2011},
note = {Submitted},
abstract = {Eigenvalue problems are fundamental to mathematics and
science. We present a simple algorithm for
determining eigenvalues and eigenfunctions of the
Laplace--Beltrami operator on rather general curved
surfaces. Our algorithm, which is based on the
Closest Point Method, relies on an embedding of the
surface in a higher-dimensional space, where
standard Cartesian finite difference and
interpolation schemes can be easily applied. We
show that there is a one-to-one correspondence
between a problem defined in the embedding space and
the original surface problem. For open surfaces, we
present a simple way to impose Dirichlet and Neumann
boundary conditions while maintaining second-order
accuracy. Convergence studies and a series of
examples demonstrate the effectiveness and
generality of our approach.}
}
@article{Ketcheson/Gottlieb/Macdonald:TSRK,
author = {Ketcheson, David I. and Gottlieb, Sigal and Macdonald, Colin B.},
title = {Strong stability preserving two-step {R}unge--{R}utta methods},
year = {2010},
note = {Submitted},
url = {http://people.maths.ox.ac.uk/~macdonald/ssptsrk.pdf},
abstract = { We investigate the strong stability preserving (SSP)
property of two-step Runge--Kutta (TSRK) methods.
We prove that SSP TSRK methods belong to a simple
subclass of TSRK methods, in which stages from the
previous step are not used. We derive simple order
conditions for this subclass. Whereas explicit SSP
Runge--Kutta methods have order at most four, we
prove that explicit SSP TSRK methods have order at
most eight. We present TSRK methods of up to eighth
order that were found by numerical search. These
methods have larger SSP coefficients than any known
methods of the same order of accuracy, and may be
implemented in a form with relatively modest storage
requirements. The usefulness of the TSRK methods is
demonstrated through numerical examples, including
integration of very high-order WENO discretizations}
}
@article{Motamed/Macdonald/Ruuth:weno5stability,
author = {Motamed, Mohammad and Macdonald, Colin B. and Ruuth, Steven J.},
title = {On Linear Stability of the Fifth-order {WENO}
Discretization},
year = {2010},
doi = {10.1007/s10915-010-9423-9},
note = {To appear in Journal of Scientific Computing},
url = {http://people.maths.ox.ac.uk/~macdonald/weno5_stability.pdf},
abstract = {We study the linear stability of the fifth-order
Weighted Essentially Non-Oscillatory spatial
discretization (WENO5) combined with explicit time
stepping applied to the one-dimensional advection
equation. We show that it is not necessary for the
stability domain of the time integrator to include a
part of the imaginary axis. In particular, we show
that the combination of WENO5 with either the
forward Euler method or a two-stage, second-order
Runge--Kutta method is linearly stable provided very
small time step-sizes are taken. We also consider
fifth-order multistep time discretizations whose
stability domains do not include the imaginary axis.
These are found to be linearly stable with moderate
time steps when combined with WENO5. In particular,
the fifth-order extrapolated BDF scheme gave
superior results in practice to high-order
Runge--Kutta methods whose stability domain includes
the imaginary axis. Numerical tests are presented
which confirm the analysis.}
}
@article{cbm:ridc,
author = {Christlieb, Andrew and Macdonald, Colin B. and Ong, Benjamin},
title = {Parallel High-Order Integrators},
journal = {SIAM J. Sci. Comput.},
fjournal = {SIAM Journal on Scientific Computing},
year = {2010},
volume = {32},
number = {2},
pages = {818--835},
note = {doi:10.1137/09075740X},
doi = {10.1137/09075740X},
url = {http://people.maths.ox.ac.uk/~macdonald/ridc.pdf},
abstract = {In this work we discuss a class of defect correction
methods which is easily adapted to create parallel
time integrators for multicore architectures and is
ideally suited for developing methods which can be
order adaptive in time. The method is based on
integral deferred correction (IDC), which was itself
motivated by spectral deferred correction by Dutt,
Greengard, and Rokhlin [BIT, 40 (2000),
pp. 241--266]. The method presented here is a revised
formulation of explicit IDC, dubbed revisionist IDC
(RIDC), which can achieve $p$th-order accuracy in
"wall-clock time" comparable to a single forward
Euler simulation on problems where the time to
evaluate the right-hand side of a system of
differential equations is greater than latency costs
of interprocessor communication, such as in the case
of the $N$-body problem. The key idea is to rewrite
the defect correction framework so that, after
initial start-up costs, each correction loop can be
lagged behind the previous correction loop in a
manner that facilitates running the predictor and
$M=p-1$ correctors in parallel on an interval which
has $K$ steps, where $K$ much greater than $p$. We
prove that given an $r$th-order Runge--Kutta method
in both the prediction and $M$ correction loops of
RIDC, then the method is order $r\times(M+1)$. The
parallelization in RIDC uses a small number of cores
(the number of processors used is limited by the
order one wants to achieve). Using a four-core CPU,
it is natural to think about fourth-order RIDC built
with forward Euler, or eighth-order RIDC constructed
with second-order Runge--Kutta. Numerical tests on an
$N$-body simulation show that RIDC methods can be
significantly faster than popular Runge--Kutta
methods such as the classical fourth-order
Runge--Kutta scheme. In a PDE setting, one can
imagine coupling RIDC time integrators with parallel
spatial evaluators, thereby increasing the
parallelization. The ideas behind RIDC extend to
implicit and semi-implicit IDC and have high
potential in this area.}
}
@inproceedings{luke:segment,
author = {Tian, {Li (Luke)} and Macdonald, Colin B. and Ruuth, Steven J.},
title = {Segmentation on surfaces with the {C}losest {P}oint {M}ethod},
year = {2009},
booktitle = {Proc. ICIP09, 16th {IEEE} International Conference on Image Processing},
pages = {3009--3012},
note = {doi:10.1109/ICIP.2009.5414447},
doi = {10.1109/ICIP.2009.5414447},
address = {Cairo, Egypt},
url = {http://people.maths.ox.ac.uk/~macdonald/TianMacdonaldRuuth.pdf},
abstract = {We propose a method to detect objects and patterns in
textures on general surfaces. Our approach applies
the Chan--Vese variational model for active contours
without edges to the problem of segmentation of
scalar surface data. This leads to gradient descent
equations which are level set equations on surfaces.
These equations are evolved using the Closest Point
Method, which is a recent technique for solving
partial differential equations (PDEs) on surfaces.
The final algorithm has a particularly simple form:
it merely alternates a time step of the usual
Chan--Vese model in a small 3D neighborhood of the
surface with an interpolation step. We remark that
the method can treat very general surfaces since it
uses a closest point function to represent the
underlying surface. Various experimental results
are presented, including segmentation on smooth
surfaces, non-smooth surfaces, open surfaces, and
general triangulated surfaces.}
}
@article{cbm:icpm,
author = {Macdonald, Colin B. and Ruuth, Steven J.},
title = {The Implicit {C}losest {P}oint {M}ethod for the Numerical
Solution of Partial Differential Equations on
Surfaces},
journal = {SIAM J. Sci. Comput.},
fjournal = {SIAM Journal on Scientific Computing},
year = {2009},
volume = {31},
number = {6},
pages = {4330--4350},
note = {doi:10.1137/080740003},
doi = {10.1137/080740003},
url = {http://people.maths.ox.ac.uk/~macdonald/icpm.pdf},
abstract = {Many applications in the natural and applied sciences
require the solutions of partial differential
equations (PDEs) on surfaces or more general
manifolds. The Closest Point Method is a simple and
accurate embedding method for numerically
approximating PDEs on rather general smooth
surfaces. However, the original formulation is
designed to use explicit time stepping. This may
lead to a strict time-step restriction for some
important PDEs such as those involving the
Laplace-Beltrami operator or higher-order derivative
operators. To achieve improved stability and
efficiency, we introduce a new implicit Closest
Point Method for surface PDEs. The method allows
for large, stable time steps while retaining the
principal benefits of the original method. In
particular, it maintains the order of accuracy of
the discretization of the underlying embedding PDE,
it works on sharply defined bands without degrading
the accuracy of the method, and it applies to
general smooth surfaces. It also is very simple and
may be applied to a rather general class of surface
PDEs. Convergence studies for the in-surface heat
equation and a fourth-order biharmonic problem are
given to illustrate the accuracy of the method. We
demonstrate the flexibility and generality of the
method by treating flows involving diffusion,
reaction-diffusion and fourth-order spatial
derivatives on a variety of interesting surfaces
including surfaces of mixed codimension.}
}
@article{Ketcheson/Macdonald/Gottlieb:imssp,
author = {Ketcheson, David I. and Macdonald, Colin B. and Gottlieb, Sigal},
title = {Optimal implicit strong stability preserving {R}unge--{K}utta methods},
journal = {Appl. Numer. Math.},
fjournal = {Applied Numerical Mathematics},
month = {February},
year = {2009},
volume = {59},
number = {2},
pages = {373--392},
note = {doi:10.1016/j.apnum.2008.03.034},
doi = {10.1016/j.apnum.2008.03.034},
url = {http://people.maths.ox.ac.uk/~macdonald/imssp.pdf},
abstract = {Strong stability preserving (SSP) time discretizations
were developed for use with spatial discretizations
of partial differential equations that are strongly
stable under forward Euler time integration. SSP
methods preserve convex boundedness and
contractivity properties satisfied by forward Euler,
under a modified timestep restriction. We turn to
implicit Runge--Kutta methods to alleviate this
timestep restriction, and present implicit SSP
Runge--Kutta methods which are optimal in the sense
that they preserve convex boundedness properties
under the largest timestep possible among all
methods with a given number of stages and order of
accuracy. We consider methods up to order six (the
maximal order of SSP Runge--Kutta methods) and up to
eleven stages. The numerically optimal methods found
are all diagonally implicit, leading us to
conjecture that optimal implicit SSP Runge--Kutta
methods are diagonally implicit. These methods
allow a significant increase in the SSP timestep
limit, compared to explicit methods of the same
order and number of stages. Numerical tests verify
the order and the SSP property of the methods.}
}
@article{cbm:lscpm,
author = {Macdonald, Colin B. and Ruuth, Steven J.},
title = {Level set equations on surfaces via the {C}losest {P}oint {M}ethod},
journal = {J. Sci. Comput.},
fjournal = {Journal of Scientific Computing},
month = {June},
year = {2008},
volume = {35},
number = {2--3},
pages = {219--240},
note = {doi:10.1007/s10915-008-9196-6},
doi = {10.1007/s10915-008-9196-6},
url = {http://people.maths.ox.ac.uk/~macdonald/lscpm.pdf},
abstract = {Level set methods have been used in a great number of
applications in $\mathbb{R}^2$ and $\mathbb{R}^3$
and it is natural to consider extending some of
these methods to problems defined on surfaces
embedded in $\mathbb{R}^3$ or higher dimensions. In
this paper we consider the treatment of level set
equations on surfaces via a recent technique for
solving partial differential equations (PDEs) on
surfaces, the Closest Point Method
\cite{Ruuth/Merriman:jcp08:CPM}. Our main
modification is to introduce a Weighted Essentially
Non-Oscillatory (WENO) interpolation step into the
Closest Point Method. This, in combination with
standard WENO for Hamilton--Jacobi equations, gives
high-order results (up to fifth-order) on a variety
of smooth test problems including passive transport,
normal flow and redistancing. The algorithms we
propose are straightforward modifications of
standard codes, are carried out in the embedding
space in a well-defined band around the surface and
retain the robustness of the level set method with
respect to the self-intersection of interfaces.
Numerous examples are provided to illustrate the
flexibility of the method with respect to geometry.}
}
@article{cbm:dsrk,
author = {Macdonald, Colin B. and Gottlieb, Sigal and Ruuth, Steven J.},
title = {A numerical study of diagonally split {R}unge--{K}utta methods for {PDEs} with discontinuities},
journal = {J. Sci. Comput.},
fjournal = {Journal of Scientific Computing},
year = {2008},
volume = {36},
number = {1},
pages = {89--112},
month = {July},
note = {doi:10.1007/s10915-007-9180-6},
doi = {10.1007/s10915-007-9180-6},
url = {http://people.maths.ox.ac.uk/~macdonald/dsrk.pdf},
keywords = {diagonally split Runge--Kutta methods; Runge--Kutta
methods; unconditional contractivity; strong
stability preserving; time discretization; order
reduction; stage order; hyperbolic PDEs},
abstract = {Diagonally split Runge--Kutta (DSRK) time discretization
methods are a class of implicit time-stepping
schemes which offer both high-order convergence and
a form of nonlinear stability known as unconditional
contractivity. This combination is not possible
within the classes of Runge--Kutta or linear
multistep methods and therefore appears promising
for the strong stability preserving (SSP)
time-stepping community which is generally concerned
with computing oscillation-free numerical solutions
of PDEs. Using a variety of numerical test
problems, we show that although second- and
third-order unconditionally contractive DSRK methods
do preserve the strong stability property for all
time step-sizes, they suffer from order reduction at
large step-sizes. Indeed, for time-steps larger
than those typically chosen for explicit methods,
these DSRK methods behave like first-order implicit
methods. This is unfortunate, because it is
precisely to allow a large time-step that we choose
to use implicit methods. These results suggest that
unconditionally contractive DSRK methods are limited
in usefulness as they are unable to compete with
either the first-order backward Euler method for
large step-sizes or with Crank--Nicolson or
high-order explicit SSP Runge--Kutta methods for
smaller step-sizes. We also present stage order
conditions for DSRK methods and show that the
observed order reduction is associated with the
necessarily low stage order of the unconditionally
contractive DSRK methods.}
}
@incollection{Macdonald/Spiteri:2001:psrm,
author = {Colin B. Macdonald and Raymond J. Spiteri},
title = {The predicted sequential regularization method for
dif\-fe\-ren\-tial-algebraic equations},
booktitle = {Mathematics and Simulation with Biological,
Economic, and Musicoacoustical Applications},
pages = {107--112},
publisher = {WSES Press},
year = {2001},
editor = {C.E. D'Attellis and V.V. Kluev and N. Mastorakis}
}
Back to Colin Macdonald’s website.