MIMS EPrints
Not a member yet
2151 research outputs found
Sort by
Computational graphs for matrix functions
Full text linkMany numerical methods for evaluating matrix functions can be naturally viewed as computational graphs. Rephrasing these methods as directed acyclic graphs (DAGs) is a particularly effective way to study existing techniques, improve them, and eventually derive new ones. As the accuracy of these matrix techniques is determined by the accuracy of their scalar counterparts, the design of algorithms for matrix functions can be viewed as a scalar-valued optimization problem. The derivatives needed during the optimization can be calculated automatically by exploiting the structure of the DAG, in a fashion akin to backpropagation. The Julia package GraphMatFun.jl offers the tools to generate and manipulate computational graphs, to optimize their coefficients, and to generate Julia, MATLAB, and C code to evaluate them efficiently. The software also provides the means to estimate the accuracy of an algorithm and thus obtain numerically reliable methods. For the matrix exponential, for example, using a particular form (degree-optimal) of polynomials produces algorithms that are cheaper, in terms of computational cost, than the Padé-based techniques typically used in mathematical software. The optimized graphs and the corresponding generated code are available online
Mixed Precision Algorithms in Numerical Linear Algebra
No full textToday's floating-point arithmetic landscape is broader than ever. While scientific computing has traditionally used single precision and double precision floating-point arithmetics, half precision is increasingly available in hardware and quadruple precision is supported in software. Lower precision arithmetic brings increased speed and reduced communication and energy costs, but it produces results of correspondingly low accuracy. Higher precisions are more expensive but can potentially provide great benefits, even if used sparingly. A variety of mixed precision algorithms have been developed that combine the superior performance of lower precisions with the better accuracy of higher precisions. Some of these algorithms aim to provide results of the same quality as algorithms running in a fixed precision but at a much lower cost; others use a little higher precision to improve the accuracy of an algorithm. This survey treats a broad range of mixed precision algorithms in numerical linear algebra, both direct and iterative, for problems including matrix multiplication, matrix factorization, linear systems, least squares, eigenvalue decomposition, and singular value decomposition. We identify key algorithmic ideas, such as iterative refinement, adapting the precision to the data, and exploiting mixed precision block fused multiply--add operations. We also describe the possible performance benefits and explain what is known about the numerical stability of the algorithms. This survey should be useful to a wide community of researchers and practitioners who wish to develop or benefit from mixed precision numerical linear algebra algorithms
Optimizing and Factorizing the Wilson Matrix
No full textThe Wilson matrix, , is a unimodular symmetric positive definite matrix of integers that has been used as a test matrix since the 1940s, owing to its mild ill-conditioning. We ask how close is to being the most ill-conditioned matrix in its class, with or without the requirement of positive definiteness. By exploiting the matrix adjugate and applying various matrix norm bounds from the literature we derive bounds on the condition numbers for the two cases and we compare them with the optimal condition numbers found by exhaustive search. We also investigate the existence of factorizations with having integer or rational entries. Drawing on recent research that links the existence of these factorizations to number-theoretic considerations of quadratic forms, we show that has an integer factor and two rational factors, up to signed permutations. This little matrix continues to be a useful example on which to apply existing matrix theory as well as being capable of raising challenging questions that lead to new results
Anymatrix: An Extensible MATLAB Matrix Collection. Users' Guide
Full text linkThis guide is for users and developers of the Anymatrix MATLAB toolbox, which provides an extensible collection of matrices organized into groups and sets and the ability to search for matrices by their properties. Full details of the usage of Anymatrix are given, along with details of the implementation
Mixed Precision Algorithms in Numerical Linear Algebra
No full textToday's floating-point arithmetic landscape is broader than ever. While scientific computing has traditionally used single precision and double precision floating-point arithmetics, half precision is increasingly available in hardware and quadruple precision is supported in software. Lower precision arithmetic brings increased speed and reduced communication and energy costs, but it produces results of correspondingly low accuracy. Higher precisions are more expensive but can potentially provide great benefits, even if used sparingly. A variety of mixed precision algorithms have been developed that combine the superior performance of lower precisions with the better accuracy of higher precisions. Some of these algorithms aim to provide results of the same quality as algorithms running in a fixed precision but at a much lower cost; others use a little higher precision to improve the accuracy of an algorithm. This survey treats a broad range of mixed precision algorithms in numerical linear algebra, both direct and iterative, for problems including matrix multiplication, matrix factorization, linear systems, least squares, eigenvalue decomposition, and singular value decomposition. We identify key algorithmic ideas, such as iterative refinement, adapting the precision to the data, and exploiting mixed precision block fused multiply--add operations. We also describe the possible performance benefits and explain what is known about the numerical stability of the algorithms. This survey should be useful to a wide community of researchers and practitioners who wish to develop or benefit from mixed precision numerical linear algebra algorithms
The dynamical functional particle method for the generalized Sylvester equation
Full text linkRecent years have seen a renewal of interest in the study of generalized Sylvester equations, which have come to play a role in a number or applications. Here we consider the solution of such equations by means of the dynamical functional particle method, an iterative technique that relies on the construction and numerical integration of a damped second order dynamical system. We develop a new algorithm for the solution of a large class of these equations, a class that includes, among others, all generalized Sylvester equations with Hermitian positive definite coefficients. Our numerical experiments show that the new implementations outperform existing methods for the solution of generalized Sylvester equations, and can be faster and more accurate than the Bartels–Stewart algorithm for the solution of the Sylvester equation AX − XB = C, when A and B are well conditioned and have very different order
Stochastic Rounding: Implementation, Error Analysis, and Applications
Full text linkStochastic rounding randomly maps a real number to one of the two nearest values in a finite precision number system. First proposed for use in computer arithmetic in the 1950s, it is attracting renewed interest. If used in floating-point arithmetic in the computation of the inner product of two vectors of length n, it yields an error bounded by \sqrt(n)u with high probability, where u is the unit roundoff, which is not necessarily the case for round to nearest. A particular attraction of stochastic rounding is that, unlike round to nearest, it is immune to the phenomenon of stagnation, whereby a sequence of tiny updates to a relatively large quantity are lost. We survey stochastic rounding, covering its mathematical properties and probabilistic error analysis, its implementation, and its use in applications, including deep learning and the numerical solution of differential equations
Arbitrary Precision Algorithms for Computing the Matrix Cosine and its Fréchet Derivative
Full text linkExisting algorithms for computing the matrix cosine are tightly coupled to a specific precision of floating-point arithmetic for optimal efficiency so they do not conveniently extend to an arbitrary precision environment. We develop an algorithm for computing the matrix cosine that takes the unit roundoff of the working precision as input, and so works in an arbitrary precision. The algorithm employs a Taylor approximation with scaling and recovering and it can be used with a Schur decomposition or in a decomposition-free manner. We also derive a framework for computing the \fd, construct an efficient evaluation scheme for computing the cosine and its Fr\'echet derivative simultaneously in arbitrary precision, and show how this scheme can be extended to compute the matrix sine, cosine, and their \fd s all together. Numerical experiments show that the new algorithms behave in a forward stable way over a wide range of precisions. The transformation-free version of the algorithm for computing the cosine is competitive in accuracy with the state-of-the-art algorithms in double precision and surpasses existing alternatives in both speed and accuracy in working precisions higher than double
The dynamical functional particle method for multi-term linear matrix equations
Full text linkRecent years have seen a renewal of interest in multi-term linear matrix equations, as these have come to play a role in a number of important applications. Here, we consider the solution of such equations by means of the dynamical functional particle method, an iterative technique that relies on the numerical integration of a damped second order dynamical system. We develop a new algorithm for the solution of a large class of these equations, a class that includes, among others, all linear matrix equations with Hermitian positive or negative definite coefficients. In numerical experiments, our MATLAB implementation outperforms existing methods for the solution of generalized Sylvester equations. For the Sylvester equation AX + XB = C, in particular, it can be faster and more accurate than the built-in implementation of the Bartels-Stewart algorithm, when A and B are well conditioned and have very different size