El tema principal de esta tesis es el desarrollo de técnicas de actualización de precondicionadores para resolver sistemas lineales de gran tamaño y dispersos Ax=b mediante el uso de métodos iterativos de Krylov. Se consideran dos tipos interesantes de problemas. En el primero se estudia la solución iterativa de sistemas lineales no singulares y antisimétricos, donde la matriz de coeficientes A tiene parte antisimétrica de rango bajo o puede aproximarse bien con una matriz antisimétrica de rango bajo. Sistemas como este surgen de la discretización de PDEs con ciertas condiciones de frontera de Neumann, la discretización de ecuaciones integrales y métodos de puntos interiores, por ejemplo, el problema de Bratu y la ecuación integral de Love. El segundo tipo de sistemas lineales considerados son problemas de mínimos cuadrados (LS) que se resuelven considerando la solución del sistema equivalente de ecuaciones normales. Concretamente, consideramos la solución de problemas LS modificados y de rango incompleto. Por problema LS modificado se entiende que el conjunto de ecuaciones lineales se actualiza con alguna información nueva, se agrega una nueva variable o, por el contrario, se elimina alguna información o variable del conjunto. En los problemas LS de rango deficiente, la matriz de coeficientes no tiene rango completo, lo que dificulta el cálculo de una factorización incompleta de las ecuaciones normales. Los problemas LS surgen en muchas aplicaciones a gran escala de la ciencia y la ingeniería como, por ejemplo, redes neuronales, programación lineal, sismología de exploración o procesamiento de imágenes. Los precondicionadores directos para métodos iterativos usados habitualmente son las factorizaciones incompletas LU, o de Cholesky cuando la matriz es simétrica definida positiva. La principal contribución de esta tesis es el desarrollo de técnicas de actualización de precondicionadores. Básicamente, el método consiste en el cálculo de una descomposición incompleta para un sistema lineal aumentado equivalente, que se utiliza como precondicionador para el problema original. El estudio teórico y los resultados numéricos presentados en esta tesis muestran el rendimiento de la técnica de precondicionamiento propuesta y su competitividad en comparación con otros métodos disponibles en la literatura para calcular precondicionadores para los problemas estudiados. / The main topic of this thesis is updating preconditioners for solving large sparse linear systems Ax=b by using Krylov iterative methods. Two interesting types of problems are considered. In the first one is studied the iterative solution of non-singular, non-symmetric linear systems where the coefficient matrix A has a skew-symmetric part of low-rank or can be well approximated with a skew-symmetric low-rank matrix. Systems like this arise from the discretization of PDEs with certain Neumann boundary conditions, the discretization of integral equations as well as path following methods, for example, the Bratu problem and the Love's integral equation. The second type of linear systems considered are least squares (LS) problems that are solved by considering the solution of the equivalent normal equations system. More precisely, we consider the solution of modified and rank deficient LS problems. By modified LS problem, it is understood that the set of linear relations is updated with some new information, a new variable is added or, contrarily, some information or variable is removed from the set. Rank deficient LS problems are characterized by a coefficient matrix that has not full rank, which makes difficult the computation of an incomplete factorization of the normal equations. LS problems arise in many large-scale applications of the science and engineering as for instance neural networks, linear programming, exploration seismology or image processing. Usually, incomplete LU or incomplete Cholesky factorization are used as preconditioners for iterative methods. The main contribution of this thesis is the development of a technique for updating preconditioners by bordering. It consists in the computation of an approximate decomposition for an equivalent augmented linear system, that is used as preconditioner for the original problem. The theoretical study and the results of the numerical experiments presented in this thesis show the performance of the preconditioner technique proposed and its competitiveness compared with other methods available in the literature for computing preconditioners for the problems studied. / El tema principal d'esta tesi és actualitzar precondicionadors per a resoldre sistemes lineals grans i buits Ax=b per mitjà de l'ús de mètodes iteratius de Krylov. Es consideren dos tipus interessants de problemes. En el primer s'estudia la solució iterativa de sistemes lineals no singulars i antisimètrics, on la matriu de coeficients A té una part antisimètrica de baix rang, o bé pot aproximar-se amb una matriu antisimètrica de baix rang. Sistemes com este sorgixen de la discretització de PDEs amb certes condicions de frontera de Neumann, la discretització d'equacions integrals i mètodes de punts interiors, per exemple, el problema de Bratu i l'equació integral de Love. El segon tipus de sistemes lineals considerats, són problemes de mínims quadrats (LS) que es resolen considerant la solució del sistema equivalent d'equacions normals. Concretament, considerem la solució de problemes de LS modificats i de rang incomplet. Per problema LS modificat, s'entén que el conjunt d'equacions lineals s'actualitza amb alguna informació nova, s'agrega una nova variable o, al contrari, s'elimina alguna informació o variable del conjunt. En els problemes LS de rang deficient, la matriu de coeficients no té rang complet, la qual cosa dificultata el calcul d'una factorització incompleta de les equacions normals. Els problemes LS sorgixen en moltes aplicacions a gran escala de la ciència i l'enginyeria com, per exemple, xarxes neuronals, programació lineal, sismologia d'exploració o processament d'imatges. Els precondicionadors directes per a mètodes iteratius utilitzats més a sovint són les factoritzacions incompletes tipus ILU, o la factorització incompleta de Cholesky quan la matriu és simètrica definida positiva. La principal contribució d'esta tesi és el desenvolupament de tècniques d'actualització de precondicionadors. Bàsicament, el mètode consistix en el càlcul d'una descomposició incompleta per a un sistema lineal augmentat equivalent, que s'utilitza com a precondicionador pel problema original. L'estudi teòric i els resultats numèrics presentats en esta tesi mostren el rendiment de la tècnica de precondicionament proposta i la seua competitivitat en comparació amb altres mètodes disponibles en la literatura per a calcular precondicionadors per als problemes considerats. / Guerrero Flores, DJ. (2018). On Updating Preconditioners for the Iterative Solution of Linear Systems [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/104923 / TESIS

