Kronecker structured representations are used to cope with the state space explosion problem in Markovian modeling and analysis. Currently an open research problem is that of devising strong preconditioners to be used with projection methods for the computation of the stationary vector of Markov chains (MCs) underlying such representations. This paper proposes a block SOR (BSOR) preconditioner for hierarchical Markovian Models (HMMs) that are composed of multiple low level models and a high level model that defines the interaction among low level models. The Kronecker structure of an HMM yields nested block partitionings in its underlying continuous-time MC which may be used in the BSOR preconditioner. The computation of the BSOR preconditioned residual in each iteration of a preconditioned projection method becoms the problem of solving multiple nonsingular linear systems whose coefficient matrices are the diagonal blocks of the chosen partitioning. The proposed BSOR preconditioner solvers these systems using sparse LU or real Schur factors of diagonal blocks. The fill-in of sparse LU factorized diagonal blocks is reduced using the column approximate minimum degree algorithm (COLAMD). A set of numerical experiments are presented to show the merits of the proposed BSOR preconditioner.

Background. Graphical projection methods define how virtual 3D environments are depicted on 2D monitors. No projection method provides a flawless reproduction, and the look of the resulting projections vary considerably. Field of view is a parameter of these projection methods, it determines the breadth of vision of the virtual camera used in the projection process. Field of view is represented by a degree, that defines the angle from the left to the right extent of the projection, as seen from the camera. Objectives. The aim of this study was to investigate the perceived quality of high degrees of field of view, using different graphical projection methods. The Perspective, the Panini, and the Stereographic projection methods were evaluated at 110, 140, and 170 degrees of field of view. Methods. To evaluate the perceived quality of the three projection methods at varying degrees of field of view; a user study was conducted in which 24 participants rated 81 tests each. This study was held in a conference room where the participants sat undisturbed, and could experience the tests under consistent conditions. The tests took three different usage scenarios into account, presenting scenes in which the camera was still, where it moved, and where the participants could control it. Each test was rated separately, one at a time, using every combination of projection method and degree of field of view. Results. The perceived quality of each projection method dropped at an exponential rate, relative to the increase in the degree of field of view. The Perspective projection method was always rated the most favorably at 110 degrees of field of view, but unlike the other projections, it would be rated much more poorly at higher degrees. The Panini and the Stereographic projections received favorable ratings at up to 140-170 degrees, but the perceived quality of these projection methods varied significantly, depending on the usage scenario and the virtual environment displayed. Conclusions. The study concludes that the Perspective projection method is optimal for use at up to 110 degrees of field of view. At higher degrees of field of view, no consistently optimal choice remains, as the perceived quality of the Panini and the Stereographic projection method vary significantly, depending on the usage scenario. As such, the perceived quality becomes a function of the graphical projection method, the degree of field of view, the usage scenario, and the virtual environment displayed.

