MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Modified Cholesky Decomposition and Applications
Get PDFThe modified Cholesky decomposition is one of the standard tools in various areas of mathematics for dealing with symmetric indefinite matrices that are required to be positive definite. We survey the literature and determine which of the existing modified Cholesky algorithms is most suitable for inclusion in the Numerical Algorithms Group (NAG) software library, focussing in particular on the algorithms of Gill, Murray and Wright, Schnabel and Eskow, Cheng and Higham, and Moré and Sorensen. In order to make this determination we consider how best to take advantage of modern computer architectures and existing numerical software. We create an efficient implementation of the chosen algorithm and perform extensive numerical testing to ensure that it works as intended. We then discuss various applications of the modified Cholesky decomposition and show how the new implementation can be used for some of these. In particular, significant attention is devoted to describing how the modified Cholesky decomposition can be used to compute an upper bound on the distance to the nearest correlation matrix
A model theoretic approach to simple groups of finite Morley rank with finitary groups of automorphisms
No full textIn (Karhumäki, manuscript 2017), the author proved the following theorem:
An infinite simple group of finite Morley rank admitting a finitary group of automorphisms is a Chevalley group over an algebraically closed field of positive characteristic.
Proof of the theorem above was achieved by group theoretic methods, with a heavy use of methods (but not the statement of the Classification of Finite Simple Groups). In this paper we give an alternative model theoretic proof. In particular, this new approach is shorter and more transparent than the original proof
Gauge momenta as Casimir functions of nonholonomic systems
Get PDFWe consider nonholonomic systems with symmetry possessing a certain type of first integrals that are linear in the velocities. We develop a systematic method for modifying the standard nonholonomic almost Poisson structure that describes the dynamics so that these integrals become Casimir functions after reduction. This explains a number of recent results on Hamiltonization of nonholonomic systems, and has consequences for the study of relative equilibria in such systems
Nonbacktracking walk centrality for directed networks
Get PDFThe theory of zeta functions provides an expression for the generating fu
nction of
nonbacktracking walk counts on a directed network. We show how this
expression can be used to
produce a centrality measure that eliminates backtracking walks at
no cost. We also show that the
radius of convergence of the generating function is determined by the spect
rum of a three-by-three
block matrix involving the original adjacency matrix. This giv
es a means to choose appropriate
values of the attenuation parameter. We find that three important a
dditional benefits arise when we
use this technique to eliminate traversals around the network that
are unlikely to be of relevance.
First, we obtain a larger range of choices for the attenuation para
meter. Second, because the radius
of convergence of the generating function is invariant under the remov
al of certain types of nodes,
we can gain computational efficiencies through reducing the dimension of t
he resulting eigenvalue
problem. Third, the dimension of the linear system defining the centrali
ty measures may be reduced
in the same manner. We show that the new centrality measure may be interp
reted as standard Katz
on a modified network, where self loops are added, and where nonreciproca
l edges are augmented
with negative weights. We also give a multilayer interpretation, wh
ere negatively weighted walks
between layers compensate for backtracking walks on the only non-emp
ty layer. Studying the limit
as the attenuation parameter approaches its upper bound allows us
to propose an eigenvector-based
nonbacktracking centrality measure in this directed network setting.
We find that the two-by-two
block matrix arising in previous studies focused on undirected networks
must be extended to a new
three-by-three block structure to allow for directed edges. We illustrat
e the centrality measure on
a synthetic network, where it is shown to eliminate a localization effect p
resent in standard Katz
centrality. Finally, we give results for real networks
Workshop on Batched, Reproducible, and Reduced Precision BLAS
Get PDFA summary of the second workshop on Batched, Reproducible, and Reduced Precision BLAS
CBS Constants and Their Role in Error Estimation for Stochastic Galerkin Finite Element Methods
Get PDFStochastic Galerkin finite element methods (SGFEMs) are commonly used to approximate solutions to PDEs with random inputs. However, the study of a posteriori error estimation strategies to drive adaptive enrichment of the associated tensor product spaces is still in its infancy. In this work, we revisit an error estimator introduced in [A. Bespalov, D. Silvester, Efficient adaptive stochastic Galerkin methods for parametric operator equations, SIAM J. Sci. Comput., 38(4), 2016] for SGFEM approximations of the parametric reformulation of the stochastic diffusion problem. We show that the proven bound for that error estimator can be derived using classical theory that is well known for determinstic Galerkin FEMs. A key issue is that the bound involves a CBS (Cauchy-Buniakowskii-Schwarz) constant. If the approximation spaces associated with the parameter domain are orthogonal, then this CBS constant only depends on a pair of finite element spaces H1, H2 and their compatibility with respect to an inner product associated with a parameter-free problem. For fixed choices of H2, we investigate non-standard choices of H2 and the associated CBS constants, with the aim of designing efficient error estimators. When H1 and H2 satisfy certain conditions, we also prove theoretical estimates for the CBS constant using a novel linear algebra approach. Our results are also applicable to the design of adaptive finite element schemes for deterministic PDEs
Quadratic Realizability of Palindromic Matrix Polynomials
Get PDFLet \cL = (\cL_1,\cL_2) be a list consisting
of a sublist \cL_1
of powers of irreducible (monic) scalar polynomials
over an algebraically closed field \FF,
and a sublist \cL_2 of nonnegative integers.
For an arbitrary such list \cL,
we give easily verifiable necessary
and sufficient conditions
for \cL to be the list of elementary divisors
and minimal indices
of some -palindromic quadratic matrix polynomial
with entries in the field \FF.
For \cL satisfying these conditions,
we show how to explicitly construct a -palindromic quadratic matrix polynomial
having \cL as its structural data;
that is, we provide a -palindromic
quadratic realization of \cL.
Our construction of -palindromic realizations
is accomplished
by taking a direct sum of low bandwidth
-palindromic blocks,
closely resembling the Kronecker canonical form
of matrix pencils.
An immediate consequence of our in-depth study
of the structure
of -palindromic quadratic polynomials is
that all even grade -palindromic matrix polynomials
have a -palindromic strong quadratification.
Finally, using a particular M\"{o}bius transformation,
we show how all of our results can be easily extended
to quadratic matrix polynomials with -even structure
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
Accelerating the Solution of Linear Systems by Iterative Refinement in Three Precisions
No full textWe propose a general algorithm for solving a nonsingular linear system based on iterative refinement with three precisions. The working precision is combined with possibly different precisions for solving for the correction term and for computing the residuals. Via rounding error analysis of the algorithm we derive sufficient conditions for convergence and bounds for the attainable normwise forward error and normwise and componentwise backward errors. Our results generalize and unify many existing rounding error analyses for iterative refinement. With single precision as the working precision, we show that by using LU factorization in IEEE half precision as the solver and calculating the residuals in double precision it is possible to solve to full single precision accuracy for condition numbers , with the part of the computations carried out entirely in half precision. We show further that by solving the correction equations by GMRES preconditioned by the LU factors the restriction on the condition number can be weakened to , although in general there is no guarantee that GMRES will converge quickly. Taking for comparison a standard solver that uses LU factorization in single precision, these results suggest that on architectures for which half precision is efficiently implemented it will be possible to solve certain linear systems up to twice as fast \emph{and} to greater accuracy. Analogous results are given with double precision as the working precision