This thesis proposes a novel anomaly detection algorithm for detect-ing anomalies in high-dimensional, multimodal, real-valued time se-ries data. The approach, requiring no domain knowledge, is based on Stochastic Recurrent Networks (STORNs), a universal distribution approximator for sequential data leveraging the power of Recurrent Neural Networks (RNNs) and Variational Auto-Encoders (VAEs). The detection algorithm is evaluated on real robot time series data in order to prove that the method robustly detects anomalies off- and on-line. / Detta arbete förslår en ny detektionsalgoritm för anomalier i högdi-mensionell multimodal reellvärd tidsseriedata. Metoden kräver in-gen domänkunskap och baseras på Stochastic Recurrent Networks (STORNs), en teknik för oövervakad och universell fördelningssapprox-imation för sekventiell data som bygger på Recurrent Neural Net-works (RNNs) och Variational Auto-Encoders (VAEs). Algoritmen utvärderades på robotgenererade tidsserier och slutsat-sen är att metoden på ett robust sätt upptäcker anomalier både offline och online. / Anomaliedetektion in Roboterzeitreihen  mittels stochastischer Rekurrenter Netzwerke   In dieser Arbeit wird ein neuartiger Algorithmus entwickelt, um in hochdimensionalen, multimodalen, reellwertigen Zeitreihen Anomalien zu detektieren. Der Ansatz benötigt keine domänenspezifisches Fachwissen und basiert auf Stochastischen Rekurrenten Netzwerken (STORN), einem universellen Wahrscheinlichkeitsverteilungsapproximator für sequenzielle Daten, der die Stärken von Rekurrenten Neuronalen Netzwerken (RNN) und dem Variational Auto-Encoder (VAE) vereinigt. Der Detektionsalgorithmus wird auf realen Robotertrajektorien evaluiert. Es wird gezeigt, dass Anomalien robust online und offline gefunden werden können.

The purpose of this thesis is to develop an algorithm which solves the Vehicle Relocation Problem in the One-Way Car-Sharing (VRLPOWCS) as fast as possible. The problem describes the task of relocating the cars to areas with the largest demand. The chauffeurs who relocate the cars are transported by shuttle buses. Each car is assigned an individual relocation utility. The objective is to find shuttle tours that maximise in a given time the relocation utility while balancing the distribution of the cars. The VRLPOWCS is formulated as a mixed integer linear program. Since this problem is NP-complete we choose the branch-and-cut method to solve it. Using additional cutting planes – which exploit the structure of the VRLPOWCS – we enhance this method. Tests on real data show that this extended algorithm can solve the VRLPOWCS faster. / Syftet med detta examensarbete är att utveckla en algoritm som löser fördelningsproblemet av car-sharing bilar (VRLPOWCS) så snabbt som möjligt. Problemet beskriver uppgiften att flytta bilarna till områden där efterfrågan är störst. Bilarna flyttas av chaufförer som är transporterade med bussar. Varje bil ges ett flyttningsvärde. Målet är att hitta resor för bussarna så att inom ett visst tidsintervall det totala flyttningsvärdet är maximerat med hänsyn till en given fördelning. VRLPOWCS formuleras som ett linjärt heltalsprogrammeringsproblem. Eftersom problemet är NP-fullständigt, använder vi branch-and-cut metoden för att lösa det. Metoden utvidgar vi med cutting planes vilka utnyttjar VRLPOWCS strukturen. Tester med olika riktiga data visar att den utvidga algoritmen kan lösa VRLPOWCS snabbare. / Das Ziel dieser Arbeit ist die Entwicklung eines Algorithmus, der das Umparkproblem im Free-Floating Carsharing (VRLPOWCS) schnellstmöglich löst. Beim Umparkproblem werden Carsharing Fahrzeuge in Gebiete mit der höchsten Nachfrage umverteilt. Dabei werden die Autos von Fahrern umgeparkt, welche von Kleinbussen transportiert werden. Jedem Auto wird ein individueller Nutzenwert zugewiesen. Das Ziel des Umparkproblems ist das Finden von Bustouren, die in gegebener Zeit den Umparknutzen unter Beachtung einer gewissen Verteilung der Fahrzeuge in den Zielräumen maximieren. Das VRLPOWCS wird als ganzahlig-lineares Optimierungsproblem formuliert. Zur Lösung des VRLPOWCS wird ein Schnittebenenverfahren verwendet, da das Problem NP-vollständig ist. Das Verfahren wird mit Schnitten verbessert, die die Struktur des VRLPOWCS ausnutzen. Testläufe mit echten Daten zeigen, dass der erweiterte Algorithmus das VRLPOWCS schneller lösen kann.

