none

Stuttgart, Univ., Diss., 2000.

Moore’s law is the main driving factor behind the rapid evolution of computers that has been observed in the past 50 years. Though the law is soon ending due to heat- and sizing-related issues. One solution to continuing the evolution is utilizing alternative computer hardware, where parallel hardware is especially interesting. The Field Programmable Gate Array (FPGA) is one such piece of hardware. This study compares the runtime of two linear-algebra benchmarks executed on a traditional CPU-based platform and an FPGA-based platform respectively. The benchmarks are called cholesky and durbin respectively. The cholesky benchmark performs Cholesky decomposition and the durbin benchmark computes the solution to a Yule-Walker equation. The CPU implementations of the benchmarks were provided in the C programming language and the FPGA implementations of the benchmarks were written using OpenCL, which is a High-Level-Synthesis framework. The results highlighted a clear advantage for the CPU implementations, which had a shorter runtime than the FPGA implementations in both benchmarks for every test case. This was caused by both benchmarks containing data dependencies, which required them to be executed sequentially. Since the CPU operates at a clock frequency more than ten times higher than the FPGA’s clock frequency, it executed sequential instructions faster than the FPGA. / Moores lag är den främsta orsaken till den snabba datorutveckling som skett de senaste 50 åren. På grund av svårigheter med värme och dimensionering närmar sig dock lagen sin applicerbara gräns. En lösning för att bibehålla utvecklingen är att nyttja alternativ hårdvara och särskilt intressant är parallell hårdvara. En Field Programmable Gate Array (FPGA) är ett exempel på sådan hårdvara. Denna studie jämför körtiden mellan två prestandatest för linjär-algebra-algoritmer som utvärderades på en traditionell CPU-baserad plattform och en FPGA-baserad plattform. Prestandatesterna kallas cholesky respektive durbin. Testet cholesky utför Choleskydekomposition och testet durbin löser en Yule-Walker-ekvation. CPU-implementationerna av testen tillhandahölls i programmeringsspråket C och FPGA-implementationerna av testen skrevs i OpenCL, som är ett ramverk för högnivåsyntes. Resultaten visade en tydlig fördel för CPU-implementationerna, som har en kortare körtid än FPGA-implementationerna för alla testfall i båda prestandatest. Detta orsakades av databeroenden som existerar i båda algoritmerna, vilket påtvingade en sekventiell exekvering. Då CPU:n når en närmare tio gånger högre klockfrekvens än FPGA:n exekverar den sålunda sekventiella instruktioner snabbare än FPGA:n.

In dieser Arbeit werden Techniken beschrieben, die es erlauben (höhere) Ableitungen und Taylorapproximationen solcher Computerprogramme effizient zu berechnen. Auch inbesondere dann, wenn die Programme Algorithmen der numerischen linearen Algebra (NLA) enthalten. Im Gegensatz zur traditionellen algorithmischen Differentiation (AD), bei der die zugrunde liegenden Algorithmen um zusätzliche Befehlere erweitert werden, sind in dieser Arbeit die Zerlegungen durch definierende Gleichungen charakterisiert. Basierend auf den definierenden Gleichungen werden Strukturausnutzende Algorithmen hergeleitet. Genauer, neuartige Algorithmen für die Propagation von Taylorpolynomen durch die QR, Cholesky und reell-symmetrischen Eigenwertzerlegung werden präsentiert. Desweiteren werden Algorithmen für den Rückwärtsmodus der AD hergeleitet, welche im Wesentlichen nur die Faktoren der Zerlegungen benötigen. Im Vergleich zum traditionellen Ansatz, bei dem alle Zwischenergebnisse gespeichert werden, ist dies eine Reduktion von O(N^3) zu O(N^2) für Algorithmen mit O(N^3) Komplexität. N ist hier die Größe der Matrix. Zusätzlich kann bestehende, hoch-optimierte Software verwendet werden. Ein Laufzeitvergleich zeigt, dass dies im Vergleich zum traditionellen Ansatz zu einer Beschleunigung in der Größenordnung 100 führen kann. Da die NLA Funktionen als Black Box betrachtet werden, ist desweiteren auch der Berechnungsgraph um Größenordnungen kleiner. Dies bedeutet, dass Software, welche Operator Overloading benutzt, weniger Overhead hervorruft und auch weniger Speicher benötigt. / This thesis provides a framework for the evaluation of first and higher-order derivatives and Taylor series expansions through large computer programs that contain numerical linear algebra (NLA) functions. It is a generalization of traditional algorithmic differentiation (AD) techniques in that NLA functions are regarded as black boxes where the inputs and outputs are related by defining equations. Based on the defining equations, structure-exploiting algorithms are derived. More precisely, novel algorithms for the propagation of Taylor polynomials through the QR, Cholesky,- and real-symmetric eigenvalue decomposition are shown. Recurrences for the reverse mode of AD, which require essentially only the returned factors of the decomposition, are also derived. Compared to the traditional approach where all intermediates of an algorithm are stored, this is a reduction from O(N^3) to O(N^2) for algorithms with O( N^3) complexity. N denotes the matrix size. The derived algorithms make it possible to use existing high-performance implementations. A runtime comparison shows that the treatment of NLA functions as atomic can be more than one order of magnitude faster than an automatic differentiation of the underlying algorithm. Furthermore, the computational graph is orders of magnitudes smaller. This reduces the additional memory requirements, as well as the overhead, of operator overloading techniques to a fraction.