The first half of the thesis focuses on the computation of high-dimensional multivariate normal (MVN) and multivariate Student-t (MVT) probabilities. Chapter 2 generalizes the bivariate conditioning method to a d-dimensional conditioning method and combines it with a hierarchical representation of the n × n covariance matrix. The resulting two-level hierarchical-block conditioning method requires Monte Carlo simulations to be performed only in d dimensions, with d ≪ n, and allows the dominant complexity term of the algorithm to be O(n log n). Chapter 3 improves the block reordering scheme from Chapter 2 and integrates it into the Quasi-Monte Carlo simulation under the tile-low-rank representation of the covariance matrix. Simulations up to dimension 65,536 suggest that this method can improve the run time by one order of magnitude compared with the hierarchical Monte Carlo method. The second half of the thesis discusses a novel matrix compression scheme with Kronecker products, an R package that implements the methods described in Chapter 3, and an application study with the probit Gaussian random field. Chapter 4 studies the potential of using the sum of Kronecker products (SKP) as a compressed covariance matrix representation. Experiments show that this new SKP representation can save the memory footprint by one order of magnitude compared with the hierarchical representation for covariance matrices from large grids and the Cholesky factorization in one million dimensions can be achieved within 600 seconds. In Chapter 5, an R package is introduced that implements the methods in Chapter 3 and show how the package improves the accuracy of the computed excursion sets. Chapter 6 derives the posterior properties of the probit Gaussian random field, based on which model selection and posterior prediction are performed. With the tlrmvnmvt package, the computation becomes feasible in tens of thousands of dimensions, where the prediction errors are significantly reduced.

Accounting for seismic forces and thermal expansion in bridge design requires an accurate passive force-deflection relationship for the abutment wall. Current design codes make no allowance for skew effects on passive force; however, large scale field tests indicate that there is a substantial reduction in peak passive force as skew angle increases. A reduction in passive force also reduces the transverse shear resistance on the abutment. The purpose of this study is to validate three-dimensional model using PLAXIS 3D, against large scale test results performed at Brigham Young University and to develop a set of calibrated finite element models. The model set could be used to evaluate the variation in passive resistance with skew angle for various abutment geometries and backfill types. Initially, the finite element model was calibrated using the results from a suite of field tests where the backfill material consisted of dense compacted sand. Results were available for skew angles of 0, 15, 30 and 45°. Numerical model results were compared with measured passive force-deflection curves, ground surface heave and displacement contours, longitudinal displacements, and failure plane geometry. Soil properties were defined by laboratory testing and in-situ direct shear tests on the compacted fill. Soil properties and mesh geometries were primarily calibrated based on the zero skew test results. The results were particularly sensitive to the soil friction angle, wall friction angle, angle of dilatancy, soil stiffness and lateral restraint of the abutment backwall movement. Reasonable agreement between measured and computed response was obtained in all cases confirming numerically that passive force decreases as skew angle increases Additional analyses were then performed for abutments with different soil boundaries.