Dual Energy X-ray Absorptiometry is a proven technique used to identify unknown materials, by measuring the transmission of two X-ray energies. This technique is limited to measuring a single chemical quantity and is not able to handle more chemical variation. To overcome this, one approach is to use multiple-energies to resolve more information. The differences in the processes controlling the Xray transmission limits the theoretical resolution capability to three characteristics. Of these three, one is dependent on the sample geometry and density. The remaining two are purely chemical characteristics and are investigated in this thesis. It is found that using X-ray photon energies in the range 20-90 keV, it is possible to measure one chemical characteristic to a high precision. Two chemical characteristics can be measured in limited circumstances and even though the precision is good, the measurement is prone to inaccuracies in machine modeling and stability. A two step method is defined, first finding an approximation of the X-ray spectra and then reconstructing the attenuation coefficient of the sample to a high precision (< 0.2%) using a robust low-rank basis for the characteristics. / DXA (Dual Energy X-ray Absorptiometry) är en teknik för att identifiera okända material genom att mäta transmissionen för två olika röntgenenergier. Den här metoden är begränsad till att mäta en kemiskt variation. Vid mer än en varierande komponent, kan MXA (Multiple Energy X-ray Absorptiometry) användas för att utröna mer information. MXA är dock begränsat av de små skillnaderna i de fysikaliska processerna som styr röntgenfotonernas interaktion med materialet. Teoretiskt är det bara möjligt att mäta tre egenskaper med MXA, varav en är beroende på provets geometri och densitet. De kvarvarande kemiska egenskaper är utforskade i den här rapporten. Det är möjligt att mäta en kemisk material egenskap med hög precision med röntgen energier mellan 20 - 90 keV. Två kemiska egenskaper går att mäta i vissa fall, dock är precisionen sämre och mätningen är känslig för fel i modelleringen av maskinen och mätningens stabilitet. I den tvåstegs metod som används uppskattas först de använda röntgenspectra och sedan återskapas provets attenueringskoefficient med en hög precision (< 0.2 %) med en lågranks bas av attenueringsegenskaperna.

This master’s thesis concerns the implementation of a GPUaccelerated version of Mehrotra’s predictor-corrector interior point algorithm for large-scale linear programming (LP). The implementations are tested on LP problems arising in the financial industry, where there is high demand for faster LP solvers. The algorithm was implemented in C++, MATLAB and CUDA, using double precision for numerical stability. A performance comparison showed that the algorithm can be accelerated from 2x to 6x using an Nvidia GTX Titan Black GPU compared to using only an Intel Xeon E5-2630v2 CPU. The amount of memory on the GPU restricts the size of problems that can be solved, but all tested problems that are small enough to fit on the GPU could be accelerated. / Detta masterexamensarbete behandlar implementeringen av en grafikkortsaccelererad inrepunktsmetod av predictor-corrector-typ för storskalig linjärprogrammering (LP). Implementeringarna testas på LP-problem som uppkommer i finansbranschen, där det finns ett stort behov av allt snabbare LP-lösare. Algoritmen implementeras i C++, MATLAB och CUDA, och dubbelprecision används för numerisk stabilitet. En prestandajämförelse visade att algoritmen kan accelereras 2x till 6x genom att använda ett Nvidia GTX Titan Black jämfört med att bara använda en Intel Xeon E5-2630v2. Mängden minne på grafikkortet begränsar problemstorleken, men alla testade problem som får plats i grafikkortsminnet kunde accelereras.