La presente investigación tiene como objetivo cuantificar en términos de duración e impacto del efecto de choques en la cotización internacional del precio del petróleo sobre la inflación del Perú para el periodo 2007 al 2019. Por ello, se realiza una diferenciación entre el efecto directo e indirecto, ya que el efecto sobre la economía no solo se visualiza en los precios de los combustibles, sino también en variables macroeconómicas consideradas como variables control (crecimiento de la economía de Estados Unidos, términos de intercambio, tasa de crecimiento de Perú, tasa de referencia y la tasa de desempleo), las cuales multiplican aún más el efecto sobre la inflación. El análisis del efecto directo se desarrolló mediante una regresión simple OLS, la cual evaluará cambios en la cotización internacional del petróleo sobre el precio de los combustibles y derivados y su efecto sobre la inflación. Mientras que para los efectos indirectos se ejecutó utilizando un SVAR bajo la metodología de identificación de SIMS (1980) y la imposición de restricciones estructurales según la teoría económica. El resultado esperado, es demostrar que cambios en el precio de la cotización internacional del petróleo afectará en mayor medida (magnitud, duración e impacto) a la inflación por el canal indirecto, que por el canal directo. / The objective of this research is to quantify in terms of duration and impact the effect of shocks in the international price of oil on inflation in Peru for the period 2007-2019. Therefore, a differentiation is made between the direct and indirect effect since the effect on the economy is not only seen in fuel prices, but also in macroeconomic variables considered as control variables (growth of the United States economy, terms of trade, Peru's growth rate, reference rate, and unemployment rate), which further multiply the effect on inflation. The direct effect analysis was developed through a simple OLS regression, which will evaluate changes in the international price of oil on the price of fuels and derivatives and their effect on inflation. While for indirect effects, it is executed using an SVAR under the identification methodology of SIMS (1980) and the imposition of structural restrictions according to economic theory. The expected result is to show that changes in the international price of oil will affect inflation to a greater extent (magnitude, duration, and impact) through the indirect channel than through the direct channel. / Tesis

The process of factorizing a symmetric matrix using the Cholesky (LLT ) or indefinite (LDLT ) factorization of A allows the efficient solution of systems Ax = b when A is symmetric. This thesis describes the development of new serial and parallel techniques for this problem and demonstrates them in the setting of interior point methods. In serial, the effects of various scalings are reported, and a fast and robust mixed precision sparse solver is developed. In parallel, DAG-driven dense and sparse factorizations are developed for the positive definite case. These achieve performance comparable with other world-leading implementations using a novel algorithm in the same family as those given by Buttari et al. for the dense problem. Performance of these techniques in the context of an interior point method is assessed.

Orientador: Eliana Xavier Linhares de Andrade / Banca: Roberto Andreani / Banca: Cleonice Fátima Bracciali / Resumo: O principal objetivo deste trabalho é apresentar, discutir as qualidades e desempenho e provar a convergência de um método iterativo para a solução numérica do problema de autovalores de uma matriz, que chamamos de Método Assemelhado ao de Francis (MAF). O método em questão distingue-se do QR de Francis pela maneira, mais simples e rápida, de se obter as matrizes ortogonais Qk, k = 1; 2. Apresentamos, também, uma comparação entre o MAF e os algoritmos QR de Francis e LR de Rutishauser. / Abstract: The main purpose of this work is to presente, to discuss the qualities and performance and to prove the convergence of an iterative method for the numerical solution of the eigenvalue problem, that we have called the Método Assemelhado ao de Francis (MAF)þþ. This method di ers from the QR method of Francis by providing a simpler and faster technique of getting the unitary matrices Qk; k = 1; 2; We present, also, a comparison analises between the MAF and the QR of Francis and LR of Rutishauser algorithms. / Mestre

This thesis explores the relationship between interest rates, house prices and main macroeconomic variables. In particular, I examine how monetary policy affects house prices in the Czech Republic. The hypotheses assume that an increase in the interest rate that tends to decrease house prices also reduces output and inflation simultaneously. Therefore, the latter would imply that the monetary authority faces a trade-off between macroeconomic and financial stability. The empirical analysis is based on a vector autoregression model and the monetary policy shock is retrieved by the Cholesky decomposition. As for the results, the findings of the thesis conclude that there is a costly trade-off between macroeconomic and financial stability within the Czech economy.

Diversos procesos naturales e industriales de interés medioambiental se modelan a través de la ecuación de convección-difusión-reacción transitoria. Dos aplicaciones tecnológicas que han motivado esta tesis son el funcionamiento de filtros de carbón activo y la dispersión de contaminantes en la atmósfera. Para que la modelización numérica de estos problemas sea eficaz es indispensable contar con un solver lineal eficiente para resolver los sistemas de ecuaciones obtenidos al discretizar la ecuación en derivadas parciales, mediante elementos finitos.Por ello, el objetivo de esta tesis es resolver de forma eficiente los grandes sistemas de ecuaciones, simétricos definidos positivos (SDP), tipo sparse asociados a los problemas de convección-difusión transitorios. Con este fin se estudian los precondicionadores tanto explícitos como implícitos, así como los métodos de descomposición de dominios (DD). La tesis se estructura en tres partes. En la primera se elabora un análisis computacional detallado del comportamiento de dos familias de factorizaciones incompletas de Cholesky (FIC): de memoria prescrita y de umbral. Estas técnicas se utilizan para precondicionar el método iterativo de gradientes conjugados (PCG). En la segunda parte se construye una inversa aproximada sparse simétrica (SSPAI) basada en la minimización en la norma de Frobenius. El precondicionador explícito se diseña para resolver en paralelo grandes sistemas de ecuaciones sparse, SDP, tridiagonales por bloques con múltiples lados derechos. Finalmente, se desarrolla el método multiplicativo de Schwarz (MSM) en dominios activos, es decir, DD solapados con la innovación de activar y desactivar dominios. Se estudia el comportamiento de esta estrategia al resolver los subproblemas mediante: (1) el método directo de Cholesky y (2) PCG + FIC de umbral.De los resultados numéricos presentados se concluye que es preferible utilizar el método directo de Cholesky para sistemas con menos de 30,000 variables. Para sistemas mayores y hasta 80,000 incógnitas se sugiere emplear una FIC de umbral. Y para sistemas aún más grandes, el MSM en dominios activos + PCG + FIC de umbral propuesto es el más eficiente usando un solo procesador. Por su parte, la SSPAI presentada podría superar a las FIC de umbral si se trabaja en paralelo. / Many natural and industrial processes of environmental interest are modeled through the transient convection-diffusion-reaction equation. Two technological applications that have motivated this thesis are the operation of activated-carbon filters and the dispersion of pollutants in the atmosphere. In order to ensure the effectiveness of numerical modeling of these problems it is necessary to have an efficient linear solver to solve the systems obtained when discretizing the partial differential equation by means of the finite element method.For that reason, the goal of this thesis is to solve in an efficient way the large sparse symmetric positive definite (SPD) systems of linear equations associated to the transient convection-diffusion problems. With this purpose, we have studied the explicit and implicit preconditioners, as well as domain decomposition (DD) methods.The thesis is structured in three parts. In the first one we have elaborated a detailed analysis of the numerical performance of two families of incomplete Cholesky factorizations (ICF): drop tolerance and prescribed-memory strategies. These techniques are used to precondition conjugate gradient iterations (PCG). In the second part a symmetric sparse approximate inverse (SSPAI) based on the minimization of the Frobenius norm is built. The explicit preconditioner is designed to solve in parallel large block tridiagonal SPD systems with multiple right hand sides.Finally, the multiplicative Schwarz method (MSM) in active domains is developed, which consists of overlapped domain decomposition with the innovation to activate and to deactivate domains. The behavior of this strategy is studied when solving the subproblems by means of: (1) the Cholesky direct solver and (2) PCG + drop-tolerance ICF. According to our numerical experiments we conclude that it is preferable to use the Cholesky direct solver for systems with less than 30,000 variables. For larger systems and up to 80,000 equations we suggest to use a drop tolerance ICF. And for even lager systems, the proposed MSM in active domains is the most efficient when using a single processor. On the other hand, the presented SSPAI could overcome the drop-tolerance ICF if one works in parallel.

Three different algorithms for the generation of stationary Gaussian time series with given autocorrelation function are presented in this paper. The algorithms have already been suggested in the literature but are not well known and have never been compared before. Interrelations between the different methods, advantages and disadvantages with respect to speed and memory requirements and the range of autocorrelation functions for which the different methods are stable are discussed. The time-complexity of the algorithms and the comparisons of their implementations show that the method twice using the Fourier transform is by far the most efficient if time series of moderate or large length are generated. A tested C-code of the latter algorithm is included as this method is tricky to implement and very difficult to find in the literature. (We know only one reference, that gives a correct algorithm, but there the description is very short and no proof is included.) (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing