# Papers on Numerical Methods for PDEs and related topics

Numerical analysis of random drift in a cline, by Thomas Nagylaki and Bradley Lucier, Genetics, 94 (1980), 497-517.

Abstract: The equilibrium state of a diffusion model for random genetic drift in a cline is analyzed numerically. The monoecious organism occupies an un- bounded linear habitat with constant, uniform population density. Migration is homogeneous, symmetric and independent of genotype. A single diallelic locus with a step environment is investigated in the absence of dominance and mutation. The flattening of the expected cline due to random drift is very slight in natural populations. The ratio of the variance of either gene frequency to the product of the expected gene frequencies decreases monotonically to a nonzero constant. The correlation between the gene frequencies at two points decreases monotonically to zero as the separation is increased with the average position fixed; the decrease is asymptotically exponential. The correlation decreases monotonically to a positive constant depending on the separation as the average position increasingly deviates from the center of the cline with the separation fixed. The correlation also decreases monotonically to zero if one of the points is fixed and the other is moved outward in the habitat, the ultimate decrease again being exponential. Some asymptotic formulae are derived analytically.---The loss of an allele favored in an environmental pocket is investigated by simulating a chain of demes exchanging migrants, the other assumptions being the same as above. For most natural populations, provided the allele would be maintained in the population deterministically, this process is too slow to have evolutionary importance.

On nonlocal monotone difference schemes for scalar conservation laws, by Bradley J. Lucier, Mathematics of Computation, 47 (1986), 19-36.

Abstract: We provide error analyses for explicit, implicit, and semi-implicit monotone finite-difference schemes on uniform meshes with nonlocal numerical fluxes. We are motivated by finite-difference discretizations of certain long-wave (Sobolev) regularizations of the conservation laws that explicitly add a dispersive term as well as a nonlinear dissipative term. We also develop certain relationships between dispersion and stability in finite difference schemes. Specifically, we find that discretization and explicit dispersion have identical effects on the amount of artificial dissipation necessary for stability.

On Sobolev regularizations of hyperbolic conservation laws, by Bradley J. Lucier, Communications in Partial Differential Equations, 10 (1985), 1-28.

Abstract: Necessary and sufficient conditions are given so that Sobolev-type regularizations of scalar hyperbolic conservation laws generate contraction semigroups on $L^1(\Bbb R)$ and satisfy a maximum principle, despite the dispersive character of the equations. Part of the argument is based on a maximum principle for general nonlinear mappings on $L^1(\Bbb R)$. We bound the difference between the solutions of the regularized equation and the solution of the underlying conservation law. Finally, we describe an application to singular, second-order hyperbolic perturbations of first-order conservation laws.

A stable adaptive numerical scheme for hyperbolic conservation laws, by Bradley J. Lucier, SIAM Journal on Numerical Analysis, 22 (1985), 180-203.

Abstract: A new adaptive finite-difference scheme for scalar hyperbolic conservation laws is introduced. A key aspect of the method is a new automatic mesh selection algorithm for problems with shocks. We show that the scheme is $L^1$-stable in the sense of Kuznetsov, and that it generates convergent approximations for linear problems. Numerical evidence is presented that indicates that if an error of size $\varepsilon$ is required, our scheme takes at most $O(\varepsilon ^{ - 3} )$ operations. Standard monotone difference schemes can take up to $O(\varepsilon ^{ - 4} )$ calculations for the same problems.

A moving mesh numerical method for hyperbolic conservation laws, by Bradley J. Lucier, Mathematics of Computation, 46 (1986), 59-69

Abstract: We show that the possibly discontinuous solution of a scalar conservation law in one space dimension may be approximated in $L_1(\Bbb R)$ to within $O(N ^{-2})$ by a piecewise linear function with $O(N)$ nodes; the nodes are moved according to the method of characteristics. We also show that a previous method of Dafermos, which uses piecewise constant approximations, is accurate to $O(N^{-1})$. These numerical methods for conservation laws are the first to have proven convergence rates of greater than $O(N^{-1/2})$.

