In some cases, I've included the final journal .pdf of my papers. In other cases, preprints are linked; the final journal version may be more uptodate.
[1] 
Emma Naden, Thomas März, and Colin B. Macdonald.
Anisotropic diffusion on curved surfaces.
2014.
Undergoing revision.
[ bib 
arXiv 
.pdf ]
We demonstrate a method for filtering images defined on curved surfaces embedded in 3D. Applications are noise removal and the creation of artistic effects. Our approach relies on insurface diffusion: we formulate Weickert's edge/coherence enhancing diffusion models in a surfaceintrinsic way. These diffusion processes are anisotropic and the equations depend nonlinearly on the data. The surfaceintrinsic equations are dealt with the closest point method, a technique for solving partial differential equations (PDEs) on general surfaces. The resulting algorithm has a very simple structure: we merely alternate a time step of a 3D analog of the insurface PDE in a narrow 3D band containing the surface with a reconstruction of the surface function. Surfaces are represented by a closest point function. This representation is flexible and the method can treat very general surfaces. Experimental results include image filtering on smooth surfaces, open surfaces, and general triangulated surfaces.

[2] 
Ingrid von Glehn, Thomas März, and Colin B. Macdonald.
An embedded methodoflines approach to solving partial differential
equations on surfaces.
2014.
Undergoing revision.
[ bib 
arXiv 
.pdf ]
We introduce a methodoflines formulation of the closest point method, a numerical technique for solving partial differential equations (PDEs) defined on surfaces. This is an embedding method, which uses an implicit representation of the surface in a band containing the surface. We define a modified equation in the band, obtained in a straightforward way from the original evolution PDE, and show that the solutions of this equation are consistent with those of the surface equation. The resulting system can then be solved with standard implicit or explicit timestepping schemes, and the solutions in the band can be restricted to the surface. Our derivation generalizes existing formulations of the closest point method and is amenable to standard convergence analysis.

[3] 
Andrew J. Christlieb, Colin B. Macdonald, Benjamin W. Ong, and Raymond J.
Spiteri.
Revisionist integral deferred correction with adaptive stepsize
control.
Comm. App. Math. Com. Sc., 2015.
To appear.
[ bib 
arXiv 
.pdf ]
Adaptive stepsize control is a critical feature for the robust and efficient numerical solution of initialvalue problems in ordinary differential equations. In this paper, we show that adaptive stepsize control can be incorporated within a family of parallel time integrators known as Revisionist Integral Deferred Correction (RIDC) methods. The RIDC framework allows for various strategies to implement stepsize control, and we report results from exploring a few of them.

[4] 
Yujia Chen and Colin B. Macdonald.
The Closest Point Method and multigrid solvers for elliptic
equations on surfaces.
SIAM J. Sci. Comput., 37(1), 2015.
[ bib 
DOI 
arXiv 
.pdf ]
Elliptic partial differential equations are important both from application and analysis points of views. In this paper we apply the Closest Point Method to solving elliptic equations on general curved surfaces. Based on the closest point representation of the underlying surface, we formulate an embedding equation for the surface elliptic problem, then discretize it using standard finite differences and interpolation schemes on banded, but uniform Cartesian grids. We prove the convergence of the difference scheme for the Poisson's equation on a smooth closed curve. In order to solve the resulting large sparse linear systems, we propose a specific geometric multigrid method in the setting of the Closest Point Method. Convergence studies both in the accuracy of the difference scheme and the speed of the multigrid algorithm show that our approaches are effective.

[5] 
Harry Biddle, Ingrid von Glehn, Colin B. Macdonald, and Thomas März.
A volumebased method for denoising on curved surfaces.
In Proc. ICIP13, 20th IEEE International Conference on Image
Processing, pages 529533, 2013.
[ bib 
DOI 
.pdf ]
We demonstrate a method for removing noise from images or other data on curved surfaces. Our approach relies on insurface diffusion: we formulate both the Gaussian diffusion and PeronaMalik edgepreserving diffusion equations in a surfaceintrinsic way. Using the Closest Point Method, a recent technique for solving partial differential equations (PDEs) on general surfaces, we obtain a very simple algorithm where we merely alternate a time step of the usual Gaussian diffusion (and similarly PeronaMalik) in a small 3D volume containing the surface with an interpolation step. The method uses a closest point function to represent the underlying surface and can treat very general surfaces. Experimental results include image filtering on smooth surfaces, open surfaces, and general triangulated surfaces.

