MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Bounds for the Distance to the Nearest Correlation Matrix
Get PDFIn a wide range of practical problems correlation matrices are formed in such a way that, while symmetry and a unit diagonal are assured, they may lack semidefiniteness. We derive a variety of new upper bounds for the distance from an arbitrary symmetric matrix to the nearest correlation matrix. The bounds are of two main classes: those based on the eigensystem and those based on a modified Cholesky factorization. Bounds from both classes have a computational cost of flops for a matrix of order but are much less expensive to evaluate than the nearest correlation matrix itself. For unit diagonal with for all the eigensystem bounds are shown to overestimate the distance by a factor at most . We show that for a collection of matrices from the literature and from practical applications the eigensystem-based bounds are often good order of magnitude estimates of the actual distance; indeed the best upper bound is never more than a factor larger than a related lower bound. The modified Cholesky bounds are less sharp but also less expensive, and they provide an efficient way to test for definiteness of the putative correlation matrix. Both classes of bounds enable a user to identify an invalid correlation matrix relatively cheaply and to decide whether to revisit its construction or to compute a replacement, such as the nearest correlation matrix
Parallelization of the rational Arnoldi algorithm
Get PDFRational Krylov methods are applicable to a wide range of scientific computing problems, and the rational Arnoldi algorithm is a commonly used procedure for computing an orthonormal basis of a rational Krylov space. Typically, the computationally most expensive component of this algorithm 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 badly 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 significantly more accurate and reliable parallel rational Arnoldi algorithm. The computational benefits are illustrated using several numerical examples from different application areas
Strong linearizations of rational matrices
Get PDFThis paper defines for the first time strong linearizations of arbitrary rational matrices, studies in depth properties and diferent characterizations
of such linear matrix pencils, and develops infinitely many
examples of strong linearizations that can be explicitly and easily constructed from a minimal state-space realization of the strictly proper
part of the considered rational matrix and the coefficients of the polynomial part. As a consequence, the results in this paper establish a rigorous foundation for the numerical computation of the complete structure of zeros and poles, both finite and at infinity, of any rational matrix by applying any well known backward stable algorithm for generalized eigenvalue problems to any of the strong linearizations explicitly constructed in this work. Since the results of this paper require to use several concepts that are not standard in matrix computations,
a considerable effort has been done to make the paper as self-contained as possible
Stratified Langlands duality in the A_n tower
Get PDFLet S_k denote a maximal torus in the complex Lie group G = SL_n(C)/C_k and let T_k denote a maximal torus in its compact real form SU_n(C)/C_k, where k divides n.
Let W denote the Weyl group of G, namely the symmetric group S_n.
We elucidate the structure of the extended quotient S_k // W as an algebraic variety and of T_k // W as a topological space, in both cases describing them as bundles over unions of tori. Corresponding to the invariance of K-theory under Langlands duality, this calculation provides a homotopy equivalence between T_k // W and its dual T_{n/k} // W. Hence there is an isomorphism in cohomology for the extended quotients which is stratified as a direct sum over conjugacy classes of the Weyl group. We use our formula to compute a number of examples
Strong linearizations of rational matrices
Get PDFThis paper defines for the first time strong linearizations of arbitrary rational matrices, studies in depth properties and diferent characterizations
of such linear matrix pencils, and develops infinitely many
examples of strong linearizations that can be explicitly and easily constructed from a minimal state-space realization of the strictly proper
part of the considered rational matrix and the coefficients of the polynomial part. As a consequence, the results in this paper establish a rigorous foundation for the numerical computation of the complete structure of zeros and poles, both finite and at infinity, of any rational matrix by applying any well known backward stable algorithm for generalized eigenvalue problems to any of the strong linearizations explicitly constructed in this work. Since the results of this paper require to use several concepts that are not standard in matrix computations,
a considerable effort has been done to make the paper as self-contained as possible
The Right Way to Search Evolving Graphs
Get PDFEvolving graphs arise in many different contexts
where the interrelations between data elements change over
time. We present a breadth first search (BFS) algorithm for
evolving graphs that can track (active) nodes correctly. Using
simple examples, we show naïve matrix-matrix multiplication
on time-dependent adjacency matrices miscounts the number
of temporal paths. By mapping an evolving graph to an
adjacency matrix of the equivalent static graph, we prove
the properties of the BFS algorithm using the properties of
the adjacency matrix. Finally, demonstrate how the BFS over
evolving graphs can be applied to mining citation network
The Right Way to Search Evolving Graphs
Get PDFEvolving graphs arise in problems where interrelations between data change over time. We present a breadth
first search (BFS) algorithm for evolving graphs that computes
the most direct influences between nodes at two different
times. Using simple examples, we show that na �ıve unfoldings
of adjacency matrices miscount the number of temporal paths.
By mapping an evolving graph to an adjacency matrix of an
equivalent static graph, we prove that our generalization of the
BFS algorithm correctly accounts for paths that traverse both
space and time. Finally, we demonstrate how the BFS over
evolving graphs can be applied to mine citation networks
A Daleckii-Krein formula for the Frechet derivative of a generalized matrix function
Get PDFWe state and prove an extension of the Daleckii-Krein theorem, thus obtaining an
explicit formula for the Frechet derivative of generalized matrix functions. Moreover,
we prove the differentiability of generalized matrix functions of real matrices under very
mild assumptions. For complex matrices, we argue that generalized matrix functions
are real differentiable but generally not complex differentiable. Finally, we discuss the
application of our result to the study of the condition number of generalized matrix
functions. Along our way, we also derive generalized matrix functional analogues of
a few classical theorems on polynomial interpolation of classical matrix functions and
their derivatives
Taylor's Theorem for Matrix Functions with Applications to Condition Number Estimation
Get PDFWe derive an explicit formula for the remainder term of a
Taylor polynomial of a matrix function.
This formula generalizes a known result for the remainder of the
Taylor polynomial for an analytic function of a complex scalar.
We investigate some consequences of this result,
which culminate in new upper bounds for the level-1 and level-2
condition numbers of a matrix function in terms of the
pseudospectrum of the matrix.
Numerical experiments show that,
although the bounds can be pessimistic,
they can be computed much faster than the standard methods.
This makes the upper bounds ideal for a quick estimation of the
condition number whilst a more accurate (and expensive) method
can be used if further accuracy is required.
They are also easily applicable to more complicated matrix functions
for which no specialized condition number estimators are
currently available
A Block Krylov Method to Compute the Action of the Frechet Derivative of a Matrix Function on a Vector with Applications to Condition Number Estimation
Get PDFWe design a block Krylov method to compute the action of the Fréchet derivative of a
matrix function on a vector using only matrix�vector products. The algorithm we derive is especially
effective when the direction matrix in the derivative is of low rank. Our results and experiments
are focused mainly on Fréchet derivatives with rank-1 direction matrices. Our analysis applies to all
functions with a power series expansion convergent on a subdomain of the complex plane which, in
particular, includes the matrix exponential. We perform an a priori error analysis of our algorithm to
obtain rigorous stopping criteria. Furthermore, we show how our algorithm can be used to estimate
the 2-norm condition number of f(A)b efficiently. Our numerical experiments show that our new
algorithm for computing the action of a Fréchet derivative typically requires a small number of
iterations to converge and (particularly for single and half precision accuracy) is significantly faster
than alternative algorithms. When applied to condition number estimation our experiments show
that the resulting algorithm can detect ill-conditioned problems that are undetected by competing
algorithms