The presence of structure in a computational problem can often be exploited and can lead to a more efficient numerical algorithm. In this dissertation, we look at structured numerical problems that arise from applications in wireless communications and machine learning that also impact other areas of scientific computing. In wireless communication system designs, certain structured matrices (frames) need to be generated. The design of such matrices is equivalent to a symmetric inverse eigenvalue problem where the values of the diagonal elements are prescribed. We present algorithms that are capable of generating a larger set of these constructions than previous algorithms. We also discuss the existence of equiangular tight frames---frames that satisfy additional structural properties. Kernel learning is an important class of problems in machine learning. It often relies on efficient numerical algorithms that solve underlying convex optimization problems. In our work, the objective functions to be minimized are the von Neumann and the LogDet Bregman matrix divergences. The algorithm that solves this optimization problem performs matrix updates based on repeated eigendecompositions of diagonal plus rank-one matrices in the case of von Neumann matrix divergence, and Cholesky updates in case of the LogDet Bregman matrix divergence. Our contribution exploits the low-rank representations and the structure of the constraint matrices, resulting in more efficient algorithms than previously known. We also present two specialized zero-finding algorithms where we exploit the structure through the shape and exact formulation of the objective function. The first zero-finding task arises during the matrix update step which is part of the above-mentioned kernel learning application. The second zero-finding problem is for the secular equation; it is equivalent to the computation of the eigenvalues of a diagonal plus rank-one matrix. The secular equation arises in various applications, the most well-known is the divide-and-conquer eigensolver. In our solutions, we build upon a somewhat forgotten zero-finding method by P. Jarratt, first described in 1966. The method employs first derivatives only and needs the same amount of evaluations as Newton's method, but converges faster. Our contributions are the more efficient specialized zero-finding algorithms. / text

The biological diversity on planet Earth is astounding. Understanding the origins of this diversity, and how it is maintained, are the twin goals of ecology and evolutionary biology. An early and oft-repeated insight in this investigation is that that similar organisms cannot coexist indefinitely. Theory predicts that individuals and species will compete for limited resources and whichever has even a slight advantage will drive all others extinct in a process known as ‘competitive exclusion’. By diversifying, species avoid competition, thereby ‘stabilizing’ their coexistence. Yet natural systems often display levels of diversity that are surprisingly high, given this theory and investigations of how the similarity of coexisting species is maintained have received much less attention. Using a combination of field studies and experiments I demonstrate that highly similar species of freshwater amphipods may compete for resources without resulting in competitive exclusion. These findings suggest that there exist a range of interactions among Hyalella amphipods, ranging from strong stabilizing effects due to ecological trade-offs, to weakly stabilizing effects, to a total lack of stabilizing effects among various pairs of species in this system. These findings demonstrate how the relative strength of stabilizing forces may vary among coexisting species. Although much effort has been dedicated to enumerating and classifying the ways in which ecological and evolutionary forces promote diversity among species, there has been far less attention paid to mechanisms such as convergent evolution, habitat filtering, competition for non-substitutable resources, and non-ecological speciation, among others. I surveyed current theory that may explain the high levels of similarity among species often found in natural systems. I describe how several ecological and evolutionary mechanisms may operate to promote the coexistence of similar species and present results from new theoretical combinations of mechanisms to demonstrate how they may further act in concert with one another. / text

Graphics Processing Units (GPUs) have become a popular platform for executing general purpose (i.e., non-graphics) applications. To run efficiently on a GPU, applications must be parallelized into many threads, each of which performs the same task but operates on different data (i.e., data parallelism). Previous work has shown that some applications experience significant speedup when executed on a GPU instead of a CPU. The applications that benefit most tend to have certain characteristics such as high computational intensity, regular control-flow and memory access patterns, and little to no communication among threads. However, not all parallel applications have these characteristics. Applications with a more balanced compute to memory ratio, divergent control flow, irregular memory accesses, and/or frequent communication (i.e., not-so-regular applications) will not take full advantage of the GPU's resources, resulting in performance far short of what could be delivered. The goal of this dissertation is to enhance the GPU architecture to better handle not-so-regular parallelism. This is accomplished in two parts. First, I analyze a diverse set of data parallel applications that suffer from divergent control-flow and/or significant stall time due to memory. I propose two microarchitectural enhancements to the GPU called the Large Warp Microarchitecture and Two-Level Warp Scheduling to address these problems respectively. When combined, these mechanisms increase performance by 19% on average. Second, I examine one of the most important and fundamental applications in computing: database search. Database search is an excellent example of an application that is rich in parallelism, but rife with not-so-regular characteristics. I propose enhancements to the GPU architecture including new instructions that improve intra-warp thread communication and decision making, and also a row-buffer locality hint bit to better handle the irregular memory access patterns of index-based tree search. These proposals improve performance by 21% for full table scans, and 39% for index-based search. The result of this dissertation is an enhanced GPU architecture that better handles not-so-regular parallelism. This increases the scope of applications that run efficiently on the GPU, making it a more viable platform not only for current parallel workloads such as databases, but also for future and emerging parallel applications. / text