Error bounds for the methods of Glimm, Godunov, and LeVeque, by Bradley J. Lucier, SIAM Journal on Numerical Analysis, 22 (1985), 1074-1081.

Abstract: The expected error in ${L^1(\Bbb R)}$ at time $T$ for Glimm's scheme when applied to a scalar conservation law is bounded by $$\left(h+{2\over\sqrt3} \left({h\over\Delta t}\right)^{1/2}(hT)^{1/2}\right)\|u_0\|_{BV(\Bbb R)},$$ where $h$ is the mesh size and $\Delta t$ is the time step. We show that the error in Godunov's scheme is bounded by the same expression and use this result to analyze a variant of a large time step numerical method of LeVeque that may be viewed as a combination of Godunov's scheme and a method of Dafermos.

Numerical methods with interface estimates for the porous medium equation, by David Hoff and Bradley J. Lucier, RAIRO Mod\'elisation Math\'ematique et Analyse Num\'erique, 21 (1987), 465-485

Abstract: We provide a general basis, based on the weak truncation error, for proving $L^\infty$ error bounds for the porous medium equation in one space dimension. We show how such bounds for the solution can lead to estimates for the interface of the support for the solution, and we apply this theory to a specific finite difference approximation to the differential equation.

Parallel adaptive numerical schemes for hyperbolic systems of conservation laws, by Bradley J. Lucier and Ross Overbeek, SIAM Journal on Scientific and Statistical Computing, 8 (1987), s203-s219. Reprinted in Selected Papers from the Second Conference on Parallel Processing for Scientific Computing, C. W. Gear and R. G. Voight, eds., SIAM, Philadelphia, 1987.

Abstract: We generalize the first author's adaptive numerical scheme for scalar first order conservation laws to systems of equations. The resulting numerical methods generate highly non-uniform, time-dependent grids, and hence are difficult to execute efficiently on vector computers such as the Cray or Cyber 205. In contrast, we show that these algorithms may be executed in parallel on alternate computer architectures. We describe a parallel implementation of the algorithm on the Denelcor HEP, a multiple-instruction, multiple-data (MIMD) shared memory parallel computer.

Performance evaluation for multiprocessors programmed using monitors, by Bradley J. Lucier, Proceedings of the 1988 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, Special Issue of the SIGMETRICS Performance Evaluation Review, 16, No. 1 (1988), 22-29.

Abstract: We present a classification of synchronization delays inherent in multiprocessor systems programmed using the monitor paradigm. This characterization is useful in relating performance of such systems to algorithmic parameters in subproblems such as domain decomposition. We apply this approach to a parallel, adaptive grid code for solving the equations of one-dimensional gas dynamics implemented on shared memory multiprocessors such as the Encore Multimax.

Regularity through approximation for scalar conservation laws, by Bradley J. Lucier, SIAM Journal on Mathematical Analysis, 19 (1988), 763-773

Abstract: In this paper it is shown that recent approximation results for scalar conservation laws in one space dimension imply that solutions of these equations with smooth, convex fluxes have more regularity than previously believed. Regularity is measured in spaces determined by quasinorms related to the solution's approximation properties in $L^1(\Bbb R)$ by discontinuous, piecewise linear functions. Using a previous characterization of these approximation spaces in terms of Besov spaces, it is shown that there is a one-parameter family of Besov spaces that are invariant under the differential equation. An intriguing feature of this investigation is that regularity is measured quite naturally in smoothness classes that are not locally convex---they are similar to $L^p$ spaces for $0<p<1$. Extensions to Hamilton-Jacobi equations are mentioned.

High order regularity for conservation laws, by Ronald A. DeVore and Bradley J. Lucier, Indiana University Mathematics Journal, 39 (1990), 413-430