[6] 
David I. Ketcheson, Colin B. Macdonald, and Steven J. Ruuth.
Spatially partitioned embedded RungeKutta methods.
SIAM J. Numer. Anal., 51(5):28872910, 2013.
[ bib 
arXiv 
.pdf ]
We study spatially partitioned embedded RungeKutta (SPERK) schemes for partial differential equations (PDEs), in which each of the component schemes is applied over a different part of the spatial domain. Such methods may be convenient for problems in which the smoothness of the solution or the magnitudes of the PDE coefficients vary strongly in space. We focus on embedded partitioned methods as they offer greater efficiency and avoid the order reduction that may occur in nonembedded schemes. We demonstrate that the lack of conservation in partitioned schemes can lead to nonphysical effects and propose conservative additive schemes based on partitioning the fluxes rather than the ordinary differential equations. A variety of SPERK schemes are presented, including an embedded pair suitable for the time evolution of fifthorder weighted nonoscillatory (WENO) spatial discretizations. Numerical experiments are provided to support the theory.

[7] 
Colin B. Macdonald, Barry Merriman, and Steven J. Ruuth.
Simple computation of reactiondiffusion processes on point clouds.
Proc. Natl. Acad. Sci., 110(23), 2013.
[ bib 
DOI ]
The study of reactiondiffusion processes is much more complicated on general curved surfaces than on standard Cartesian coordinate spaces. Here we show how to formulate and solve systems of reactiondiffusion equations on surfaces in an extremely simple way, using only the standard Cartesian form of differential operators, and a discrete unorganized point set to represent the surface. Our method decouples surface geometry from the underlying differential operators. As a consequence, it becomes possible to formulate and solve rather general reactiondiffusion equations on general surfaces without having to consider the complexities of differential geometry or sophisticated numerical analysis. To illustrate the generality of the method, computations for surface diffusion, pattern formation, excitable media, and bulksurface coupling are provided for a variety of complex point cloud surfaces.

[8] 
Yiannis Hadjimichael, Colin B. Macdonald, David I. Ketcheson, and James H.
Verner.
Strong stability preserving explicit RungeKutta methods of
maximal effective order.
SIAM J. Numer. Anal., 51(4):21492165, 2013.
[ bib 
DOI 
arXiv 
.pdf ]
We apply the concept of effective order to strong stability preserving (SSP) explicit RungeKutta methods. Relative to classical RungeKutta methods, methods with an effective order of accuracy are designed to satisfy a relaxed set of order conditions, but yield higher order accuracy when composed with special starting and stopping methods. We show that this allows the construction of fourstage SSP methods with effective order four (such methods cannot have classical order four). However, we also prove that effective order five methodslike classical order five methodsrequire the use of nonpositive weights and so cannot be SSP. By numerical optimization, we construct explicit SSP RungeKutta methods up to effective order four and establish the optimality of many of them. Numerical experiments demonstrate the validity of these methods in practice.

[9] 
Thomas März and Colin B. Macdonald.
Calculus on surfaces with general closest point functions.
SIAM J. Numer. Anal., 50(6):33033328, 2012.
[ bib 
DOI 
arXiv 
.pdf ]
The Closest Point Method for solving partial differential equations (PDEs) posed on surfaces was recently introduced by Ruuth and Merriman [J. Comput. Phys. 2008] and successfully applied to a variety of surface PDEs. In this paper we study the theoretical foundations of this method. The main idea is that surface differentials of a surface function can be replaced with Cartesian differentials of its closest point extension, i.e., its composition with a closest point function. We introduce a general class of these closest point functions (a subset of differentiable retractions), show that these are exactly the functions necessary to satisfy the above idea, and give a geometric characterization this class. Finally, we construct some closest point functions and demonstrate their effectiveness numerically on surface PDEs