No contexto do método MAC e baseado em esquemas de diferenças finitas, este trabalho apresenta três estudos: i) uma análise de estabilidade, ii) o desenvolvimento de técnicas implícitas e, iii) a construção de métodos de projeção para escoamentos com superfície livre. Na análise de estabilidade, o principal resultado mostra que o método de Crank-Nicolson torna-se condicionalmente estável quando aplicado para uma malha deslocada com a discretiza ção explícita das condições de contorno do tipo Dirichlet. Entretanto, o mesmo método com condições de contorno implícitas é incondicionalmente estável. Para obter métodos mais estáveis, formulações implícitas são desenvolvidas para a equação da pressão na superfície livre, derivada da condição de tensão normal. Esta estratégia resulta no acoplamento dos campos de velocidade e pressão, o que exige a introdução de novos métodos de projeção. Os métodos de projeção assim desenvolvidos resultam em novas metodologias para escoamentos com superfície livre que são apropriados para o tratamento de problemas com baixo número de Reynolds. Além disso, mostra-se que os métodos propostos podem ser aplicados para fluidos viscoelásticos. Novas estratégias são derivadas para obter métodos de projeção de segunda ordem de precisão para escoamentos com superfícies livres. Além dos resultados teóricos sobre a estabilidade de esquemas numéricos, técnicas implícitas e métodos de projeção, testes computacionais são realizados e comparados para consolidação da teoria apresentada. Os resultados numéricos são obtidos no sistema FREEFLOW. A eficiência e robustez das técnicas desenvolvidas neste trabalho são demonstradas na solução de problemas tridimensionais complexos com superfície livre e baixo número de Reynolds, incluindo os problemas do jato oscilante e do inchamento do extrudado / In the context of the MAC method and based on finite difference schemes, this work presents three studies: i) a stability analysis, ii) the development of implicit techniques, and iii) the construction of projection methods for free surface flows. In the stability analysis, the main result shows a precise stability restriction on the Crank-Nicolson method when one uses a staggered grid with Dirichlet explicit boundary conditions. However, the same method with implicit boundary conditions becomes unconditionally stable. In order to obtain more stable methods, implicit formulations are applied for the pressure equation at the free surface, which is derived from the normal stress condition. This approach results in a coupling of the velocity and pressure fields; hence new projection methods for free surface flows need to be developed. The developed projection methods result in new methodologies for low Reynolds number free surface flows. It is also shown that the proposed methods can be applied for viscoelastic fluids. New strategies are derived for obtaining second-order accurate projection methods for free surface flows. In addition to the theoretical results on the stability of numerical schemes, implicit techniques and projection methods, computational tests are carried out and the results compared to consolidate the theory. The numerical results are obtained by the FREEFLOW system. The eficiency and robustness of the techniques in this work are demonstrated by solving complex tridimensional problems involving free surface and low Reynolds numbers, including the jet buckling and the extrudate swell problems

For many scientific applications, inverse problems have played a key role in solving important problems by enabling researchers to estimate desired parameters of a system from observed measurements. For example, large-scale inverse problems arise in many global problems and medical imaging problems such as greenhouse gas tracking and computational tomography reconstruction. This dissertation describes advancements in computational tools for solving large-scale inverse problems and for uncertainty quantification. Oftentimes, inverse problems are ill-posed and large-scale. Iterative projection methods have dramatically reduced the computational costs of solving large-scale inverse problems, and regularization methods have been critical in obtaining stable estimations by applying prior information of unknowns via Bayesian inference. However, by combining iterative projection methods and variational regularization methods, hybrid projection approaches, in particular generalized hybrid methods, create a powerful framework that can maximize the benefits of each method. In this dissertation, we describe various advancements and extensions of hybrid projection methods that we developed to address three recent open problems. First, we develop hybrid projection methods that incorporate mixed Gaussian priors, where we seek more sophisticated estimations where the unknowns can be treated as random variables from a mixture of distributions. Second, we describe hybrid projection methods for mean estimation in a hierarchical Bayesian approach. By including more than one prior covariance matrix (e.g., mixed Gaussian priors) or estimating unknowns and hyper-parameters simultaneously (e.g., hierarchical Gaussian priors), we show that better estimations can be obtained. Third, we develop computational tools for a respirometry system that incorporate various regularization methods for both linear and nonlinear respirometry inversions. For the nonlinear systems, blind deconvolution methods are developed and prior knowledge of nonlinear parameters are used to reduce the dimension of the nonlinear systems. Simulated and real-data experiments of the respirometry problems are provided. This dissertation provides advanced tools for computational inversion and uncertainty quantification. / Doctor of Philosophy / For many scientific applications, inverse problems have played a key role in solving important problems by enabling researchers to estimate desired parameters of a system from observed measurements. For example, large-scale inverse problems arise in many global problems such as greenhouse gas tracking where the problem of estimating the amount of added or removed greenhouse gas at the atmosphere gets more difficult. The number of observations has been increased with improvements in measurement technologies (e.g., satellite). Therefore, the inverse problems become large-scale and they are computationally hard to solve. Another example of an inverse problem arises in tomography, where the goal is to examine materials deep underground (e.g., to look for gas or oil) or reconstruct an image of the interior of the human body from exterior measurements (e.g., to look for tumors). For tomography applications, there are typically fewer measurements than unknowns, which results in non-unique solutions. In this dissertation, we treat unknowns as random variables with prior probability distributions in order to compensate for a deficiency in measurements. We consider various additional assumptions on the prior distribution and develop efficient and robust numerical methods for solving inverse problems and for performing uncertainty quantification. We apply our developed methods to many numerical applications such as greenhouse gas tracking, seismic tomography, spherical tomography problems, and the estimation of CO2 of living organisms.

