MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
A Rational Krylov Toolbox for MATLAB
Get PDFThe Rational Krylov Toolbox contains MATLAB implementations of Ruhe's rational Krylov sequence method, algorithms for the implicit and explicit relocation of the poles of a rational Krylov space, and an implementation of RKFIT, a robust algorithm for rational least squares fitting
Solving log-transformed random diffusion problems by stochastic Galerkin mixed finite element methods
Get PDFStochastic Galerkin finite element discretisations of PDEs with stochastically nonlinear coefficients lead to linear systems of equations with block dense matrices. In contrast, stochastic Galerkin finite element discretisations of PDEs with stochastically linear coefficients lead to linear systems of equations with block sparse matrices which are cheaper to manipulate and precondition in the framework of Krylov subspace iteration. In this paper we focus on mixed formulations of second-order elliptic problems, where the diffusion coefficient is the exponential of a random field, and the priority is to approximate the flux. We build on the previous work [Efficient iterative solvers for stochastic Galerkin discretizations of log-transformed random diffusion problems, SIAM J.~Sci.~Comput., 34(2012), pp.A659--A682] and reformulate the PDE model as a first-order system in which the logarithm of the diffusion coefficient appears on the left-hand side. We apply a stochastic Galerkin mixed finite element method and discuss block triangular and block diagonal preconditioners for use with GMRES iteration. In particular, we analyse a practical approximation to the Schur complement of the Galerkin matrix and provide spectral inclusion bounds. Numerical experiments reveal that the preconditioners are completely insensitive to the spatial mesh size, and are only slightly sensitive to the statistical parameters of the diffusion coefficient. As a result, the computational cost required to approximate the flux when the diffusion coefficient is stochastically nonlinear grows only linearly with respect to the total problem size
Generalized rational Krylov decompositions with an application to rational approximation
Get PDFGeneralized rational Krylov decompositions are matrix relations which, under certain conditions, are associated with rational Krylov spaces. We study the algebraic properties of such decompositions and present an implicit Q theorem for rational Krylov spaces. Transformations on rational Krylov decompositions allow for changing the poles of a rational Krylov space without recomputation, and two algorithms are presented for this task. Using such transformations we develop a rational Krylov method for rational least squares fitting. Numerical experiments indicate that the proposed method converges fast and robustly. A MATLAB toolbox with implementations of the presented algorithms and experiments is provided
GPU Accelerated Structure-Exploiting Matched Forward and Back Projection for Algebraic Iterative Cone Beam CT Reconstruction
Get PDFAlgebraic iterative reconstruction algorithms have been the subject of much research into problems of limited data CT reconstruction. However, their use for practical problems, particularly for high resolution systems and corresponding large volume sizes, has often been considered unfeasible due to their high computational demands. For cone beam geometry, we present a highly parallel adaptation of Siddon�s algorithm for discrete forward and back projection, based on exploitation of structure in the pattern of the cone beam rays. The proposed algorithm has been implemented for nVidia GPUs using CUDA, resulting in speedup of an order of magnitude when tested against a non-structure exploiting parallel CPU implementation of Ja- cobs� algorithm. The work is presented in the context of circular scan, flat panel detector micro CT, but could easily be adapted to other scanning trajectories and detector configurations
Invariance Principles in Polyadic Inductive Logic
Get PDFWe show that the Permutation Invariance Principle can be equivalently stated to involve invariance under finitely many permutations, specified by their action on a particular finite set of formulae. We argue that these formulae define the polyadic equivalents of unary atoms. Using this we investigate the properties of probability functions satisfying this principle, in particular, we examine the idea that the Permutation Invariance Principle provides a natural generalisation of (unary) Atom Exchangeability. We also clarify the status of the Principle of Super Regularity in relation to invariance principles
Dimensionality Reduction for Dynamical Systems with Parameters
No full textDimensionality reduction methods allow for the study of high-dimensional systems by producing low-dimensional descriptions that preserve the relevant structure and features of interest. For dynamical systems, attractors are particularly important ex- amples of such features, as they govern the long-term dynamics of the system, and are typically low-dimensional even if the state space is high- or infinite-dimensional. Methods for reduction need to be able to determine a suitable reduced state space in which to describe the attractor, and to produce a reduced description of the cor- responding dynamics. In the presence of a parameter space, a system can possess a family of attractors. Parameters are important quantities that represent aspects of the physical system not directly modelled in the dynamics, and may take different values in different instances of the system. Therefore, including the parameter dependence in the reduced system is desirable, in order to capture the model�s full range of behaviour.
Existing methods typically involve algebraically manipulating the original differ- ential equation, either by applying a projection, or by making local approximations around a fixed-point. In this work, we take more of a geometric approach, both for the reduction process and for determining the dynamics in the reduced space. For the reduction, we make use of an existing secant-based projection method, which has properties that make it well-suited to the reduction of attractors. We also regard the system to be a manifold and vector field, consider the attractor�s normal and tan- gent spaces, and the derivatives of the vector field, in order to determine the desired properties of the reduced system.
We introduce a secant culling procedure that allows for the number of secants to be greatly reduced in the case that the generating set explores a low-dimensional space. This reduces the computational cost of the secant-based method without sacrificing the detail captured in the data set. This makes it feasible to use secant-based methods with larger examples.
We investigate a geometric formulation of the problem of dimensionality reduction of attractors, and identify and resolve the complications that arise. The benefit of this approach is that it is compatible with a wider range of examples than conventional approaches, particularly those with angular state variables. In turn this allows for application to non-autonomous systems with periodic time-dependence. We also adapt secant-based projection for use in this more general setting, which provides a concrete method of reduction.
We then extend the geometric approach to include a parameter space, resulting in a family of vector fields and a corresponding family of attractors. Both the secant-based projection and the reproduction of dynamics are extended to produce a reduced model that correctly responds to the parameter dependence. The method is compatible with multiple parameters within a given region of parameter space. This is illustrated by a variety of examples
IFISS: A computational laboratory for investigating incompressible flow problems
No full textThe IFISS Incompressible Flow & Iterative Solver Software package contains software which can be run with MATLAB or Octave to create a computational laboratory for the interactive numerical study of incompressible flow problems. It includes algorithms for discretization by mixed finite element methods and a posteriori error estimation of the computed solutions, together with state-of-the-art preconditioned iterative solvers for the resulting discrete linear equation systems.
In this paper we give a flavour of the code's main features and illustrate its applicability using several case studies. We aim to show that IFISS can be a valuable tool in both teaching and research
Algorithms for Hessenberg-Triangular Reduction of Fiedler Linearization of Matrix Polynomials
No full textSmall- to medium-sized polynomial eigenvalue problems can be solved by linearizing the matrix polynomial and solving the resulting generalized eigenvalue problem using the QZ algorithm. The QZ algorithm, in turn, requires an initial reduction of a matrix pair to Hessenberg--triangular form. In this paper, we discuss the design and evaluation of high-performance parallel algorithms and software for Hessenberg--triangular reduction of a specific linearization of matrix polynomials of arbitrary degree. The proposed algorithm exploits the sparsity structure of the linearization to reduce the number of operations and improve the cache reuse compared to existing algorithms for unstructured inputs.Experiments on both a workstation and an HPC system demonstrate that our structure-exploiting parallel implementation can outperform both the general LAPACK routine DGGHRD and the prototype implementation DGGHR3 of a general blocked algorithm
Implementing QR Factorization Updating Algorithms on GPUs
Get PDFLinear least squares problems are commonly solved by QR factorization. When multiple solutions need to be computed with only minor changes in the underlying data, knowledge of the difference between the old data set and the new can be used to update an existing factorization at reduced computational cost. We investigate the viability of implementing QR updating algorithms on GPUs and demonstrate that GPU-based updating for removing columns achieves speed-ups of up to 13.5x compared with full GPU QR factorization. We characterize the conditions under which other types of updates also achieve speed-ups