[10] 
S. Auer, C. B. Macdonald, M. Treib, J. Schneider, and R. Westermann.
Realtime fluid effects on surfaces using the Closest Point
Method.
Comput. Graph. Forum, 31(6):19091923, 2012.
[ bib 
DOI 
.pdf ]
The Closest Point Method (CPM) is a method for numerically solving partial differential equations (PDEs) on arbitrary surfaces, independent of the existence of a surface parametrization. The CPM uses a closest point representation of the surface, to solve the unmodified Cartesian version of a surface PDE in a 3D volume embedding, using simple and wellunderstood techniques. In this paper we present the numerical solution of the wave equation and the incompressible NavierStokes equations on surfaces via the CPM, and we demonstrate surface appearance and shape variations in realtime using this method. To fully exploit the potential of the CPM, we present a novel GPU realization of the entire CPM pipeline. We propose a surfaceembedding adaptive 3D spatial grid for efficient representation of the surface, and present a highperformance approach using CUDA for converting surfaces given by triangulations into this representation. For realtime performance, CUDA is also used for the numerical procedures of the CPM. For rendering the surface (and the PDE solution) directly from the closest point representation without the need to reconstruct a triangulated surface, we present a GPU raycasting method that works on the adaptive 3D grid.

[11] 
Colin B. Macdonald, Jeremy Brandman, and Steven J. Ruuth.
Solving eigenvalue problems on curved surfaces using the Closest
Point Method.
J. Comput. Phys., 230(22):79447956, 2011.
[ bib 
DOI 
arXiv 
.pdf ]
Eigenvalue problems are fundamental to mathematics and science. We present a simple algorithm for determining eigenvalues and eigenfunctions of the LaplaceBeltrami 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 higherdimensional space, where standard Cartesian finite difference and interpolation schemes can be easily applied. We show that there is a onetoone 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 secondorder accuracy. Convergence studies and a series of examples demonstrate the effectiveness and generality of our approach.

[12] 
David I. Ketcheson, Sigal Gottlieb, and Colin B. Macdonald.
Strong stability preserving twostep RungeKutta methods.
SIAM J. Numer. Anal., 49(6):26182639, 2012.
[ bib 
DOI 
arXiv 
.pdf ]
We investigate the strong stability preserving (SSP) property of twostep RungeKutta (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 RungeKutta 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 highorder WENO discretizations

[13] 
Mohammad Motamed, Colin B. Macdonald, and Steven J. Ruuth.
On linear stability of the fifthorder WENO discretization.
J. Sci. Comput., 47(2):127149, 2010.
[ bib 
DOI 
.pdf ]
We study the linear stability of the fifthorder Weighted Essentially NonOscillatory spatial discretization (WENO5) combined with explicit time stepping applied to the onedimensional 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 twostage, secondorder RungeKutta method is linearly stable provided very small time stepsizes are taken. We also consider fifthorder 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 fifthorder extrapolated BDF scheme gave superior results in practice to highorder RungeKutta methods whose stability domain includes the imaginary axis. Numerical tests are presented which confirm the analysis.

[14] 
Andrew J. Christlieb, Colin B. Macdonald, and Benjamin W. Ong.
Parallel highorder integrators.
SIAM J. Sci. Comput., 32(2):818835, 2010.
[ bib 
DOI 
.pdf ]
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. 241266]. The method presented here is a revised formulation of explicit IDC, dubbed revisionist IDC (RIDC), which can achieve pthorder accuracy in "wallclock time" comparable to a single forward Euler simulation on problems where the time to evaluate the righthand side of a system of differential equations is greater than latency costs of interprocessor communication, such as in the case of the Nbody problem. The key idea is to rewrite the defect correction framework so that, after initial startup costs, each correction loop can be lagged behind the previous correction loop in a manner that facilitates running the predictor and M=p1 correctors in parallel on an interval which has K steps, where K much greater than p. We prove that given an rthorder RungeKutta method in both the prediction and M correction loops of RIDC, then the method is order r×(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 fourcore CPU, it is natural to think about fourthorder RIDC built with forward Euler, or eighthorder RIDC constructed with secondorder RungeKutta. Numerical tests on an Nbody simulation show that RIDC methods can be significantly faster than popular RungeKutta methods such as the classical fourthorder RungeKutta 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 semiimplicit IDC and have high potential in this area.

[15] 
Li (Luke) Tian, Colin B. Macdonald, and Steven J. Ruuth.
Segmentation on surfaces with the Closest Point Method.
In Proc. ICIP09, 16th IEEE International Conference on Image
Processing, pages 30093012, Cairo, Egypt, 2009.
[ bib 
DOI 
.pdf ]
We propose a method to detect objects and patterns in textures on general surfaces. Our approach applies the ChanVese 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 ChanVese 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, nonsmooth surfaces, open surfaces, and general triangulated surfaces.

[16] 
Colin B. Macdonald and Steven J. Ruuth.
The implicit Closest Point Method for the numerical solution of
partial differential equations on surfaces.
SIAM J. Sci. Comput., 31(6):43304350, 2009.
[ bib 
DOI 
.pdf ]
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 timestep restriction for some important PDEs such as those involving the LaplaceBeltrami operator or higherorder 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 insurface heat equation and a fourthorder 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, reactiondiffusion and fourthorder spatial derivatives on a variety of interesting surfaces including surfaces of mixed codimension.

[17] 
David I. Ketcheson, Colin B. Macdonald, and Sigal Gottlieb.
Optimal implicit strong stability preserving RungeKutta
methods.
Appl. Numer. Math., 59(2):373392, 2009.
[ bib 
DOI 
.pdf ]
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 RungeKutta methods to alleviate this timestep restriction, and present implicit SSP RungeKutta 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 RungeKutta methods) and up to eleven stages. The numerically optimal methods found are all diagonally implicit, leading us to conjecture that optimal implicit SSP RungeKutta 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.

