## Conference Celebrating the 70th Birthday of Jack Dongarra

by Sven Hammarling, Nick Higham, and Françoise Tisseur

Jack Dongarra

July 18, 2020 is the 70th birthday of Professor Jack Dongarra, who holds appointments at the University of Tennessee, Oak Ridge National Laboratory, and the University of Manchester.

Jack has made seminal contributions to algorithms for numerical linear algebra and the design and development of high performance mathematical software for machines ranging from workstations to the largest parallel computers. His recent honours include election as a Foreign Member of the Royal Society and receipt of the
SIAM/ACM Prize in Computational Science and Engineering (2019)and the IEEE Computer Society Computer Pioneer Award (2020).

To celebrate Jack’s birthday we are organizing a conference New Directions in Numerical Linear Algebra and High Performance Computing: Celebrating the 70th Birthday of Jack Dongarra at The University of Manchester, July 17, 2020.  Registration is now open and we welcome submission of posters.

## Sharper Probabilistic Backward Error Bounds

Most backward error bounds for numerical linear algebra algorithms are of the form $nu$, for a machine precision $u$ and a problem size $n$. The dependence on $n$ of these bounds is known to be pessimistic: together with Nick Higham, our recent probabilistic analysis [SIAM J. Sci. Comput., 41 (2019), pp. A2815–A2835], which assumes rounding errors to be independent random variables of mean zero, proves that $n$ can be replaced by a small multiple of $\sqrt{n}$ with high probability. However, even these smaller bounds can still be pessimistic, as the figure below illustrates.

The figure plots the backward error for summation (in single precision) of $n$ floating-point numbers randomly sampled from a uniform distribution. For numbers in the $[0,1]$ distribution, the bound $\sqrt{n}u$ is almost sharp and accurately predicts the error growth. However, for the $[-1,1]$ distribution, the error is much smaller, seemingly not growing with $n$. This strong dependence of the backward error on the data cannot be explained by the existing bounds, which do not depend on the values of the data.

In our recent preprint, we perform a new probabilistic analysis that combines a probabilistic model of the rounding errors with a second probabilistic model of the data. Our analysis reveals a strong dependence of the backward error on the mean of the data $\mu$: indeed, our new backward error bounds are proportional to $\mu\sqrt{n}u + u$. Therefore, for data with small or zero mean, these new bounds are much sharper as they bound the backward error by a small multiple of the machine precision independent of the problem size $n$.

Motivated by this observation, we also propose new algorithms that transform the data to have zero mean, so as to benefit from these more favorable bounds. We implement this idea for matrix multiplication and show that our new algorithm can produce significantly more accurate results than standard matrix multiplication.

## Numerical Algorithms for High-Performance Computational Science Issue of Phil Trans R Soc A

Professors Jack Dongarra and Nick Higham, together with Dr Laura Grigori (Inria Paris), have edited the issue Numerical Algorithms for High-Performance Computational Science of the journal Philosophical Transaction of The Royal Society A. The issue is now available online.

The issue contains papers from a Discussion meeting of the same title organized at the Royal Society in April 2019.  A report on that meeting, along with photos from it, is available here.  The content of the issue, with links to the papers, is as follows.

Numerical algorithms for high-performance computational science by Jack Dongarra, Laura Grigori and Nicholas J. Higham.

The future of computing beyond Moore’s Law by John Shalf.

Hierarchical algorithms on hierarchical architectures by D. E. Keyes , H. Ltaief and G. Turkiyyah.

Stochastic rounding and reduced-precision fixed-point arithmetic for solving neural ordinary differential equations by Michael Hopkins, Mantas Mikaitis, Dave R. Lester and Steve Furber.

Preparing sparse solvers for exascale computing by Hartwig Anzt, Erik Boman, Rob Falgout et al.

On the cost of iterative computations by Erin Carson and Zdeněk Strakoš.

Rethinking arithmetic for deep neural networks by G. A. Constantinides.

Machine learning and big scientific data by Tony Hey , Keith Butler, Sam Jackson and Jeyarajan Thiyagalingam.

Exascale applications: skin in the game by Francis Alexander, Ann Almgren, John Bell et al.

Big telescope, big data: towards exascale with the Square Kilometre Array by A. M. M. Scaife.

Optimal memory-aware backpropagation of deep join networks by Olivier Beaumont, Julien Herrmann, Guillaume Pallez (Aupy) and Alena Shilova.

A survey of algorithms for transforming molecular dynamics data into metadata for in situ analytics based on machine learning methods by Michela Taufer , Trilce Estrada and Travis Johnston.

The parallelism motifs of genomic data analysis by Katherine Yelick , Aydın Buluç, Muaaz Awan et al.

## Jack Dongarra Selected to Receive the 2020 IEEE Computer Society’s Computer Pioneer Award

Jack Dongarra

