MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Explicit Solutions to Correlation Matrix Completion Problems, with an Application to Risk Management and Insurance
Get PDFWe derive explicit solutions to the problem of completing a partially specified correlation matrix. Our results apply to several block structures for the unspecified entries that arise in insurance and risk management, where an insurance company with many lines of business is required to satisfy certain capital requirements but may have incomplete knowledge of the underlying correlation matrix. Among the many possible completions we focus on the one with maximal determinant. This has attractive properties and we argue that it is suitable for use in the insurance application. Our explicit formulas enable easy solution of practical problems and are useful for testing algorithms for the general correlation matrix completion problem
Optimal iterative solvers for linear systems with stochastic PDE origins: Balanced black-box stopping tests
Get PDFThe central theme of this thesis is the design of optimal balanced black-box stopping criteria in iterative solvers of symmetric positive-definite, symmetric indefinite, and nonsymmetric linear systems arising from finite element approximation of stochastic (parametric) partial differential equations.
For a given stochastic and spatial approximation, it is known that iteratively solving the corresponding linear(ized) system(s) of equations to too tight algebraic error tolerance results in a wastage of computational resources without decreasing the usually unknown approximation error. In order to stop optimally—by avoiding unnecessary computations and premature stopping—algebraic error and a posteriori approximation error estimate must be balanced at the optimal stopping iteration. Efficient and reliable a posteriori error estimators do exist for close estimation of the approximation error in a finite element setting. But the algebraic error is generally unknown since the exact algebraic solution is not usually available. Obtaining tractable upper and lower bounds on the algebraic error in terms of a readily computable and monotonically decreasing quantity (if any) of the chosen iterative solver is the distinctive feature of the designed optimal balanced stopping strategy. Moreover, this work states the exact constants, that is, there are no user-defined parameters in the optimal balanced stopping tests. Hence, an iterative solver incorporating the optimal balanced stopping methodology that is presented here will be a black-box iterative solver. Typically, employing such a stopping methodology would lead to huge computational savings and in any case would definitely rule out premature stopping.
The constants in the devised optimal balanced black-box stopping tests in MINRES solver for solving symmetric positive-definite and symmetric indefinite linear systems can be estimated cheaply on-the-fly. The contribution of this thesis goes one step further for the nonsymmetric case in the sense that it not only provides an optimal balanced black-box stopping test in a memory-expensive Krylov solver like GMRES but it also presents an optimal balanced black-box stopping test in memory-inexpensive Krylov solvers such as BICGSTAB(l), TFQMR etc. Currently, little convergence theory exists for the memory-inexpensive Krylov solvers and hence devising stopping criteria for them is an active field of research. Also, an optimal balanced black-box stopping criterion is proposed for nonlinear (Picard or Newton) iterative method that is used for solving the finite dimensional Navier–Stokes equations.
The optimal balanced black-box stopping methodology presented in this thesis can be generalized for any iterative solver of a linear(ized) system arising from numerical approximation of a partial differential equation. The only prerequisites for this purpose are the existence of a cheap and tight a posteriori error estimator for the approximation error along with cheap and tractable bounds on the algebraic error
A Nonlinear ParaExp Algorithm
Get PDFWe propose and analyse a variant of the ParaExp algorithm for nonlinear initial value problems. We show that this algorithm is mathematically equivalent to a parareal iteration where the coarse integrator solves linear subproblems on overlapping time intervals. A numerical example with a nonlinear wave equation illustrates the convergence behaviour
Ancient Indian Logic and Analogy
Get PDFB.K.Matilal, and earlier J.F.Staal, have suggested a reading of the `Ny\={a}ya five limb schema' (also sometimes referred to as the Indian Schema or Hindu Syllogism) from Gotama's Ny\={a}ya-S\={u}tra in terms of a binary {\it occurrence} relation. In this paper we provide a rational justification of a version of this reading as Analogical Reasoning within the framework of Polyadic Pure Inductive Logic
Multiprecision Algorithms for Computing the Matrix Logarithm
Get PDFTwo algorithms are developed for computing the matrix logarithm in floating
point arithmetic of any specified precision. The backward error-based
approach used in the state of the art inverse scaling and squaring
algorithms does not conveniently extend to a multiprecision environment, so
instead we choose algorithmic parameters based on a forward error bound. We
derive a new forward error bound for Pad\'{e} approximants that for
highly nonnormal matrices can be much smaller than the classical bound of
Kenney and Laub. One of our algorithms exploits a Schur decomposition
while the other is transformation-free and uses only the computational
kernels of matrix multiplication and the solution of multiple right-hand
side linear systems. For double precision computations the algorithms are
competitive with the state of the art algorithm of Al-Mohy, Higham, and
Relton implemented in \texttt{logm} in MATLAB\@. They are intended for
computing environments providing multiprecision floating point arithmetic,
such as Julia, MATLAB via the Symbolic Math Toolbox or the Multiprecision
Computing Toolbox, or Python with the mpmath or SymPy packages. We show
experimentally that
the algorithms behave in a forward stable manner over a
wide range of precisions, unlike existing alternatives
A New Algorithm for Computing the Actions of Trigonometric and Hyperbolic Matrix Functions
Get PDFA new algorithm is derived for computing the actions and , where is cosine, sinc, sine, hyperbolic cosine, hyperbolic sinc, or hyperbolic sine function. is an matrix and is with . denotes any matrix square root of and it is never required
to be computed. The algorithm offers six independent output options given , , , and a tolerance. For each option, actions of a pair of trigonometric or
hyperbolic matrix functions are simultaneously computed.
The algorithm scales the matrix down by a positive integer , approximates by a truncated Taylor series, and finally uses the recurrences of the Chebyshev polynomials of the first and second kind to recover . The selection of the scaling parameter
and the degree of Taylor polynomial are based on a forward error analysis and a sequence of the form in such a way the overall computational cost of the algorithm is optimized.
Shifting is used where applicable as a preprocessing step to reduce the scaling parameter.
The algorithm works for any matrix and
its computational cost is dominated by the formation of products of with matrices that could take advantage of the implementation of level-3 BLAS.
Our numerical experiments show that the new algorithm behaves in a forward stable fashion and in most problems outperforms the existing algorithms in terms of CPU time, computational cost, and accuracy
On the spectra of finite type algebras
Get PDFLet X be a complex affine variety and k its coordinate algebra. This paper will review Morita equivalence for k-algebras and will then review, for finite type k-algebras, a weakening of Morita equivalence called spectral equivalence.
The spectrum of A is, by definition, the set of equivalence classes of irreducible A-modules. For any finite type k-algebra A, the spectrum of A is in bijection with the set of primitive ideals of A. The spectral equivalence relation preserves the spectrum of A and also preserves the periodic cyclic homology of A. However, the spectral equivalence relation permits a tearing apart of strata in the primitive ideal space which is not allowed by Morita equivalence.
A key example illustrating the distinction between Morita equivalence and spectral equivalence relation is provided by affine Hecke algebras associated to affine Weyl groups. We also review the role of spectral equivalence in the ABPS conjecture
Rational Krylov Decompositions: Theory and Applications
Get PDFNumerical methods based on rational Krylov spaces have become an indispensable tool of scientific computing. In this thesis we study rational Krylov spaces by considering rational Krylov decompositions; matrix relations which, under certain conditions, are associated with these spaces. We investigate the algebraic properties of such decompositions and present an implicit Q theorem for rational Krylov spaces.
We derive standard and harmonic Ritz extraction strategies for approximating the eigenpairs of a matrix and for approximating the action of a matrix function
onto a vector. While these topics have been considered previously, our approach does not require the last pole to be infinite, which makes the extraction procedure
computationally more efficient.
Typically, the computationally most expensive component of the rational Arnoldi algorithm for computing a rational Krylov basis is the solution of a large linear system of equations at each iteration. We explore the option of solving several linear systems simultaneously, thus constructing the rational Krylov basis in parallel. If this is not done carefully, the basis being orthogonalized may become poorly conditioned, leading
to numerical instabilities in the orthogonalization process. We introduce the new concept of continuation pairs which gives rise to a near-optimal parallelization strategy that allows to control the growth of the condition number of this nonorthogonal basis. As a consequence we obtain a more accurate and reliable parallel rational Arnoldi algorithm. The computational benefits are illustrated using our high performance C++ implementation.
We develop an iterative algorithm for solving nonlinear rational least squares problems. The difficulty is in finding the poles of a rational function. For this purpose, at each iteration a rational Krylov decomposition is constructed and a modified linear problem is solved in order to relocate the poles to new ones. Our numerical results indicate that the algorithm, called RKFIT, is well suited for model order reduction of linear time invariant dynamical systems and for optimisation problems related to exponential integration. Furthermore, we derive a strategy for the degree reduction of the approximant obtained by RKFIT. The rational function obtained by RKFIT is represented with the aid of a scalar rational Krylov decomposition and an additional coefficient vector. A function represented in this form is called an RKFUN. We develop efficient methods for the evaluation, pole and root finding, and for performing basic arithmetic operations with RKFUNs.
Lastly, we discuss RKToolbox, a rational Krylov toolbox for MATLAB, which implements all our algorithms and is freely available from http://rktoolbox.org. RKToolbox also features an extensive guide and a growing number of examples. In particular, most of our numerical experiments are easily reproducible by downloading
the toolbox and running the corresponding example files in MATLAB
Arnold-Winther Mixed Finite Elements for Stokes Eigenvalue Problems
Get PDFThis paper is devoted to study the Arnold-Winther mixed finite element method
for two dimensional Stokes eigenvalue problems using the stress-velocity formulation.
A priori error estimates for the eigenvalue and eigenfunction errors are presented.
To improve the approximation for both eigenvalues and eigenfunctions, we propose a local post-processing.
With the help of the local post-processing, we derive a reliable a posteriori error estimator which is shown
to be empirically efficient.
We confirm numerically the proven higher order convergence of the post-processed eigenvalues for convex domains
with smooth eigenfunctions.
On adaptively refined meshes we obtain numerically optimal higher orders of convergence of the post-processed eigenvalues
even on nonconvex domains
Linearizations of Matrix Polynomials in Newton Bases
Get PDFWe discuss matrix polynomials expressed in a Newton basis,
and the associated polynomial eigenvalue problems.
Properties of the generalized ansatz spaces
associated with such polynomials
are proved directly by utilizing a novel representation of pencils in these spaces.
Also, we show how the family of Fiedler pencils
can be adapted to matrix polynomials expressed
in a Newton basis.
These new Newton-Fiedler pencils are shown to be strong linearizations,
and some computational aspects related to them are discussed