When pricing american option with discrete cash dividends standard tree techniques are insufficient. J. W. Nieuwenhuis and M. H. Vellekoop have presented a new tree technique involving interpolation to solve the problem. At ORC it has been observed that when using an adaptive mesh to increase the resolution of the tree around the dividends the speed of convergence is improved n this paper we isolate the sources of errors in the tree model and explain why the adaptive mesh has a good effect. Using that knowledge we further improve the algorithm. We found that we could both improve the accuracy and reduce execution time for the algorithm. / När man prissätter amerikanska optioner där underliggande har diskreta utdelningar så kan vanliga trädmodeller vara otillräckliga. J. W. Nieuwenhuis och M. H. Vellekoop har hittat en ny trädmetod där interpolation används för att lösa de problem som uppstår. På ORC har man upptäckt att genom att använda ett adaptivt träd för att öka punkttätheten i trädet kring utdelningarna så kan man få snabbare konvergens av optionspriset.  I detta arbete undersöker vi det adaptiva trädets effekter på prissättningsalgoritmen och isolerar olika felkällor. Vi använder den kunskapen till att effektivisera algoritmen för optimal noggrannhet och prestanda.

In this thesis we implement and study the effects of different convective outflow boundary conditions for the high order spectral element solver Nek5000 in the context of solving convective-dominated fluid flow problems. By numerical testing we show that the convective boundary conditions preserve the spatial and temporal convergence rates of the solver. We also study highly convective test cases such as a single vortex propagating through the outflow boundary, and the typical Kármán vortex shedding problem to analyze the accuracy and stability. A detailed comparison with the natural boundary condition that corresponds to the variational form of the incompressible Navier–Stokes equations (the Nek5000 “O” condition), and a stabilized version of it (by Dong et al. (2014)), are also presented.   Our results show a major advantage of using the convective boundary conditions over the natural counterpart in solving convective problems, both according to stability and accuracy. Analytic and numerical results show that the natural condition has big stability problems for high Reynolds numbers, which make the use of stabilization methods or damping regions crucial. But, the (Dong) stabilized natural condition does not improve accuracy, and damping regions are computationally expensive. The convective conditions show very good accuracy if its convection speed is approximated accurately, and our results indicate that it can be used without damping regions efficiently. Our results also show that the magnitude of reflections significantly depends on the amplitude of the disturbances that move through the boundary. The convective boundary condition can handle large disturbances without producing significant reflections, while the natural one or a stabilized version of it in general can not. / I det här examensarbetet har vi implementerat och studerat effekterna av olika konvektiva randvillkor för spektralelement lösaren Nek5000 vid beräkningar av konvektivt dominanta flödesproblem. Med hjälp av numeriska tester bevisar vi att de nya implementationerna bevarar lösarens konvergens i både rum och tid. Vi studerar noggrannheten hos de konvektiva randvillkoren genom konvektivt dominanta testfall i form av en ensam virvel som propagerar genom utflödet, samt det klassiska Kármán-virvel-gata problemet. En detaljerad jämförelse med det naturliga randvillkoret tillhörande den svaga formuleringen av de inkompressibla Navier-Stokes ekvationerna (Nek5000 “O”) och en stabiliserad version av denna är också presenterade.   Våra resultat visar tydliga fördelar med att använda de konvektiva randvillkoren mot det naturliga vid lösningar av konvektiva problem, både stabilitetsmässigt och noggrannhetsmässigt. Analytiska och numeriska resultat visar att det naturliga randvillkoret har stora stabilitetsproblem vid höga Reynolds-tal, vilket medför att specifika stabilitetsversioner eller dämpningsregioner måste användas. Men stabiliserande naturliga randvillkor (Dong) förbättrar inte noggrannheten och dämpningsregioner är dyra beräkningsmässigt. De konvektiva randvillkoren har uppvisat en väldigt god noggrannhet om konvektionshastigheten i villkoren är noggranna approximationer. Analyser av amplituden hos reflektioner har också undersökts. Våra resultat visar ett signifikant linjärt förhållande mellan storleken på störningar som genomborrar utflödes-randen och de reflektioner dessa störningar skapar. De konvektiva randvillkoren visar sig klara starka störningar bra, vilket det naturliga och den stabiliserade versionen av det naturliga randvillkoret generellt sett inte gör.

