# Browsing by Subject "Applied Mathematics"

###### Results Per Page

###### Sort Options

Item Open Access Asymptotic Analysis and Performance-based Design of Large Scale Service and Inventory Systems(2010) Talay Degirmenci, IsilayMany types of services are provided using some equipment or machines, e.g. transportation systems using vehicles. Designs of these systems require capacity decisions, e.g., the number of vehicles. In my dissertation, I use many-server and conventional heavy-traffic limit theory to derive asymptotically optimal capacity decisions, giving the desired level of delay and availability performance with minimum investment. The results provide near-optimal solutions and insights to otherwise analytically intractable problems.

The dissertation will comprise two essays. In the first essay, &ldquoAsymptotic Analysis of Delay-based Performance Metrics and Optimal Capacity Decisions for the Machine Repair Problem with Spares,&rdquo I study the M/M/R machine repair problem with spares. This system can be represented by a closed queuing network. Applications include fleet vehicles' repair and backup capacity, warranty services' staffing and spare items investment decisions. For these types of systems, customer satisfaction is essential; thus, the delays until replacements of broken units are even more important than delays until the repair initiations of the units. Moreover, the service contract may include conditions on not only the fill rate but also the probability of acceptable delay (delay being less than a specified threshold value).

I address these concerns by expressing delays in terms of the broken-machines process; scaling this process by the number of required operating machines (or the number of customers in the system); and using many-server limit theorems (limits taken as the number of customers goes to infinity) to obtain the limiting expected delay and probability of acceptable delay for both delay until replacement and repair initiation. These results lead to an approximate optimization problem to decide on the repair and backup-capacity investment giving the minimum expected cost rate, subject to a constraint on the acceptable delay probability. Using the characteristics of the scaled broken-machines process, we obtain insights about the relationship between quality of service and capacity decisions. Inspired by the call-center literature, we categorize capacity level choice as efficiency-driven, quality-driven, or quality- and efficiency-driven. Hence, our study extends the conventional call center staffing problem to joint staffing and backup provisioning. Moreover, to our knowledge, the machine-repair problem literature has focused mainly on mean and fill rate measures of performance for steady-state cost analysis. This approach provides complex, nonlinear expressions not possible to solve analytically. The contribution of this essay to the machine-repair literature is the construction of delay-distribution approximations and a near-optimal analytical solution. Among the interesting results, we find that for capacity levels leading to very high utilization of both spares and repair capacity, the limiting distribution of delay until replacement depends on one type of resource only, the repair capacity investment.

In the second essay, &ldquoDiffusion Approximations and Near-Optimal Design of a Make-to-Stock Queue with Perishable Goods and Impatient Customers,&rdquo I study a make-to-stock system with perishable inventory and impatient customers as a two-sided queue with abandonment from both sides. This model describes many consumer goods, where not only spoilage but also theft and damage can occur. We will refer to positive jobs as individual products on the shelf and negative jobs as backlogged customers. In this sense, an arriving negative job provides the service to a waiting positive job, and vice versa. Jobs that must wait in queue before potential matching are subject to abandonment. Under certain assumptions on the magnitude of the abandonment rates and the scaled difference between the two arrival rates (products and customers), we suggest approximations to the system dynamics such as average inventory, backorders, and fill rate via conventional heavy traffic limit theory.

We find that the approximate limiting queue length distribution is a normalized weighted average of two truncated normal distributions and then extend our results to analyze make-to-stock queues with/without perishability and limiting inventory space by inducing thresholds on the production (positive) side of the queue. Finally, we develop conjectures for the queue-length distribution for a non-Markovian system with general arrival streams. We take production rate as the decision variable and suggest near-optimal solutions.

Item Open Access Bayesian Model Uncertainty and Prior Choice with Applications to Genetic Association Studies(2010) Wilson, Melanie AnnThe Bayesian approach to model selection allows for uncertainty in both model specific parameters and in the models themselves. Much of the recent Bayesian model uncertainty literature has focused on defining these prior distributions in an objective manner, providing conditions under which Bayes factors lead to the correct model selection, particularly in the situation where the number of variables, p, increases with the sample size, n. This is certainly the case in our area of motivation; the biological application of genetic association studies involving single nucleotide polymorphisms. While the most common approach to this problem has been to apply a marginal test to all genetic markers, we employ analytical strategies that improve upon these marginal methods by modeling the outcome variable as a function of a multivariate genetic profile using Bayesian variable selection. In doing so, we perform variable selection on a large number of correlated covariates within studies involving modest sample sizes.