Abstract: We study the regularity of discontinuous entropy solutions to scalar hyperbolic conservation laws with uniformly convex fluxes posed as initial value problems on $\Bbb R$. For positive $\alpha$ we show that if the initial data has bounded variation and the flux is smooth enough then the solution $u(\,\cdot\,,t)$ is in the Besov space $B^\alpha_\sigma(L_\sigma(\Bbb R))$ where $\sigma=1/(\alpha+1)$ whenever the initial data is in this space. As a corollary, we show that discontinuous solutions of conservation laws have enough regularity to be approximated well by moving-grid finite element methods. Techniques from approximation theory are the basis for our analysis.

Best approximations in $L_1$ are near best in $L_p$, $p<1$, by Lawrence G. Brown and Bradley J. Lucier, Proceedings of the American Mathematical Society, 120 (1994), 97-100

Abstract: We show that any best $L^1$ polynomial approximation to a function $f$ in $L^p$, $0<p<1$, is near best in $L^p$.

On the size and smoothness of solutions to nonlinear conservation laws, by Ronald A. DeVore and Bradley J. Lucier, SIAM Journal on Mathematical Analysis, 27 (1996), 684-707

Abstract: We address the question of which function spaces are invariant under the action of scalar conservation laws in one and several space dimensions. We establish two types of results. The first result shows that if the initial data is in a rearrangement-invariant function space, then the solution is in the same space for all time. Secondly, we examine which smoothness spaces among the Besov spaces are invariant for conservation laws. Previously, we showed in one dimension that if the initial data has bounded variation and the flux is convex and smooth enough, then the Besov spaces $B^\alpha_q(L_q)$, $\alpha>1$, $q=1/(\alpha+1)$, are invariant smoothness spaces. Now, in one space dimension, we show that no other Besov space with $\alpha>1$ is invariant. In several space dimensions, we show that no Besov space $B^\alpha_q(L_q)$ with $\alpha>1$ is invariant. Combined with previous results, our theorems completely characterize for $\alpha>1$ which Besov spaces are smoothness spaces for scalar conservation laws.

Un principe du maximum pour des op\'erateurs monotones [A maximum principle for order-preserving mappings], by Antonin Chambolle and Bradley J. Lucier, Comptes Rendus des S\'eances de l'Acad\'emie des Sciences, S\'erie I, Math\'ematique, 326 (1998), 823-827

English abstract: We prove that if $T$ is a possibly nonlinear mapping from $L_1(\Bbb R^n)$ to itself that preserves the integral, is order preserving, and that commutes with translations, then $T$ satisfies a maximum principle: the essential supremum of $Tu$ is no greater than the essential supremum of $u$.

Numerical partial differential equations in Scheme, by Bradley J. Lucier, Proceedings of the Workshop on Scheme and Functional Programming, M. Felleisen, ed., Rice University Computer Science Department Technical Report 00-368, 2000, 27-30.

An Upwind Finite-Difference Method for Total Variation--Based Image Smoothing, by Antonin Chambolle, Stacey E. Levine, and Bradley J. Lucier, SIAM Journal on Imaging Sciences, 4 (2011), 277-299.

Abstract: In this paper we study finite-difference approximations to the variational problem using the BV smoothness penalty that was introduced in an image smoothing context by Rudin, Osher, and Fatemi. We give a dual formulation for an upwind finite-difference approximation for the BV seminorm; this formulation is in the same spirit as one popularized by the first author for a simpler, less isotropic, finite-difference approximation to the (isotropic) BV seminorm. We introduce a multiscale method for speeding the approximation of both Chambolle's original method and of the new formulation of the upwind scheme. We demonstrate numerically that the multiscale method is effective, and we provide numerical examples that illustrate both the qualitative and quantitative behavior of the solutions of the numerical formulations.

Error bounds for finite-difference methods for Rudin-Osher-Fatemi image smoothing, by Jingyue Wang and Bradley J. Lucier, SIAM Journal on Numerical Analysis, 49 (2011), 845-868.

Abstract: We bound the difference between the solution to the continuous Rudin-Osher-Fatemi image smoothing model and the solutions to various finite-difference approximations to this model. These bounds apply to "typical" images, i.e., images with edges or with fractal structure. These are the first bounds on the error in numerical methods for ROF smoothing.