The major objective of this Master's thesis is to accelerate a serial implementation of a numerical algorithm for the simulation of slender fiber dynamics by using Graphical Processing Units (GPU). We focus on rigid fibers sedimenting due to gravity in a free-space Stokes flow. The ability to simulate a large number of fibers in a reasonable computational time on a high-performance parallel platform opens exciting new research opportunities. The previous serial implementation is rewritten for parallel execution. The algorithm is implemented in single precision using the Compute Unified Device Architecture (CUDA) on NVIDIA GPUs. In addition, we develop an OpenMP version of the parallel implementation to run on multi-core CPUs. Using both implementations, we perform a number of benchmarks to determine the fastest variant of the algorithm. We observe a speedup of 20x to 40x on the NVIDIA GTX 970 compared to an Intel Core i7 4770. The GPU implementation can simulate up to 2000 fibers on a desktop computer and it takes only in the order of 8 seconds to advance one time step. Furthermore, we have performed a number of simulations of known experiments for sedimenting fibers to validate the algorithm and to explore the numerical precision of the results. The results show an excellent agreement with results from prior experiments in the field. / Huvudsyftet med detta arbete är att, med hjälp av grafikprocessorer (GPU:er), accelerera en seriell implementation av en numerisk algoritm för simulering av stela fibrer i en vätska. Fibrerna är modellerade på partikelnivå och ett stort antal fibrer krävs i beräkningarna för att kunna göra realistiska simuleringar. Trots förenklingar i modellen blir ekvationerna så komplexa att de måste lösas numeriskt och det krävs kraftfulla metoder för beräkningarna vilket innebär att snabba och effektiva algoritmer måste utvecklas. Utgående från den seriella implementationen har en algoritm för parallell exekvering på GPU:er utvecklats. Algoritmen är implementerad i enkel precision på NVIDIA-GPU:er (NVIDIA GTX 970) med hjälp av Compute Unified Device Architecture, (CUDA). För att kunna göra en rättvis prestandajämförelse mellan GPU-implementationen och en CPU-implementering har dessutom en OpenMP-version av algoritmen implementerats för en CPU (Intel Core i7 4770) med flera kärnor. Båda versionerna har optimerats med avseende på respektive arkitektur. Ett antal prestandatester visar att den nya GPU-versionen av algoritmen ger en uppsnabbning av exekveringstiden på 20 till 40 gånger jämfört med CPU-OpenMP-versionen. Detta gör att vi nu kan simulera upp till 2000 fibrer på en bordsdator med en exekveringstid på ca 8 sekunder per tidssteg. Vi har även utfört ett antal simuleringar av redan kända experiment med fibersuspensioner för att validera algoritmen samt för att utvärdera den numeriska precisionen i resultaten. Överensstämmelsen med tidigare rapporterade resultat är väldigt god.

In order to perform simulations of the human heart using a heart finite element solver developed at the Computational Technology Laboratory at KTH with a data set provided by Philips consisting of surface meshes of a whole heart, the surface mesh has to be converted to a volume mesh. The conversion is manual and time consuming. Therefore the purpose of this thesis is to develop algorithms and software tools for automatic generation of a finite element model in the form of a volume mesh of the left ventricle of a human heart based on the available Philips data set. The developed model can be used for the simulation of blood flow by solving the Navier–Stokes equations. The method used for generating the model is based on deformation of an a priori finite element volume mesh to fit the extracted inner wall surface mesh of the left ventricle, from the aforementioned data set. The deformation is done by solving a nonlinear partial differential equation (PDE) using the finite element method. The method starts with the characterization of an external field that describes the distance from the target surface mesh, and then uses this external field as a component of the total force responsible for deforming the object. The method is validated in three space dimension by deforming a sphere into an ellipsoid. For this test case, two implementations of the PDE were tested and evaluated. The method was then applied to the above mentioned Philips data set. The report summarizes the findings and proposes improvements for the future work / För att utföra simuleringar av ett mänskligt hjärta med hjälp av ett finita elements hjärtlösare på Computational Technology Laboratory på KTH, med data från Philips innehållande ytnät från ett helt hjärta, krävs att ytnätet omvandlas till ett volymnät. Omvandlingen görs för hand och tar mycket tid. Syftet med den här uppsatsen ¨ar därför att utveckla algoritmer och mjukvaruverktyg för automatisk generering av finita elementmodellen i form av ett volymnät av ett mänskligt hjärtas vänsterkammare baserat på tillgänglig data från Philips. Den utvecklade metoden kan användas för blodflödessimulering genom att lösa Navier-Stokesekvationerna. Metoden som har använts för att generera modellen baseras på deformering av ett förutbestämd finit elementnät för att passa ytnätet på vänsterkammarens uttagna innervägg från Philips data. Deformeringen görs genom att lösa en ickelinjär partialdifferentialekvation med hjälp av finita element metoden. Metoden börjar med karaktäriseringen av ett yttre fält som beskriver avståndet från det önskvärda ytnätet och sedan använder detta yttre fält som en del i den totala kraften som ansvarar för objektets deformering. Metoden har verifierats i tre rymddimensioner genom att en sfär deformeras till en ellips. I detta fall testades och utvärderades två implementeringar av partialdifferentialekvation. Sedan applicerades metoden på den tidigare nämnda datan från Philips. Rapporten sammanfattar upptäckterna och föreslår framtida förbättringar.