In particular, we present an efficient Bayesian model search strategy that searches over the space of genetic markers and their genetic parametrization. The resulting method for Multilevel Inference of SNP Associations MISA, allows computation of multilevel posterior probabilities and Bayes factors at the global, gene and SNP level. We use simulated data sets to characterize MISA's statistical power, and show that MISA has higher power to detect association than standard procedures. Using data from the North Carolina Ovarian Cancer Study (NCOCS), MISA identifies variants that were not identified by standard methods and have been externally 'validated' in independent studies.

In the context of Bayesian model uncertainty for problems involving a large number of correlated covariates we characterize commonly used prior distributions on the model space and investigate their implicit multiplicity correction properties first in the extreme case where the model includes an increasing number of redundant covariates and then under the case of full rank design matrices. We provide conditions on the asymptotic (in n and p) behavior of the model space prior

required to achieve consistent selection of the global hypothesis of at least one associated variable in the analysis using global posterior probabilities (i.e. under 0-1 loss). In particular, under the assumption that the null model is true, we show that the commonly used uniform prior on the model space leads to inconsistent selection of the global hypothesis via global posterior probabilities (the posterior probability of at least one association goes to 1) when the rank of the design matrix is finite. In the full rank case, we also show inconsistency when p goes to infinity faster than the square root of n. Alternatively, we show that any model space prior such that the global prior odds of association increases at a rate slower than the square root of n results in consistent selection of the global hypothesis in terms of posterior probabilities.

Item Open Access Estimating the Intrinsic Dimension of High-Dimensional Data Sets: A Multiscale, Geometric Approach(2011) Little, Anna VictoriaThis work deals with the problem of estimating the intrinsic dimension of noisy, high-dimensional point clouds. A general class of sets which are locally well-approximated by k dimensional planes but which are embedded in a D>>k dimensional Euclidean space are considered. Assuming one has samples from such a set, possibly corrupted by high-dimensional noise, if the data is linear the dimension can be recovered using PCA. However, when the data is non-linear, PCA fails, overestimating the intrinsic dimension. A multiscale version of PCA is thus introduced which is robust to small sample size, noise, and non-linearities in the data.

Item Open Access Maximum Norm Regularity of Implicit Difference Methods for Parabolic Equations(2011) Pruitt, MichaelWe prove maximum norm regularity properties of L-stable finite difference

methods for linear-second order parabolic equations with coefficients

independent of time, valid for large time steps. These results are almost

sharp; the regularity property for first differences of the numerical solution

is of the same form as that of the continuous problem, and the regularity

property for second differences is the same as the continuous problem except for

logarithmic factors.

This generalizes a result proved by Beale valid for the constant-coefficient

diffusion equation, and is in the spirit of work by Aronson, Widlund and

Thomeé.

To prove maximum norm regularity properties for the homogeneous problem,

we introduce a semi-discrete problem (discrete in space, continuous in time).

We estimate the semi-discrete evolution operator and its spatial differences on

a sector of the complex plan by constructing a fundamental solution.

The semi-discrete fundamental solution is obtained from the fundamental solution to the frozen coefficient problem by adding a correction term found through an iterative process.

From the bounds obtained on the evolution operator and its spatial differences,

we find bounds

on the resolvent of the discrete elliptic operator and its differences through

the Laplace transform

representation of the resolvent. Using the resolvent estimates and the

assumed stability properties of the time-stepping method in the Cauchy integral

representation of the fully discrete solution operator

yields the homogeneous regularity result.

Maximum norm regularity results for the inhomogeneous

problem follow from the homogeneous results using Duhamel's principle. The results for the inhomogeneous

problem

imply that when the time step is taken proportional to the grid width, the rate of convergence of the numerical solution and its first

differences is second-order in space, and the rate of convergence for second

differences

is second-order except for logarithmic factors .

