MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Computing the Action of Trigonometric and Hyperbolic Matrix Functions
Get PDFWe derive a new algorithm for computing the action of the cosine,
sine, hyperbolic cosine, and
hyperbolic sine of a matrix on a matrix ,
without first computing .
The algorithm can compute
and simultaneously, and likewise for
and ,
and it uses only real arithmetic when is real.
The algorithm exploits an existing algorithm \texttt{expmv}
of Al-Mohy and Higham for
and its underlying backward error analysis.
Our experiments show that the new algorithm performs in
a forward stable manner and is generally significantly faster than
alternatives based on multiple invocations of \texttt{expmv}
through formulas such as
Anderson Acceleration of the Alternating Projections Method for Computing the Nearest Correlation Matrix
Get PDFIn a wide range of applications it is required to compute the nearest correlation matrix in the Frobenius norm to a given symmetric but indefinite matrix. Of the available methods with guaranteed convergence to the unique solution of this problem the easiest to implement, and perhaps the most widely used, is the alternating projections method. However, the rate of convergence of this method is at best linear, and it can require a large number of iterations to converge to within a given tolerance. We show that Anderson acceleration, a technique for accelerating the convergence of fixed-point iterations, can be applied to the alternating projections method and that in practice it brings a significant reduction in both the number of iterations and the computation time. We also show that Anderson acceleration remains effective, and indeed can provide even greater improvements, when it is applied to the variants of the nearest correlation matrix problem in which specified elements are fixed or a lower bound is imposed on the smallest eigenvalue. Alternating projections is a general method for finding a point in the intersection of several sets and ours appears to be the first demonstration that this class of methods can benefit from Anderson acceleration
Workshop on Batched, Reproducible, and Reduced Precision BLAS
Get PDFThis report summarises the main points raised on a recent workshop discussing various extensions to the BLAS standard, held at the University of Tennessee in May 2016. In particular the discussions focused on batched, reproducible, and reduced precision BLAS extensions. Various members of the linear algebra community and representatives from Intel, NVIDIA, and ARM were present to generate and evaluate ideas in each of these areas
A Comparison of Potential Interfaces for Batched BLAS Computations
Get PDFOne trend in modern high performance computing (HPC) is to decompose a large
linear algebra problem into thousands of small problems which can be solved indepen-
dently. There is a clear need for a batched BLAS standard, allowing users to perform
thousands of small BLAS operations in parallel and making efficient use of their hard-
ware. There are many possible ways in which the BLAS standard can be extended
for batch operations. We discuss many of these possible designs, giving benefits and
criticisms of each, along with a number of experiments designed to determine how the
API may affect performance on modern HPC systems. Related issues that influence
API design, such as the effect of memory layout on performance, are also discussed
An algorithm for computing the eigenvalues of a max-plus matrix polynomial
Get PDFMax-plus matrix polynomial eigenvalues provide a useful approximation to the order of magnitude of the eigenvalues of a classical (i.e. real or complex) matrix polynomial. In this paper we review the max-plus matrix eigensolver of Gassner and Klinz [1] and present our extension of this algorithm to the max-plus matrix polynomial case. Our max-plus matrix polynomial algo- rithm computes all nd max-plus eigenvalues of a n � n degree d max-plus matrix polynomial with worst case cost O(n3d) in the dense case, which is the best that we are aware of
Incomplete LU preconditioner based on max-plus approximation of LU factorization
Get PDFWe present a new method for the a priori approximation of the orders of magnitude of the entries in the LU factors of a complex or real matrix . This approximation can be used to quickly determine the positions of the largest entries in the LU factors of and these positions can then be used as the sparsity pattern for an incomplete LU factorization preconditioner. Our method uses max-plus algebra and is based solely on the moduli of the entries of . We also present techniques for predicting which permutation matrices will be chosen by Gaussian elimination with partial pivoting. We exploit the strong connection between the field of Puiseux series and the max-plus semiring to prove properties of the max-plus LU factors.
Experiments with a set of test matrices from the University of Florida sparse matrix collection show that our max-plus LU preconditioners outperform traditional level of fill methods and have similar performance to those preconditioners computed with more expensive threshold-based methods
Compressing variable-coefficient exterior Helmholtz problems via RKFIT
Get PDFThe efficient discretization of Helmholtz problems on unbounded domains is a challenging task, in particular, when the wave medium is nonhomogeneous. We present a new numerical approach for compressing finite difference discretizations of such problems, thereby giving rise to efficient perfectly matched layers (PMLs) for nonhomogeneous media. This approach is based on the solution of a nonlinear rational least squares problem using the RKFIT method proposed in [M. Berljafa and S. G���¼ttel, SIAM J. Matrix Anal. Appl., 36(2):894--916, 2015]. We show how the solution of this least squares problem can be converted into an accurate finite difference grid within a rational Krylov framework. Several numerical experiments are included. They indicate that RKFIT computes PMLs more accurate than previous analytic approaches and even works in regimes where the Dirichlet-to-Neumann functions to be approximated are highly irregular. Spectral adaptation effects allow for accurate finite difference grids with point numbers below the Nyquist limit
Incomplete LU preconditioner based on max-plus approximation of LU factorization
Get PDFWe present a new method for the a priori approximation of the orders of magnitude of the entries in the LU factors of a complex or real matrix . This approximation can be used to quickly determine the positions of the largest entries in the LU factors of and these positions can then be used as the sparsity pattern for an incomplete LU factorization preconditioner. Our method uses max-plus algebra and is based solely on the moduli of the entries of . We also present techniques for predicting which permutation matrices will be chosen by Gaussian elimination with partial pivoting. We exploit the strong connection between the field of Puiseux series and the max-plus semiring to prove properties of the max-plus LU factors.
Experiments with a set of test matrices from the University of Florida sparse matrix collection show that our max-plus LU preconditioners outperform traditional level of fill methods and have similar performance to those preconditioners computed with more expensive threshold-based methods
A rational deferred correction approach to parabolic optimal control problems
Get PDFThe accurate and efficient solution of time-dependent PDE-constrained optimization problems is a challenging task, in large part due to the very high dimension of the matrix systems that need to be solved. We devise a new deferred correction method for coupled systems of time-dependent PDEs, allowing one to iteratively improve the accuracy of low-order time stepping schemes. We consider two variants of our method, a splitting and a coupling version, and analyze their convergence properties. We then test our approach on a number of PDE-constrained optimization problems. We obtain solution accuracies far superior to that achieved when solving a single discretized problem, in particular in cases where the accuracy is limited by the time discretization. Our approach allows for the direct reuse of existing solvers for the resulting matrix systems, as well as state-of-the-art preconditioning strategies
Rigid orbits and sheets in reductive Lie algebras over fields of prime characteristic.
Get PDFWe classify the sheets and the rigid nilpotent orbits in reductive Lie algebras over fields of good characteristic and show that the distribution of nilpotent orbits amongst the sheets remains the same as in the characteristic zero case. We use GAP to determine the reachable and strongly reachable nilpotent orbits in all characteristics and provide some information on derived subalgebras of centralisers