Two of the most challenging goals of evolutionary biology are to reconstruct the evolutionary relationships among all extant species and to understand the process by which new species form. Accomplishing these goals will require accurate computational methods for reconstructing phylogenetic trees, general analytic models of speciation, and powerful statistical tools for studying the process of speciation in natural systems. In the first chapter, I study the effects of improper model assumption on estimates of phylogeny. Using DNA sequence data simulated under a variety of models of sequence evolution, I demonstrate that use of oversimplified models can result in erroneous phylogeny estimates. This result suggests that if the models currently utilized are oversimplified then current estimates of phylogeny may be inaccurate and more complex models need to be developed and employed. In the second and third chapters, I study one process thought to be important in completing the final stages of speciation: reinforcement. Using simulations of a hybrid zone, I show that the process of reinforcement can result in patterns other than reproductive character displacement. I also show that speciation by reinforcement is more likely when the genes involved in reproductive isolation are sex-linked. In the fourth chapter, I develop a statistical method of quantifying the degree of isolation between species undergoing divergence. Using genotype data obtained from natural hybrid zones, this novel method can be used to estimate the fitness of hybrids during different stages of their life cycle. This approach offers a new approach to empirical biologists studying extrinsic postzygotic isolation in natural systems.

Die vorliegende Arbeit soll dazu beitragen, Unstimmigkeiten in den Verwandtschaftsverhältnissen innerhalb der Papionini, einem Stamm innerhalb der Altweltaffen (Cercopithecidae), zu klären. Die Papionini, die zusammen mit den Cercopithecini die Unterfamilie der Cercopithecinae bilden, beinhalten sieben Gattungen (Macaca, Cercocebus, Mandrillus, Lophocebus, Papio, Theropithecus, Rungwecebus) und 45 Arten. Sechs der sieben Gattungen kommen heute hauptsächlich in Afrika vor. Eine Ausnahme ist die Gattung Papio, die mit einer Art (P. hamadryas) auch in Südwest-Arabien vorkommt. Im Gegensatz zu den sechs hauptsächlich afrikanischen Gattungen hat die siebte Gattung (Macaca) nur ein kleines Verbreitungsgebiet im Norden Afrikas und kommt sonst hauptsächlich in Asien vor. Fossilfunde belegen allerdings, dass während des Plio- und Pleistozäns die Gattungen Macaca und Theropithecus auch in Europa vorkamen. Von der Gattung Theropithecus, die heute ausschließlich in Afrika beheimatet ist, wurden zudem auch Fossilien aus dem Pliozän im Norden Indiens gefunden. Die Verwandtschaftsbeziehungen innerhalb der Papionini wurden bisher mit Hilfe morphologischer und genetischer Merkmale untersucht, allerdings waren die Ergebnisse nicht immer übereinstimmend und es gibt immer noch viele Unklarheiten. Zum einen ist nicht eindeutig geklärt, wie die Gattungen Papio, Lophocebus und Theropithecus zu einander in Beziehung stehen. Zum anderen ist auch unklar, wie die einzelnen Pavianarten innerhalb der Gattung Papio mit einander verwandt sind. Außerdem sind auch die Verwandtschaftsverhältnisse zwischen und innerhalb der Artgruppen der Makaken nicht eindeutig geklärt. Um mehr Klarheit in die Evolution der Papionini zu bringen, habe ich im Rahmen dieser Arbeit drei Studien durchgeführt (Kapitel 2-4). Ziel dabei war es, Verwandtschaftsbeziehungen auf unterschiedlichen taxonomischen Ebenen (zwischen und innerhalb von Gattungen, sowie innerhalb einer Art) zu untersuchen. Dazu wurden komplette mitochondriale Genome von Vertretern der Papionini sequenziert und damit Phylogenien und Aufspaltungszeiten berechnet. Die Ergebnisse meiner Arbeit zeigen unter anderem drei Hauptkladen innerhalb der Papionini (Kapitel 2): 1) Papio, Theropithecus, Lophocebus; 2) Mandrillus, Cercocebus; 3) Macaca, wobei Macaca in der mitochondrialen Phylogenie näher mit Mandrillus und Cercocebus verwandt zu seien scheint und nicht wie erwartet, als Schwestergruppe der afrikanischen Papionini abgebildet wird; ein Ergebnis, das im Widerspruch zu nukleären und morphologischen Studien steht. Meine Arbeit zeigt auch, dass komplette mitochondriale Genome in manchen Fällen nicht ausreichen, um phylogenetische Beziehungen vollständig zu rekonstruieren. So bleibt weiterhin unklar wie die Gattungen Papio, Theropithecus und Lophocebus zueinander stehen (Kapitel 2). Außerdem zeigen die Ergebnisse Paraphylien für Mandrillus und Cercocebus (Kapitel 2), sowie innerhalb der Paviane (Kapitel 3). Die Paviane werden dabei gemäß ihrer geographischen Verbreitung und nicht nach ihrer taxonomischen Zugehörigkeit abgebildet, wodurch die meisten Pavian-Arten paraphyletisch sind. Der Grund für diese Baumtopologie ist sehr wahrscheinlich sekundärer Genfluss zwischen parapatrisch vorkommenden Pavian-Arten. In der dritten Studie (Kapitel 4), in der innerartliche Verwandtschaftsverhältnisse innerhalb einer südostasiatischen Makaken-Artgruppe (Macaca fascicularis) untersucht wurden, zeigt sich eine klare Unterteilung in eine kontinentale und eine insulare Klade. Sowohl die kontinentale, als auch die insulare Linie sind auf Sumatra zu finden, was für einen sekundären genetischen Austausch zwischen beiden Populationen spricht. Generell kann man sagen, dass komplette mitochondriale Genome robuste Phylogenien mit hoher statistischer Unterstützung ergeben, die eine gute Grundlage für künftige vergleichende Studien bilden. Die berechneten Aufspaltungszeiten stimmen weitestgehend mit vorherigen Studien überein, wobei sich die ermittelten Konfidenzintervalle verkleinert haben. Allerdings zeigt die Arbeit auch, dass Phylogenien basierend auf mitochondrialen Genomen keine hohe Auflösung erzielen wenn sich Taxa innerhalb kurzer Zeit voneinander trennten. Die hier gezeigten Paraphylien und die abweichenden Ergebnisse zu nukleären Studien wurden höchstwahrscheinlich durch sekundären genetischen Austausch hervorgerufen. Um Verwandtschaftsverhältnisse möglichst exakt rekonstruieren zu können, müssen neben der maternal-vererbten, mitochondrialen Linie noch paternal- und biparentalvererbte Merkmale in Betracht gezogen werden. Zu beachten ist in diesem Zusammenhang, dass ein bestimmter molekularer Marker immer nur eine mögliche Phylogenie von vielen wiedergibt.