Sei (X(t), t>= -r) ein stationärer stochastischer Prozess, der die affine stochastische Differentialgleichung mit Gedächtnis dX(t)=L(X(t+s))dt+sigma dW(t), t>= 0, löst, wobei sigma>0, (W(t), t>=0) eine Standard-Brownsche Bewegung und L ein stetiges lineares Funktional auf dem Raum der stetigen Funktionen auf [-r,0], dargestellt durch ein endliches signiertes Maß a, bezeichnet. Wir nehmen an, dass eine Trajektorie (X(t), -r 0, konvergiert. Diese Rate ist schlechter als in vielen klassischen Fällen. Wir beweisen jedoch eine untere Schranke, die zeigt, dass keine Schätzung eine bessere Rate im Minimax-Sinn aufweisen kann. Für zeit-diskrete Beobachtungen von maximalem Abstand Delta konvergiert die Galerkin-Schätzung immer noch mit obiger Rate, sofern Delta is in etwa von der Ordnung T^(-1/2). Hingegen wird bewiesen, dass für festes Delta unabhängig von T die Rate sich signifikant verschlechtern muss, indem eine untere Schranke von T^(-s/(2s+6)) gezeigt wird. Außerdem wird eine adaptive Schätzung basierend auf Wavelet-Thresholding-Techniken für das assoziierte schlechtgestellte Problem konstruiert. Diese nichtlineare Schätzung erreicht die obige Minimax-Rate sogar für die allgemeinere Klasse der Besovräume B^s_(p,infinity) mit p>max(6/(2s+3),1). Die Restriktion p>=max(6/(2s+3),1) muss für jede Schätzung gelten und ist damit inhärent mit dem Schätzproblem verknüpft. Schließlich wird ein Hypothesentest mit nichtparametrischer Alternative vorgestellt, der zum Beispiel für das Testen auf Gedächtnis verwendet werden kann. Dieser Test ist anwendbar für eine L^2-Trennungsrate zwischen Hypothese und Alternative der Ordnung T^(-s/(2s+2.5)). Diese Rate ist wiederum beweisbar optimal für jede mögliche Teststatistik. Für die Beweise müssen die Parameterabhängigkeit der stationären Lösungen sowie die Abbildungseigenschaften der assoziierten Kovarianzoperatoren detailliert bestimmt werden. Weitere Resultate von allgemeinem Interessen beziehen sich auf die Mischungseigenschaft der stationären Lösung, eine Fallstudie zu exponentiellen Gewichtsfunktionen sowie der Approximation des stationären Prozesses durch autoregressive Prozesse in diskreter Zeit. / Let (X(t), t>= -r) be a stationary stochastic process solving the affine stochastic delay differential equation dX(t)=L(X(t+s))dt+sigma dW(t), t>= 0, with sigma>0, (W(t), t>=0) a standard one-dimensional Brownian motion and with a continuous linear functional L on the space of continuous functions on [-r,0], represented by a finite signed measure a. Assume that a trajectory (X(t), -r 0. This rate is worse than those obtained in many classical cases. However, we prove a lower bound, stating that no estimator can attain a better rate of convergence in a minimax sense. For discrete time observations of maximal distance Delta, the Galerkin estimator still attains the above asymptotic rate if Delta is roughly of order T^(-1/2). In contrast, we prove that for observation intervals Delta, with Delta independent of T, the rate must deteriorate significantly by providing the rate estimate T^(-s/(2s+6)) from below. Furthermore, we construct an adaptive estimator by applying wavelet thresholding techniques to the corresponding ill-posed inverse problem. This nonlinear estimator attains the above minimax rate even for more general classes of Besov spaces B^s_(p,infinity) with p>max(6/(2s+3),1). The restriction p >= 6/(2s+3) is shown to hold for any estimator, hence to be inherently associated with the estimation problem. Finally, a hypothesis test with a nonparametric alternative is constructed that could for instance serve to decide whether a trajectory has been generated by a stationary process with or without time delay. The test works for an L^2-separation rate between hypothesis and alternative of order T^(-s/(2s+2.5)). This rate is again shown to be optimal among all conceivable tests. For the proofs, the parameter dependence of the stationary solutions has to be studied in detail and the mapping properties of the associated covariance operators have to be determined exactly. Other results of general interest concern the mixing properties of the stationary solution, a case study for exponential weight functions and the approximation of the stationary process by discrete time autoregressive processes.

Kronecker structured representations are used to cope with the state space explosion problem in Markovian modeling and analysis. Currently an open research problem is that of devising strong preconditioners to be used with projection methods for the computation of the stationary vector of Markov chains (MCs) underlying such representations. This paper proposes a block SOR (BSOR) preconditioner for hierarchical Markovian Models (HMMs) that are composed of multiple low level models and a high level model that defines the interaction among low level models. The Kronecker structure of an HMM yields nested block partitionings in its underlying continuous-time MC which may be used in the BSOR preconditioner. The computation of the BSOR preconditioned residual in each iteration of a preconditioned projection method becoms the problem of solving multiple nonsingular linear systems whose coefficient matrices are the diagonal blocks of the chosen partitioning. The proposed BSOR preconditioner solvers these systems using sparse LU or real Schur factors of diagonal blocks. The fill-in of sparse LU factorized diagonal blocks is reduced using the column approximate minimum degree algorithm (COLAMD). A set of numerical experiments are presented to show the merits of the proposed BSOR preconditioner.

L'objectif de cette thèse consiste à étudier la méthode de pénalité-projection vectorielle notée VPP (Vector Penalty-Projection method), qui est une méthode à pas fractionnaire pour la résolution des équations de Navier-Stokes incompressible avec conditions aux limites ouvertes. Nous présentons une revue bibliographique des méthodes de projection traitant le couplage de vitesse et de pression. Nous nous intéressons dans un premier temps aux conditions de Dirichlet sur toute la frontière. Les tests numériques montrent une convergence d'ordre deux en temps pour la vitesse et la pression et prouvent que la méthode est rapide et peu coûteuse en terme de nombre d'itérations par pas de temps. En outre, nous établissons des estimations d'erreurs de la vitesse et de la pression et les essais numériques révèlent une parfaite concordance avec les résultats théoriques. En revanche, la contrainte d'incompressibilité n'est pas exactement nulle et converge avec un ordre de O(varepsilondelta t) où varepsilon est un paramètre de pénalité choisi assez petit et delta t le pas temps. Dans un second temps, la thèse traite les conditions aux limites ouvertes naturelles. Trois types de conditions de sortie sont étudiés et testés numériquement pour l'étape de projection. Nous effectuons des comparaisons quantitatives des résultats avec d'autres méthodes de projection. Les essais numériques sont en concordance avec les estimations théoriques également établies. Le dernier chapitre est consacré à l'étude numérique du schéma VPP en présence d'une condition aux limites ouvertes non-linéaire sur une frontière artificielle modélisant une charge singulière pour le problème de Navier-Stokes. / Motivated by solving the incompressible Navier-Stokes equations with open boundary conditions, this thesis studies the Vector Penalty-Projection method denoted VPP, which is a splitting method in time. We first present a literature review of the projection methods addressing the issue of the velocity-pressure coupling in the incompressible Navier-Stokes system. First, we focus on the case of Dirichlet conditions on the entire boundary. The numerical tests show a second-order convergence in time for both the velocity and the pressure. They also show that the VPP method is fast and cheap in terms of number of iterations at each time step. In addition, we established for the Stokes problem optimal error estimates for the velocity and pressure and the numerical experiments are in perfect agreement with the theoretical results. However, the incompressibility constraint is not exactly equal to zero and it scales as O(varepsilondelta t) where $varepsilon$ is a penalty parameter chosen small enough and delta t is the time step. Moreover, we deal with the natural outflow boundary condition. Three types of outflow boundary conditions are presented and numerically tested for the projection step. We perform quantitative comparisons of the results with those obtained by other methods in the literature. Besides, a theoretical study of the VPP method with outflow boundary conditions is stated and the numerical tests prove to be in good agreement with the theoretical results. In the last chapter, we focus on the numerical study of the VPP scheme with a nonlinear open artificial boundary condition modelling a singular load for the unsteady incompressible Navier-Stokes problem.