This master's thesis deals with acceleration of geometrical image transforms using the GPU and NVIDIA (R) CUDA TM architecture. Time critical parts of the code are moved on the GPU and executed in parallel. One of the results is a demonstrational application for performance comparison of both architectures: the CPU, and GPU in combination with the CPU. As a reference implementation, there are used highly optimized routines from the OpenCV library, made by the Intel company.

A new method is presented for the numerical computation of the generalized eigen- values of real Hamiltonian or symplectic pencils and matrices. The method is strongly backward stable, i.e., it is numerically backward stable and preserves the structure (i.e., Hamiltonian or symplectic). In the case of a Hamiltonian matrix the method is closely related to the square reduced method of Van Loan, but in contrast to that method which may suffer from a loss of accuracy of order sqrt(epsilon), where epsilon is the machine precision, the new method computes the eigenvalues to full possible accuracy.

In this work, we study return and hitting times in measure-preserving dy- namical systems. We consider a special type of skew-products of two Bernoulli schemes, called a random walk in random scenery. For these systems, the limit distribution of normalized hitting times for cylinders of increasing length is proved to be exponential under the assumption of finite variance of the first order dis- tribution of the Bernoulli scheme representing the walk, and provided the drift is non-zero or the scenery alphabet is finite. Mixing properties of the skew-products are discussed in order to relate our work with some known results on rescaled hitting times for strongly-mixing systems. 1

Incidence coalgebras of categories as defined by Joni and Rota are studied, specifically in cases where a strict monoidal product on the underlying category turns the incidence coalgebra into a bialgebra or weak bialgebra. Examples of these incidence bialgebras in combinatorics are given, and include rooted trees and forests, skew shapes and bigraphs. The relations between incidence bialgebras of monoidal categories, incidence bialgebras of operads and posets, combinatorial Hopf algebras and the quiver Hopf algebras of Cibils and Rosso are discussed. Building on a result of Bergbauer and Kreimer, incidence bialgebras are seen as a useful setting in which to study aspects of combinatorial Dyson-Schwinger equations. The possibility of defining a grafting operator B+ and combinatorial DysonSchwinger equations for general incidence bialgebras is explored through the example of skew shapes.:1. Introduction 2. Background 3. Incidence bialgebras of monoidal categories and multicategories 4. Combinatorial Dyson-Schwinger equations

The effects of seismic forces and thermal expansion on bridge performance necessitate an accurate understanding of the relationship between passive force and backwall deflection. In past case studies, skewed bridges exhibited significantly more damage than non-skewed bridges. These findings prompted studies involving numerical modeling, lab-scale tests, and large-scale tests that each showed a dramatic reduction in passive force with increased skew. Using these results, a correlation was developed between peak passive force and backwall skew angle. The majority of these tests had length to height ratios of 2.0; however, for several abutments in the field, the length to height ratio might be considerably higher than 2.0. This change in geometry could potentially affect the validity of the previously found passive force reduction correlation. To explore this issue, laterally loaded, large-scale pile cap tests were performed with densely compacted sand at a length of 11 ft (3.35 m) and a height of 3 ft (0.91 m), resulting in a length to height ratio of 3.7. The backwall interface was adjusted to fit three various skew angles including: 0°, 15° and 30°. The behavior of both the pile cap and adjacent soil backfill were monitored under these conditions. The peak passive force for the 15° and 30° tests were found to be 71% and 45%, respectively, of the peak passive force for the 0° skew test. These findings are relatively consistent with previously performed tests. Passive forces peaked at deflections between 2% and 5% of the backwall height, decreasing with skew angle. All skews exhibited a log spiral failure plane that transitioned into a linear plane. These results also agreed with previously reported values for large-scale passive force-deflection tests. Rotation of the pile cap was detected in the direction opposite to the skew. Higher pressures were found to be on both corners of the pile cap than in the middle portion, as is suggested by the elastic theory.