This thesis investigates automatic geolocation (i.e. identification of the location, expressed as latitude/longitude coordinates) of documents. Geolocation can be an effective means of summarizing large document collections and is an important component of geographic information retrieval. We describe several simple supervised methods for document geolocation using only the document’s raw text as evidence. All of our methods predict locations in the context of geodesic grids of varying degrees of resolution. We evaluate the methods on geotagged Wikipedia articles and Twitter feeds. For Wikipedia, our best method obtains a median prediction error of just 11.8 kilometers. Twitter geolocation is more challenging: we obtain a median error of 479 km, an improvement on previous results for the dataset. / text

Stochastic programming is a mathematical technique for decision making under uncertainty using probabilistic statements in the problem objective and constraints. In practice, the distribution of the unknown quantities are often known only through observed or simulated data. This dissertation discusses several methods of using this data to formulate, solve, and evaluate the quality of solutions of stochastic programs. The central contribution of this dissertation is to investigate the use of techniques from simulation and statistics to enable data-driven models and methods for stochastic programming. We begin by extending the method of overlapping batches from simulation to assessing solution quality in stochastic programming. The Multiple Replications Procedure, where multiple stochastic programs are solved using independent batches of samples, has previously been used for assessing solution quality. The Overlapping Multiple Replications Procedure overlaps the batches, thus losing the independence between samples, but reducing the variance of the estimator without affecting its bias. We provide conditions under which the optimality gap estimators are consistent, the variance reduction benefits are obtained, and give a computational illustration of the small-sample behavior. Our second result explores the use of phi-divergences for distributionally robust optimization, also known as ambiguous stochastic programming. The phi-divergences provide a method of measuring distance between probability distributions, are widely used in statistical inference and information theory, and have recently been proposed to formulate data-driven stochastic programs. We provide a novel classification of phi-divergences for stochastic programming and give recommendations for their use. A value of data condition is derived and the asymptotic behavior of the phi-divergence constrained stochastic program is described. Then a decomposition-based solution method is proposed to solve problems computationally. The final portion of this dissertation applies the phi-divergence method to a problem of water allocation in a developing region of Tucson, AZ. In this application, we integrate several sources of uncertainty into a single model, including (1) future population growth in the region, (2) amount of water available from the Colorado River, and (3) the effects of climate variability on water demand. Estimates of the frequency and severity of future water shortages are given and we evaluate the effectiveness of several infrastructure options.