This report investigates methods of optimization to make treatment plans in radiosurgery robust to spatial uncertainty, and attempts to determine whether they could be used with bene t in a Gamma Knife context. To make the problem mathematically feasible, regions of interest (ROIs) are approximated to move in a pre-computed static dose cloud, which in turn is estimated by methods of linear interpolation and linear approximation. The movements of ROIs are modeled by transforms, of which rigid, general affine, and a special case of non-affine transforms are treated. Of these, the rigid transforms are used to flexibly assess various properties of the robust optimization model; the a ne transforms to model the total geometric error of the Gamma Knife, excluding ROI delineation; and the non-affine transforms for initial modeling of the important delineation uncertainty. For the geometric errors, traditionally seen as small for the Gamma Knife, the robust treatment plans are seen to compare favorably to those obtained by non-robust optimization. Delineation errors are found to need careful modeling in order to avoid excessively conservative plans, which may harm normal tissue.

There is large theoretical, experimental and numerical interest in studying boundary layers, which develop around any body moving through a fluid. The simplest of these boundary layers lead to the theoretical abstraction of a so-called Blasius boundary layer, which can be derived under the assumption of a flat plate and zero external pressure gradient. The Blasius solution is characterised by a slow growth of the boundary layer in the streamwise direction. For practical purposes, in particular related to studying transition scenarios, non-linear finite-amplitude states (exact coherent states, edge states), but also for turbulence, a major simplification of the problem could be attained by removing this slow streamwise growth, and instead consider a parallel boundary layer. Parallel boundary layers are found in reality, e.g. when applying suction (asymptotic suction boundary layer) or rotation (Ekman boundary layer), but not in the Blasius case. As this is only a model which is not an exact solution to the Navier-Stokes (or boundary-layer) equations, some modifications have to be introduced into the governing equations in order for such an approach to be feasible. Spalart and Yang introduced a modification term to the governing Navier-Stokes equations in 1987. In this thesis work, we adapted the amplitude of the modification term introduced by Spalart and Yang to identify the nonlinear states in the parallel Blasius boundary layer. A final application of this modification was in determining the so-called edge states for boundary layers, previously found in the asymptotic suction boundary layer / Det finns stor teoretisk, experimentell och numerisk intresse för att studera gränsskikt som utvecklas runt varje kropp som rör sig genom en vätska. Det enklaste av detta gränsskikt leder till den teoretiska abstraktion av ett s.k. Blasius gränsskikt, som kan härledas under antagande av en plan platta utan externt tryckgradient. Blasius lösningen karakteriseras av en långsam tillväxt av gränsskiktet i strömningsriktningen. Av praktiska skäl, särskilt i samband med att studera övergångsscenarier, icke-linjära finita-amplitud tillstånd (“exact coherent state” på engelska), men även för turbulens, en stor förenkling av problemet kan nås genom att ta bort denna långsamma strömvis tillväxt, och istället överväga en parallell gränsskikt. Parallella gränsskikt finns i verkligheten, t.ex. vid sugning (asymptotisk sugningsgränsskiktet) eller rotation (Ekman gränsskiktet), men inte i Blasius fallet. Eftersom detta är bara en modell som inte är en exakt lösning på Navier-Stokes (eller gränsskikts) ekvationer, vissa ändringar måste införas i de styrande ekvation för att en sådan strategi ska vara genomförbart. Spalart och Yang infört en enkel ändring i Navier-Stokes ekvationer redan 1987. I detta examensarbete har vi anpassat amplituden av modifieringstermen att identifiera de icke-linjära tillstånd i det parallella Blasius gränsskiktet. Motivation av tillämpning av denna ändring var att fastställa de så kallade “edge states” för gränsskikt, som tidigare har hittats i det asymptotiska sugningsgränsskiktet.