[18] 
Colin B. Macdonald and Steven J. Ruuth.
Level set equations on surfaces via the Closest Point Method.
J. Sci. Comput., 35(23):219240, 2008.
[ bib 
DOI 
.pdf ]
Level set methods have been used in a great number of applications in R^{2} and R^{3} and it is natural to consider extending some of these methods to problems defined on surfaces embedded in 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 [?]. Our main modification is to introduce a Weighted Essentially NonOscillatory (WENO) interpolation step into the Closest Point Method. This, in combination with standard WENO for HamiltonJacobi equations, gives highorder results (up to fifthorder) 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 welldefined band around the surface and retain the robustness of the level set method with respect to the selfintersection of interfaces. Numerous examples are provided to illustrate the flexibility of the method with respect to geometry.

[19] 
Colin B. Macdonald, Sigal Gottlieb, and Steven J. Ruuth.
A numerical study of diagonally split RungeKutta methods for
PDEs with discontinuities.
J. Sci. Comput., 36(1):89112, 2008.
[ bib 
DOI 
.pdf ]
Diagonally split RungeKutta (DSRK) time discretization methods are a class of implicit timestepping schemes which offer both highorder convergence and a form of nonlinear stability known as unconditional contractivity. This combination is not possible within the classes of RungeKutta or linear multistep methods and therefore appears promising for the strong stability preserving (SSP) timestepping community which is generally concerned with computing oscillationfree numerical solutions of PDEs. Using a variety of numerical test problems, we show that although second and thirdorder unconditionally contractive DSRK methods do preserve the strong stability property for all time stepsizes, they suffer from order reduction at large stepsizes. Indeed, for timesteps larger than those typically chosen for explicit methods, these DSRK methods behave like firstorder implicit methods. This is unfortunate, because it is precisely to allow a large timestep 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 firstorder backward Euler method for large stepsizes or with CrankNicolson or highorder explicit SSP RungeKutta methods for smaller stepsizes. 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. Keywords: diagonally split RungeKutta methods; RungeKutta methods; unconditional contractivity; strong stability preserving; time discretization; order reduction; stage order; hyperbolic PDEs 
[20]  Colin B. Macdonald and Raymond J. Spiteri. The predicted sequential regularization method for differentialalgebraic equations. In D'Attellis, Kluev, and Mastorakis, editors, Mathematics and Simulation with Biological, Economic, and Musicoacoustical Applications, pages 107112. WSES Press, 2001. [ bib ] 
Back to Colin Macdonald’s website.