Sub-pixel image alignment estimation is desirable for co-registration of objects in multiple images to a common spatial reference and as alignment input to multi-image processing. Applications include super-resolution, image fusion, change detection, object tracking, object recognition, video motion tracking, and forensics.Information theoretical measures are commonly used for co-registration in medical imaging. The published methods apply Shannon's Entropy to the Joint Measurement Space (JMS) of two images. This work introduces into the same context a new set of statistical divergence measures derived from Fisher Information. The new methods described in this work are applicable to uncorrelated imagery and imagery that becomes statistically least dependent upon co-alignment. Both characteristics occur with multi-modal imagery and cause cross-correlation methods, as well as maximum dependence indicators, to fail. Fisher Information-based estimators, together as a set with an Entropic estimator, provide substantially independent information about alignment. This increases the statistical degrees of freedom, allowing for precision improvement and for reduced estimator failure rates compared to Entropic estimator performance alone.The new Fisher Information methods are tested for performance on real remotely-sensed imagery that includes Landsat TM multispectral imagery and ESR SAR imagery, as well as randomly generated synthetic imagery. On real imagery, the co-registration cost function is qualitatively examined for features that reveal the correct point of alignment. The alignment estimates agree with manual alignment to within manual alignment precision. Alignment truth in synthetic imagery is used to quantitatively evaluate co-registration accuracy. The results from the new Fisher Information-based algorithms are compared to Entropy-based Mutual Information and correlation methods revealing equal or superior precision and lower failure rate at signal-to-noise ratios below one.

Approximation and interpolation employing radial basis functions has found important applications since the early 1980's in areas such as signal processing, medical imaging, as well as neural networks. Several applications demand that certain physical properties be fulfilled, such as a function being divergence free. No such class of radial basis functions that reflects these physical properties was known until 1994, when Narcowich and Ward introduced a family of matrix-valued radial basis functions that are divergence free. They also obtained error bounds and stability estimates for interpolation by means of these functions. These divergence-free functions are very smooth, and have unbounded support. In this thesis we introduce a new class of matrix-valued radial basis functions that are divergence free as well as compactly supported. This leads to the possibility of applying fast solvers for inverting interpolation matrices, as these matrices are not only symmetric and positive definite, but also sparse because of this compact support. We develop error bounds and stability estimates which hold for a broad class of functions. We conclude with applications to the numerical solution of the Navier-Stokes equation for certain incompressible fluid flows.

Kompiuterinis geometrinis sklandytuvo Lak-17 modelis sugeneruotas programa AVL, kuri skirta orlaivių konfigūracijos ir skrydžio charakteristikų analizei. Imituojant realų skrydį programa suskaičiuotos įvairios šoninio stabilumo charakteristikos. Tirta, kaip šoninio stabilumo savyb÷ms, tokioms kaip krypties nestabilumas, spiralinis nestabilumas, „olandiškas žingsnis“, turi įtakos skersinio V kampo didinimas ar mažinimas, vertikalios uodegos plokštumos ploto keitimas. Pagal gautus rezultatus suformuluotos išvados kiekvienam šoninio nestabilumo atvejui. Darbą sudaro 3 dalys: įvadas, problemos analiz÷, AVL programos apžvalga, tyrimas, išvados, literatūros sąrašas. Darbo apimtis – 92 p. 65 p. teksto be priedų, 82 iliustr., 6 lent. Atskirai pridedami priedai. / Computer-based geometrical model of sailplane Lak-17 was generated with a program AVL (Athena Vortex Lattice), which is designed for analysis of characteristics of flight and rapid analysis of configuration of aircraft. Analysis was done how increasing and decreasing of wing dihedral and exchange of vertical tail area characteristics are influenced on lateral stability like directional divergence, spiral divergence and „dutch roll“. Simulating a real flight with the program various characteristics of stability and control were calculated. According results the conclusion was formulated for every case of lateral unstability. Structure: introduction, problem analysis, AVL overview, research, conclusions, references. Thesis consist of – 92 p. 65 p. text without appendixes, 82 pictures, 6 tables. Appendixes are included.