As an application of the theory, we prove almost sharp maximum norm resolvent estimates for divergence

form elliptic operators on spatially periodic grid functions. Such operators are invertible, with inverses and their first differences bounded in maximum norm, uniformly in the grid width. Second differences of the inverse operator are bounded except for logarithmic factors.

Item Open Access On Computing Smooth, Singular, and Nearly Singular Integrals on Implicitly Defined Surfaces(2010) Wilson, Jason R.We present numerical methods for the approximation of smooth, singular, and nearly singular integrals on implicitly defined surfaces. We begin with a high-order quadrature formula for an integral over a compact smooth implicitly defined hypersurface. Our high-order formula is novel in that it has spectral convergence but does not require a set of overlapping patches. Rather, certain hypersurface points, called quadrature points, must be determined. To find the quadrature points, we search for certain line segments, called brackets, for which the level set function has a sign change at the endpoints. We show that as the segment spacing tends to zero, that each quadrature point must be eventually contained in exactly one bracket. To find the quadrature point within a bracket we use standard one dimensional root finding techniques. Next, we show how to accelerate the process of finding the brackets by restricting the line segment search to cells that are near the hypersurface. Finally, we give an optimal algorithm for finding the quadrature points that has an observed runtime proportional to the number of quadrature points. The high-order convergence of our new quadrature formula is demonstrated numerically on a number of complex implicitly defined surfaces and smooth integrands. Using standard interpolation and finite differencing techniques, we show how to achieve high-order accuracy in the case where the level-set function and integrand are only known at regularly spaced grid points.

We next address the problem of computing double layer and single layer potentials. By using a locally flat cutoff function, we decompose the layer potential into a global part and a local part. We numerically verify that our new quadrature formula has high-order convergence when applied to the global part of a singular double layer potential by computing Gauss's integral on a number of complex implicitly defined surfaces. For the local part, we focus on the single layer potential. In particular, we give a constant runtime complexity algorithm for evaluating the local part of a single layer potential for both the singular and nearly singular cases. To compute the local part, we write the integral in certain local polar coordinates and consider the angular and radial parts separately. We first prove that the angular part can be approximated to high order using the trapezoid rule. In particular, we show that due to our choice of local coordinates, the integrand of the angular part is well approximated by a low degree trigonometric polynomial which is integrated exactly by the trapezoid rule with a small number of quadrature points. We next show that by multiplying the radial integrands by certain helper functions and using a change of variable, the radial integrals can be written in terms of standard integrals that can be precomputed and stored in a lookup table. We demonstrate the high-order convergence of our constant runtime local single layer potential integration method with a number of numerical examples on complex implicitly defined surfaces.

Item Open Access Stable Embedded Grid Techniques in Computational Mechanics(2010) Sanders, JessicaEngineering mechanics problems involving interfaces, whether physical or introduced by numerical methodologies, are commonplace. Just a few examples include fracture and fault mechanics, classical contact-impact, phase boundary propagation, and fluid-structure interaction. This dissertation focuses on issues of numerical stability and accuracy that must be addressed when such interfaces are included in a realistic simulation of a physical system.

We begin by presenting a novel numerical method of fluid/structure interaction that may be applied to the problem of movable devices and ocean waves. The work is done with finite differences, large motion Lagrangian mechanics, and an eye towards creating a model in which complex rigid body dynamics can be incorporated.

We then review the many advantages of embedded mesh techniques for interface representation, and investigate a completely finite element based strategy for embedding domains. The work is seen as a precursor to robust multi-physics simulation capabilities. Special attention must be given to these techniques in terms of stable and convergent representation of surface fluxes. Mesh locking and over-constraint are particularly addressed. We show that traditional methods for enforcing continuity at embedded interfaces cannot adequately guarantee flux stability, and show a less traditional method, known as Nitsche's method, to be a stable alternative. We address the open problem of applying Nitsche's method to non-linear analysis by drawing parallels between the embedded mesh and discontinuous Galerkin (DG) methods, and propose a DG style approach to Nitsche's method. We conclude with stable interfacial fluxes for a continuity constraint for a case of embedded finite element meshes in large deformation elasticity. The general conclusion is drawn that stability must be addressed in the choice of interface treatment in computational mechanics.