Skewed bridges have exhibited poorer performance during lateral earthquake loading in comparison to non-skewed bridges (Apirakvorapinit et al. 2012; Elnashai et al. 2010). Results from numerical modeling by Shamsabadi et al. (2006), small-scale laboratory tests by Rollins and Jessee (2012), and several large-scale tests performed by Rollins et al. at Brigham Young University (Franke 2013; Marsh 2013; Palmer 2013; Smith 2014; Frederickson 2015) led to the proposal of a reduction curve used to determine a passive force skew reduction factor depending on abutment skew angle (Shamsabadi and Rollins 2014). In all previous tests, a uniform longitudinal load has been applied to the simulated bridge abutment. During seismic events, however, it is unlikely that bridge abutments would experience pure longitudinal loading. Rather, an inclined loading situation would be expected, causing rotation of the abutment backwall into the backfill. In this study, a large-scale test was performed where inclined loading was applied to a 30° skewed bridge abutment with sand backfill and compared to a baseline test with uniform loading and a non-skewed abutment. The impact of rotational force on the passive resistance of the backfill and the skew adjust factor was then evaluated. It was determined that inclined loading does not have a significant effect on the passive force skew reduction factor. However, the reduction factor was somewhat higher than predicted by the proposed reduction curve from Shamsabadi and Rollins 2014. This can be explained by a reduction in the effective skew angle caused by the friction between the side walls and the back wall. The inclined loading did not change the amount of movement required to mobilize passive resistance with ultimate passive force developing for displacements equal to 3 to 6% of the wall height. The rotation of the pile cap due to inclined loading produced higher earth pressure on the obtuse side of the skew wedge, as was expected.These findings largely resolve the concern that inclined loading situations during an earthquake may render the proposed passive force skew reduction curve invalid. We suggest that the proposed reduction curve remains accurate during inclined loading and should be implemented in current codes and practices to properly account for skew angle in bridge design.

Skewed bridges have exhibited poorer performance during lateral earthquake loading in comparison to non-skewed bridges (Apirakvorapinit et al. 2012; Elnashai et al. 2010). Results from numerical modeling by Shamsabadi et al. (2006), small-scale laboratory tests by Rollins and Jessee (2012), and several large-scale tests performed by Rollins et al. at Brigham Young University (Franke 2013; Marsh 2013; Palmer 2013; Smith 2014; Frederickson 2015) led to the proposal of a reduction curve used to determine a passive force skew reduction factor depending on abutment skew angle (Shamsabadi and Rollins 2014). In all previous tests, a uniform longitudinal load has been applied to the simulated bridge abutment. During seismic events, however, it is unlikely that bridge abutments would experience pure longitudinal loading. Rather, an inclined loading situation would be expected, causing rotation of the abutment backwall into the backfill. In this study, a large-scale test was performed where inclined loading was applied to a 30 skewed bridge abutment with sand backfill and compared to a baseline test with uniform loading and a non-skewed abutment. The impact of rotational force on the passive resistance of the backfill and the skew adjust factor was then evaluated. It was determined that inclined loading does not have a significant effect on the passive force skew reduction factor. However, the reduction factor was somewhat higher than predicted by the proposed reduction curve from Shamsabadi and Rollins 2014. This can be explained by a reduction in the effective skew angle caused by the friction between the side walls and the back wall. The inclined loading did not change the amount of movement required to mobilize passive resistance with ultimate passive force developing for displacements equal to 3 to 6% of the wall height. The rotation of the pile cap due to inclined loading produced higher earth pressure on the obtuse side of the skew wedge, as was expected.These findings largely resolve the concern that inclined loading situations during an earthquake may render the proposed passive force skew reduction curve invalid. We suggest that the proposed reduction curve remains accurate during inclined loading and should be implemented in current codes and practices to properly account for skew angle in bridge design.