Author Archives: Nick Higham

A New Approach to Probabilistic Rounding Error Analysis

by Nick Higham and Theo Mary

hima18_fig.jpg

Backward error for random linear system of dimension n.

James Wilkinson developed a systematic way of analyzing rounding errors in numerical algorithms in the 1960s—a time when computers typically used double precision arithmetic and a matrix of dimension n = 100 was considered large. As a result, an error bound with a dominant term p(n)u, for p a low degree polynomial and u the machine precision, was acceptably small.

Today, the supercomputers heading the TOP500 list solve linear systems of equations of dimension 10^8 and half precision arithmetic (accurate to about 4 significant decimal digits) is increasingly available in hardware, notably on graphical processing units (GPUs) from AMD and NVIDIA. Traditional rounding error bounds cannot guarantee accurate results when the dimension is very large or the precision is low. Yet computations are often successful in such cases—for example in machine learning algorithms making use of half, or even lower, precision.

This discrepancy between theory and practice stems from the fact that traditional rounding error bounds are worst-case bounds and so tend to be pessimistic. Indeed, while a single floating-point operation incurs a rounding error bounded in modulus by u, the composition of n operations leads to a worst-case error bound with dominant term proportional to nu. But this worst-case error bound is attained only when each rounding error is of maximal magnitude and identical sign, which is very unlikely. Since the beginning of the digital computer era many researchers have modelled rounding errors as random variables in an attempt to obtain better estimates of how the error behaves on average. This line of thinking has led to the well-known rule of thumb, based on informal arguments and assumptions, that constants in rounding error bounds can be replaced by their square roots.

In our EPrint A New Approach to Probabilistic Rounding Error Analysis we make minimal probabilistic assumptions on the rounding errors and make use of a tool from probability theory called a concentration inequality. We show that in several core linear algebra algorithms, including matrix-vector products and LU factorization, the backward error can be bounded with high probability by a relaxed constant proportional to \sqrt{n\log n}u instead of nu. Our analysis provides the first rigorous justification of the rule of thumb.

This new bound is illustrated in the figure above, where we consider the solution of a linear system Ax = b by LU factorization. The matrix A and vector x have entries from the random uniform [0,1] distribution and b is formed as Ax. We compare the backward error with its traditional worst-case bound and our relaxed probabilistic bound. The figure shows that the probabilistic bound is in very good agreement with the actual backward error and is much smaller than the traditional bound. Moreover, it successfully captures the asymptotic behavior of the error growth, which follows \sqrt{n} rather than n.

The assumptions underlying our analysis—that the rounding errors are independent random variables of mean zero—do not always hold, as we illustrate with examples in the paper. Nevertheless, our experiments show that the bounds do correctly predict the backward error for a selection of real-life matrices from the SuiteSparse collection.

Fast Solution of Linear Systems via GPU Tensor Cores’ FP16 Arithmetic and Iterative Refinement

181112_sc18.jpg

NVIDIA Founder & CEO Jensen Huang talking about the work reported here in his special address at Supercomputing 2018 (8:30 onwards).

Over the last 30 years, hierarchical computer memories, multicore processors and graphical processing units (GPUs) have all necessitated the redesign of numerical linear algebra algorithms, and in doing so have led to algorithmic innovations. Mixed precision arithmetic—a concept going back to the earliest computers, which had the ability to accumulate inner products in extra precision—attracted renewed interest in the late 1990s once Intel chips were able to execute single precision at twice the rate of double precision. Now the increasing availability of low precision arithmetic is offering new opportunities.

In the paper Harnessing GPU Tensor Cores for Fast FP16 Arithmetic to Speed up Mixed-Precision Iterative Refinement Solvers presented at SC18 (the leading supercomputing conference), Azzam Haidar, Stanimire Tomov, Jack Dongarra and Nick Higham show how to exploit the half precision (fp16) arithmetic that is now available in hardware. Whereas fp16 arithmetic can be expected to run at twice the rate of fp32 (single precision) arithmetic, the NVIDIA V100 GPU has tensor cores that can execute half precision at up to eight times the speed of single precision and can deliver the results to single precision accuracy. Developing algorithms that can exploit half precision arithmetic is important both for a workstation connected to a single V100 GPU and the world’s fastest computer (as of November 2018): Summit at Oak Ridge National Laboratory, which contains 27,648 V100 GPUs.

The paper shows that a dense n-by-n double precision linear system Ax = b can be solved using mixed precision iterative refinement at a rate up to four times faster than a highly optimized double precision solver and with a reduction in energy consumption by a factor five.

The key idea is to LU factorize the matrix A in a mix of half precision and single precision then apply iterative refinement. The update equations in the refinement process are solved by an inner GMRES iteration that uses the LU factors as preconditioners. This GMRES-IR algorithm was proposed by Carson and Higham in two (open access) papers in SIAM J. Sci. Comput. (2017 and 2018). In the form used here, the algorithm converges for matrices with condition numbers up to about 10^8. It provides a backward stable, double precision solution while carrying out almost all the flops at lower precision.

Codes implementing this work will be released through the open-source MAGMA library.

htdh18_fig7a.jpg

Lecturer, Senior Lecturer or Reader in Applied Mathematics

The School of Mathematics is seeking mathematical scientists of outstanding ability or potential for appointments at Lecturer, Senior Lecturer or Reader level.

Applicants working in any area of applied mathematics are welcome, particularly those working in areas that complement and enhance the applied mathematics research of the School, which spans numerical linear algebra, uncertainty quantification, dynamical systems, data science, mathematics in the life sciences, industrial mathematics, inverse problems and continuum mechanics.

Applicants with research experience in numerical linear algebra, or at the interfaces with pure mathematics or probability and statistics, are strongly encouraged.

These positions provide an excellent opportunity to join the Numerical Linear Algebra Group.

The closing date is January 11, 2019. For the advert and more details see here.

Welcome to the NLA Group Website

Welcome to the new website of the Numerical Linear Algebra group at the University of Manchester! The group, numbering around 20 and listed here, comprises four permanent faculty—Nick Higham, Françoise Tisseur, Stefan Guettel and Jack Dongarra (part-time)—and PhD students, research associates, research fellows, visitors and other associated researchers.

The website reports our activities, including papers, software and presentations. It contains regularly updated news items as well as blog posts by members of the group on research topics of interest.

We hold weekly group meetings and organize workshops in Manchester and elsewhere. Some of our conference talks are available here.

We give a number of courses in the School of Mathematics in the undergraduate mathematics degree and at M.Sc. level, and also regularly give courses externally, especially at summer schools.

We are always looking to recruit, and current opportunities are listed here. Feel free to contact us if you would like to enquire about future opportunities.

Follow us on Twitter and watch the videos on our YouTube channel.

Primary Solutions of Matrix Equations

Max Fasi and Bruno Iannazzo have shown how to compute all primary solutions of a matrix equation f(X) = A for rational functions f. A primary solution is one that can be written as a polynomial in A. The proposed algorithm exploits the Schur decomposition and generalizes earlier algorithms for matrix roots.

Fasi and Iannazzo’s paper Computing Primary Solutions of Equations Involving Primary Matrix Functions appears in Linear Algebra Appl. 560, 17-42, 2019.

faia18_fig1.jpg