Professor Jack Dongarra, a member of the Manchester Numerical Linear Algebra Group who also holds appointments at the University of Tennessee  and Oak Ridge National Laboratory, has been named as recipient of the IEEE Computer Society’s 2020 Computer Pioneer Award.

The award is given for significant contributions to early concepts and developments in the electronic computer field that have clearly advanced the state-of-the-art in computing.  Dongarra is being recognized “for leadership in the area of high-performance mathematical software.”

Dongarra will receive his award at the Computer Society’s annual awards dinner and presentation to be held on Wednesday 27 May 2020 at the Hilton McLean Tysons Corner during the IEEE Computer Society Board of Governors meeting. The award consists of a silver medal and an invitation to speak at the award presentation.

## Poster Successes at SIAM UKIE 2020 Section Meeting

Group photo at SIAM UKIE 2020

Several members of the group attended the SIAM UKIE Section Meeting held at the University of Edinburgh on Friday January 10, 2020. Françoise Tisseur, President of the Section and one of the co-organizers, chaired the morning session.

PhD students Michael Connolly,  Xiaobo (Bob) Liu, Gian Maria Negri Porzio, and Research Associate Srikara Pranesh presented posters.

Congratulations to Sri and Michael, who won first and second best poster prizes, respectively:
a cheque for £75 to both and also a copy of the book /50 Visions of Mathematics/ to Sri.

Photo credit to Gian Maria Negri Porzio

## Issues with Rounding in the GCC Implementation of the ISO 18037:2008 Standard Fixed-Point Arithmetic

Embedded systems are based on low-power, low-performance processors and can be found in various medical devices, smart watches, various communication devices, cars, planes, mobile phones and many other places. These systems come in a hardware and software package optimized for specific computational tasks and most commonly have real-time constraints. As these systems usually have energy usage and cost constraints too, sophisticated numerical hardware that can process floating-point data is not included, but rather only integer arithmetic, which is simpler in terms of area and power of the processors.

ISO 18037:2008 is a standard for embedded C programming language support. It lays out various rules that C compilers should support to make embedded systems easier to program using a high-level language. One of the most important definitions in this standard is fixed-point arithmetic data types and operations. Support for fixed-point arithmetic is highly desirable, since if it is not provided integers with scaling factors have to be used, which makes code hard to maintain and debug and most commonly requires assembler level changes or completely new implementations for each different platform.

