Computer Science Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2756
Browse
69 results
Search Results
Item Novel integro-differential schemes for multiscale image representation(2009) Athavale, Prashant Vinayak; Tadmor, Eitan; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Multiscale representation of a given image is the problem of constructing a family of images, where each image in this family represents a scaled version of the given image. This finds its motivation from biological vision studies. Using the hierarchical multiscale image representation proposed by Tadmor et. al. [32], an image is decomposed into sums of simpler `slices', which extract more refined information from the previous scales. This approach motivates us to propose a novel integro-differential equation (IDE), for a multiscale image representation. We examine various properties of this IDE. The advantage of formulating the IDE this way is that, although this IDE is motivated by variational approach, we no longer need to be associated with any minimization problem and can modify the IDE, suitable to our image processing needs. For example, we may need to find different scales in the image, while retaining or enhancing prominent edges, which may define boundaries of objects. We propose some edge preserving modifications to our IDE. One of the important problems in image processing is deblurring a blurred image. Images get blurred due to various reasons, such as unfocused camera lens, relative motion between the camera and the object pictured, etc. The blurring can be modeled with a continuous, linear operator. Recovering a clean image from a blurry image, is an ill-posed problem, which is solved using Tikhonov-like regularization. We propose a different IDE to solve the deblurring problem. We propose hierarchical multiscale scheme based on (BV; L1) decomposition, proposed by Chan, Esedoglu, Nikolova and Alliney [12, 25, 3]. We finally propose another hierarchical multiscale representation based on a novel weighted (BV;L1) decomposition.Item Numerical solution of eigenvalue problems with spectral transformations(2009) Xue, Fei; Elman, Howard; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This thesis is concerned with inexact eigenvalue algorithms for solving large and sparse algebraic eigenvalue problems with spectral transformations. In many applications, if people are interested in a small number of interior eigenvalues, a spectral transformation is usually employed to map these eigenvalues to dominant ones of the transformed problem so that they can be easily captured. At each step of the eigenvalue algorithm (outer iteration), the matrix-vector product involving the transformed linear operator requires the solution of a linear system of equations, which is generally done by preconditioned iterative linear solvers inexactly if the matrices are very large. In this thesis, we study several efficient strategies to reduce the computational cost of preconditioned iterative solution (inner iteration) of the linear systems that arise when inexact Rayleigh quotient iteration, subspace iteration and implicitly restarted Arnoldi methods are used to solve eigenvalue problems with spectral transformations. We provide new insights into a special type of preconditioner with ``tuning'' that has been studied in the literature and propose new approaches to use tuning for solving the linear systems in this context. We also investigate other strategies specific to eigenvalue algorithms to further reduce the inner iteration counts. Numerical experiments and analysis show that these techniques lead to significant savings in computational cost without affecting the convergence of outer iterations to the desired eigenpairs.Item Mining of Business Data(2009) Zhang, Shu; Jank, Wolfgang; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Applying statistical tools to help understand business processes and make informed business decisions has attracted enormous amount of research interests in recent years. In this dissertation, we develop and apply data mining techniques to two sources of data, online bidding data for eBay and offline sales transaction data from a grocery product distributor. We mine online auction data to develop forecasting models and bidding strategies and mine offline sales transaction data to investigate sales people's price formation process. We start with discussing bidders' bidding strategies in online auctions. Conventional bidding strategies do not help bidders select an auction to bid on. We propose an automated and data-driven strategy which consists of a dynamic forecasting model for auction closing price and a bidding framework built around this model to determine the best auction to bid on and the best bid amount. One important component of our bidding strategy is a good forecasting model. We investigate forecasting alternatives in three ways. Firstly, we develop model selection strategies for online auctions (Chapter 3). Secondly, we propose a novel functional K-nearest neighbor (KNN) forecaster for real time forecasting of online auctions (Chapter 4). The forecaster uses information from other auctions and weighs their contribution by their relevance in terms of auction features. It improves the predictive performance compared to several competing models across various levels of data heterogeneity. Thirdly, we develop a Beta model (Chapter 5) for capturing auction price paths and find this model has advantageous forecasting capability. Apart from online transactions, we also employ data mining techniques to understand offline transactions where sales representatives (salesreps) serve as media to interact with customers and quote prices. We investigate the mental models for salesreps' decision making, and find that price recommendation makes salesreps concentrate on cost related information. In summary, the dissertation develops various data mining techniques for business data. Our study is of great importance for understanding auction price formation processes, forecasting auction outcomes, optimizing bidding strategies, and identifying key factors in sales people's decision making. Those techniques not only advance our understanding of business processes, but also help design business infrastructure.Item Diagnostics for Nonlinear Mixed-Effects Models(2009) Nagem, Mohamed Ould; Kedem, Benjamin; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The estimation methods in Nonlinear Mixed-Effects Models (NLMM) still largely rely on numerical approximation of the likelihood function and the properties of these methods are yet to be characterized. These methods are available in most statistical software packages, such as S-plus and SAS; However approaches on how to assess the reliability of these estimation methods are still open to debate. Moreover, the lack of a common measure to capture the best fitted model is still an open area of research. Common Software packages such as SAS and S-plus do not provide a specific method for computing such a measure other than the traditional Akaike's Information Criterion (AIC) Akaike [2], Bayesian Information Criterion (BIC) Schwarz [38], or the likelihood ratio. These methods are comparative in nature and are very hard to interpret in this context due to the complex structure and dependent nature of the populations that they were intended to analyze. This dissertation focuses on approximate methods of estimating parameters of NLMM. In chapter 1, the general form of a NLMM is introduced and real data examples are presented to illustrate the usefulness of NLMM where a standard regression model is not appropriate. A general review of the approximation methods of the log-likelihood function is described. In chapter 2, we compared three approximation techniques, which are widely used in the estimation of NLMM, based on simulation studies. In this chapter we compared these approx- imation methods through extensive simulation studies motivated by two widely used data sets. We compared the empirical estimates from three different approximations of the log-likelihood function and their bias, precision, convergence rate, and the 95% confidence interval coverage probability. We compared the First Order approximation (FO) of Beal and Sheiner [5], the Laplace approximation (LP) of Wolfinger [49], and the Gaussian Quadrature (GQ) of Davidian and Gallant [10]. We also compared these approaches under different sample size configurations and analyzed their effects on both fixed effects estimates and the precision measures. The question of which approximation yields the best estimates and the degree of precision associated with it seems to depend greatly on many aspects. We explored some of these aspects such as the magnitude of variability among the random effects, the random parameters covariance structure, and the way in which such random parameters enter the model as well as the \linearity" or the "close to linearity" of the model as a function of these random parameters. We concluded that, while no method outperformed the others on a consistent basis, both the GQ and LP methods provided the most accurate estimates. The FO method has the advantage that it is exact when the model is linear in the random effects. It also has the advantage of being computationally simple and provides reasonable convergence rates. In chapter 3 we investigated the robustness and sensitivity of the three approximation techniques to the structure of the random effect parameters, the dimension of these parameters, and the correlation structure of the covariance matrix. We expanded the work of Hartford and Davidian [18] to assess the robustness of these approximation methods under different scenarios (models) of random effect covariance structures:(1) Under the assumption of single random effect models;(2) under the assumption of correlated random effect models;(3) under the assumption of non-correlated random effect models. We showed that the LP and GQ methods are very similar and provided the most accurate estimates. Even though the LP is fairly robust to mild deviations, the LP estimates can be extremely biased due to the difficulty of achieving convergence. The LP method is sensitive to misspecification of the inter-individual model. In chapter 4 we evaluated the Goodness of Fit measure (GOF) of Hosmer et. al. [20] and Sturdivant and Hosmer [43] to a class of NLMM and evaluated the asymptotic sum of residual squares statistics as a measure of goodness of fit by conditioning the response on the random effect parameter and using Taylor series approximations in the estimation technique. Simulations of different mixed logistic regression models were evaluated, as well as the effect of the sample size on such statistics. We showed that the proposed sum of squares residual statistics works well for a class of mixed logistic regression models with the presence of continuous covariates with a modest sample size dataset. However, the same statistics failed to provide an adequate power to detect the correct model in the presence of binary covariates.Item A Macroscale Perspective of Near-equilibrium Relaxation of Stepped Crystal Surfaces(2009) Quah, John; Margetis, Dionisios; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Crystal surfaces serve a crucial function as building blocks in small electronic devices, especially for mobile communications technology and photovoltaics. In the history of computing, for example, a crucial innovation that hastened the demise of vacuum tube computers was the etching of patterns on surfaces of semiconductor materials, which led to the integrated circuit. These early procedures typically worked with the materials at very high temperatures, where the thermally rough surface could be modeled from the perspective of continuum thermodynamics. More recently, with the drive towards smaller devices and the accompanying reduction of the lifetime of surface features, manufacturing conditions for the shaping of crystal surfaces have shifted to lower temperatures. At these lower temperatures the surface is no longer rough. In order to describe an evolving surface under typical experimental conditions today, we need to consider the processes that take place at the nanoscale. Nanoscale descriptions of surface evolution start with the motion of adsorbed atoms (adatoms). Because of their large numbers, the concentration of adatoms is a meaningful object to study. Restricted to certain bounded regions of the surface, the adatom concentration satisfies a diffusion equation. At the boundaries between these regions, the hopping of adatoms is governed by kinetic laws. Real-time observation of these nanoscale processes is difficult to achieve, and experimentalists have had to devise creative methods for inferring the relevant energy barriers and kinetic rates. In contrast, the real-time observation of macroscale surface evolution can be achieved with simpler imaging techniques. Motivated by the possibility of experimental validation, we derive an equation for the macroscale surface height, which is consistent with the motion of adatoms. We hope to inspire future comparison with experiments by reporting the novel results of simulating the evolution of the macroscale surface height. Many competing models have been proposed for the diffusion and kinetics of adatoms. Due to the difficulty of observing adatom motion at the nanoscale, few of the competing models can be dismissed outright for failure to capture the observed behavior. This dissertation takes a few of the nanoscale models and systematically derives the corresponding macroscopic evolution laws, of which some are implemented numerically to provide data sets for connection with experiments. For the modeling component of this thesis, I study the effect of anisotropic adatom diffusion at the nanoscale, the inclusion of an applied electric field, the desorption of adatoms, and the extension of linear kinetics in the presence of step permeability. Analytical conjectures based on the macroscale evolution equation are presented. For the numerical component of this thesis, I select a few representative simulations using the finite element method to illustrate the most salient features of the surface evolution.Item Ensemble Data Assimilation and Breeding in the Ocean, Chesapeake Bay, and Mars(2009) Hoffman, Matthew Joseph; Kalnay, Eugenia; Carton, James A; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)My dissertation focuses on studying instabilities of different time scales using breeding and data assimilation in the oceans, as well as the Martian atmosphere. The breeding method of Toth and Kalnay finds the perturbations that grow naturally in a dynamical system like the atmosphere or the ocean. Here breeding is applied to a global ocean model forced by reanalysis winds in order to identify instabilities on weekly and monthly timescales. The method is extended to show how the energy equations for the bred vectors can be derived with only very minimal approximations and used to assess the physical mechanisms that give rise to the instabilities. Tropical Instability Waves in the tropical Pacific are diagnosed, confirming the existence of bands of both baroclinic and barotropic energy conversions indicated by earlier studies. For regional prediction of smaller timescale phenomena, an advanced data assimilation system has been developed for the Chesapeake Bay Forecast System, a regional Earth System Prediction model. To accomplish this, the Regional Ocean Modeling System (ROMS) implementation on the Chesapeake Bay has been interfaced with the Local Ensemble Transform Kalman Filter (LETKF). The LETKF is among the most advanced data assimilation methods and is very effective for large, non-linear dynamical systems in both sparse and dense data coverage situations. In perfect model experiments using ChesROMS, the filter converges quickly and reduces the analysis and subsequent forecast errors in the temperature, salinity, and velocity fields. This error reduction has proved fairly robust to sensitivity studies such as reduced data coverage and realistic data coverage experiments. The LETKF also provides a method for error estimation and facilitates the investigation of the spatial distribution of the error. This information has been used to determine areas where more monitoring is needed. The LETKF framework is also applied here to a global model of the Martian atmosphere. Sensitivity experiments are performed to determine the dependence of the assimilation on observational data. Observations of temperature are simulated at realistic vertical and horizontal levels and LETKF performance is evaluated. Martian instabilities that impact the assimilation are also addressed.Item Metastability in Nearly-Hamiltonian Systems(2009) Athreya, Dwijavanti; Freidlin, Mark I; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)We characterize the phenomenon of metastability for a small random perturbation of a nearly-Hamiltonian dynamical system with one degree of freedom. We use the averaging principle and the theory of large deviations to prove that a metastable state is, in general, not a single state but rather a nondegenerate probability measure across the stable equilibrium points of the unperturbed Hamiltonian system. The set of all possible ``metastable distributions" is a finite set that is independent of the stochastic perturbation. These results lead to a generalization of metastability for systems close to Hamiltonian ones.Item TOPOLOGICAL CHARGE OF REAL FINITE-GAP SINE-GORDON SOLUTIONS(2009) Kaipa, Krishna Vinod; Novikov, Sergei P; Ramachandran, Niranjan; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The most basic characteristic of x-quasiperiodic solutions u(x, t) of the sine-Gordon equation u_{tt} -u_{xx} + sin u = 0 is the topological charge density. The real finite-gap solutions u(x, t) are expressed in terms of the Riemann theta-functions of a non-singular hyperelliptic curve, $Gamma$ and a positive generic divisor D of degree g on $Gamma$ , where the spectral data ($Gamma$ ,D) must satisfy some reality conditions. The problem addressed in this dissertation is: to calculate the topological charge density from the theta-functional expressions for the solution u(x, t). This problem has remained unsolved since it was first raised by S.P. Novikov in 1982. The problem is solved here by introducing a new limit of real finite-gap sine-Gordon solutions, which we call the multiscale or elliptic limit. We deform the spectral curve to a singular nodal curve, having elliptic curves as components, for which the calculation of topological charges reduces to two special easier cases.Item Column Generation in Infeasible Predictor-Corrector Methods for Solving Linear Programs(2009) Nicholls, Stacey Oneeta; O'Leary, Dianne P.; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Primal &ndash dual interior &ndash point methods (IPMs) are distinguished for their exceptional theoretical properties and computational behavior in solving linear programming (LP) problems. Consider solving the primal &ndash dual LP pair using an IPM such as a primal &ndash dual Affine &ndash Scaling method, Mehrotra's Predictor &ndash Corrector method (the most commonly used IPM to date), or Potra's Predictor &ndash Corrector method. The bulk of the computation in the process stems from the formation of the normal equation matrix, AD2A T, where A \in \Re {m times n} and D2 = S{-1}X is a diagonal matrix. In cases when n >> m, we propose to reduce this cost by incorporating a column generation scheme into existing infeasible IPMs for solving LPs. In particular, we solve an LP problem based on an iterative approach where we select a &ldquo small &rdquo subset of the constraints at each iteration with the aim of achieving both feasibility and optimality. Rather than n constraints, we work with k = |Q| \in [m,n] constraints at each iteration, where Q is an index set consisting of the k most nearly active constraints at the current iterate. The cost of the formation of the matrix, AQ DQ2 AQT, reduces from &theta(m2 n) to &theta(m2 k) operations, where k is relatively small compared to n. Although numerical results show an occasional increase in the number of iterations, the total operation count and time to solve the LP using our algorithms is, in most cases, small compared to other &ldquo reduced &rdquo LP algorithms.Item Barker Sequences Theory and Applications(2009) MacDonald, Kenneth; Benedetto, John; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)A Barker sequence is a finite length binary sequence with the minimum possible aperiodic autocorrelation. Currently, only eight known Barker sequences exist and it has been conjectured that these are the only Barker sequences that exist. This thesis proves that long sequences (having length longer than thirteen) must have an even length and be a perfect square. Barker sequences are then used to explore flatness problems related to Littlewood polynomials. These theorems could be used to determine the existence or non-existence of longer sequences. Lastly, an application of Barker sequences is given. Barker sequences were initially investigated for the purposes of pulse compression in radar systems. This technique results in better range and Doppler resolution without the need to shorten a radar pulse, nor increase the power.