The GCC compiler provides some support of the fixed-point arithmetic defined in this standard for ARM processors. However, in my recent technical report (https://arxiv.org/abs/2001.01496) I demonstrated various numerical pitfalls that programmers of embedded systems based on ARM and using GCC can get into. The issues demonstrated include

• larger than half machine epsilon errors in rounding decimal constants to fixed-point data types,
• errors in conversions between different data types,
• incorrect pre-rounding of arguments of mixed-format arithmetic operations before the operation is performed, and
• lack of rounding of the outputs of arithmetic operations.

These findings can be used to improve the accuracy of various embedded numerical libraries that might be using this compiler. To demonstrate one of the issues, here is a piece of test code:

The multiplication operation is a mixed-format operation, since it multiplies an unsigned long fract argument with an accum argument, therefore it is subject to prerounding of the unsigned long fract argument as described in the report. Since the comparison step in the if () sees that the argument a is larger than zero and b larger than 1, the code is executed with a hope that c will not be set to zero. However, in the arithmetic operation, a is incorrectly pre-rounded to 0, which causes c = 0*b, an unexpected outcome and a bug that is hard to detect and fix.

## Numerical Linear Algebra Group Activities 2019

The Numerical Linear Algebra Group had a busy year in 2019. This post summarizes what we got up to. Publications are not included here, but many of them can be found on MIMS EPrints under the category Numerical Analysis; see also these news stories about our publications.

Marcus Webb joined the group in September 2019 as Lecturer in Applied Mathematics.

Some of the group at the 2019 SIAM Conference on Computational Science and Engineering.

## Software

We make our research codes available as open source, principally on GitHub; see the repositories of ConnollyFasiHighamLiuPraneshZounon.

We also put MATLAB software on MATLAB Central File Exchange and on our own web sites, e.g., the Rational Krylov Toolbox (RKToolbox).

## PhD Students

Massimiliano Fasi successfully defended his PhD Computing Matrix Functions in Arbitrary Precision Arithmetic in May 2019.

## Postdoctoral Research Associates (PDRAs)

Massimiliano Fasi joined us in April 2019 to work with Nick Higham on algorithms for high-performance numerical linear algebra.  He was a Visiting Fellow at the University of Pisa from November 2019 to January 2020.

Mantas Mikaitis joined us in October 2019 on a EPSRC Doctoral Prize Fellowship, having just completed his PhD in the School of Computer Science.

Pierre Blanchard left the group in May 2019 and is now a Numerical Software Engineer at Arm.

Maksims Abalenkovs and Theo Mary left the group in September 2019. Maksims is now a Research Software Engineer with the Science and Technology Facilities Council and Theo is a CNRS researcher at LIP6 in Paris.

## Grants

Stefan Güttel, Nick Higham and Françoise Tisseur were awarded a new 30-month KTP project with Arup.  See this news story.

## Conference and Workshop Organization

ANLA19 group photo

Vanni Noferini listening to a question from Cleve Moler at ANLA19.

## Visitors

Rob Corless from University of Western Ontario visited the group in November 2019.

## Recognition and Service

• Françoise Tisseur delivered the Olga Taussky-Todd Lecture and Nick Higham was an invited speaker at the International Congress on Industrial and Applied Mathematics (ICIAM) in Valencia, Spain, July 2019.
• Jack Dongarra received the SIAM/ACM Prize in Computational Science and Engineering at the SIAM Conference on Computational Science and Engineering (CSE19)
• Jack Dongarra was elected as a Foreign Member of the Royal Society.
• Françoise Tisseur was elected as SIAM UKIE Section President, 2019-20.
• Steven Elsworth obtained a SIAM Student Travel Award to attend the 2019 SIAM Conference on Computational Science and Engineering (CSE19) in Spokane, Washington.
• Nick Higham received the London Mathematics Society’s Naylor Prize and Lectureship.
• Nick Higham delivered the Feng Kang Distinguished Lecture at the Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, Beijing, in April 2019, and the LAA Lecture (formerly the Hans Schneider Lecture) in the Department of Mathematics, University of Wisconsin, Madison, December 2019.

## NLA Group Partnering with Arup on Next Generation Structural Engineering Software

Dr Stefan Güttel, Professor Nick Higham, and Professor Françoise Tisseur have been awarded a new 30-month project with Arup, a multidisciplinary engineering firm operating in all areas of built environment.

This Knowledge Transfer Partnership (KTP), funded by Arup and Innovate UK, aims to embed new matrix eigenvalue solvers into Arup’s next generation software for structural engineering simulation.

The Numerical Linear Algebra  (NLA) group team will be working with Dr Stephen Hendry and Dr Ramaseshan Kannan of Arup, along with a KTP Associate, for which the position is advertised here.

The project builds on a long history of collaboration between Arup and the NLA Group, which has  previously led to the development of “model stability analysis” in Arup’s flagship structural engineering simulation package, Oasys GSA (see the paper What is Your Structural Model Not Telling You?).

## Low Precision Floating-Point Formats: The Wild West of Computer Arithmetic

The November 2019 edition of SIAM News contains an article by Research Associate Srikara Pranesh about the growing importance of low precision floating-point arithmetic. Sri describes the opportunities provided by recent hardware and explains how new algorithms are being derived to exploit low precision arithmetic.  To read the article click the image below.

Also see Sri’s recent blog post Simulating Low Precision Floating-Point Arithmetics.

## Solving Block Low-Rank Linear Systems by LU Factorization is Numerically Stable

In many applications requiring the solution of a linear system $Ax=b$, the matrix $A$ possesses a block low-rank (BLR) property: most of its off-diagonal blocks are of low numerical rank and can therefore be well approximated by low-rank matrices. This property arises for example in the solution of discretized partial differential equations, because the numerical rank of a given off-diagonal block is closely related to the distance between the two subdomains associated with this block. BLR matrices have been exploited to significantly reduce the cost of solving $Ax=b$, in particular in the context of sparse direct solvers such as MUMPS, PaStiX, and STRUMPACK.

However, the impact of these low-rank approximations on the numerical stability of the solution in floating-point arithmetic has not been previously analyzed. The difficulty of such an analysis lies in the fact that, unlike for classical algorithms without low-rank approximations, there are two kinds of errors to analyze: floating-point errors (which depend on the unit roundoff $u$), and low-rank truncation errors (which depend on the the low-rank threshold $\varepsilon$, the parameter controlling the accuracy of the blockwise low-rank approximations). Moreover, the two kinds of error cannot easily be isolated in the analysis, because the BLR compression and factorization stages are often interlaced.

In our recent preprint, with Nick Higham, we present rounding error analysis for the solution of a linear system by LU factorization of BLR matrices. Assuming that a stable pivoting scheme is used, we prove backward stability: the relative backward error is bounded by a modest constant times $\varepsilon$, and does not depend on the unit roundoff $u$ as long as $u$ is safely smaller than $\varepsilon$. This is a very desirable theoretical guarantee that can now be given to the users, who can therefore control the numerical behavior of BLR solvers simply by setting $\varepsilon$ to the target accuracy. We illustrate this key result in the figure below, which shows a strong correlation between the backward error and the $\varepsilon$ threshold for 26 matrices from the SuiteSparse collection coming from a wide range of real-life applications.