Nick Higham Awarded the SIAM George Pólya Prize for Mathematical Exposition

The Society for Industrial and Applied Mathematics (SIAM) has chosen Nick Higham, Royal Society Research Professor and Richardson Professor of Applied Mathematics, as the 2021 recipient of the George Pólya Prize for Mathematical Exposition.

The prize, which is awarded for expository work that communicates mathematics effectively, is named after George Pólya, the Hungarian mathematician who wrote the million-selling book How to Solve It, first published in 1945.

“Pólya was a brilliant researcher, teacher, and expositor of mathematics,” said Higham. “It is an honor to receive this SIAM prize named after him, especially as most of my research and expository writing has been published with SIAM.”

Higham was cited for “the crisp clarity, elegance and accessibility of his mathematical and popular exposition on a broad range of topics in applied mathematics.”

The award ceremony will be held at the 2021 SIAM Annual Meeting, scheduled to be held in a virtual format during July 19-23, 2021.

Professor Nicholas J. Higham, University of Manchester. Photo: Rob Whitrow

The BLAS named as one of the “Ten Codes that Transformed Science”

By Sven Hammarling.

An article in a recent issue of the journal Nature has the title “Ten Codes that Transformed Science”.

Two of the codes are purely numerical, namely the fast Fourier transform (FFT) and the Basic Linear Algebra Subprograms (BLAS). The BLAS evolved in three stages, the Level 1 BLAS2 for scalar and vector operations, the Level 2 BLAS3 for matrix-vector operations and the Level 3 BLAS4 for matrix-matrix operations. The first draft proposal for the Level 1 BLAS appeared in the ACM Signum Newsletter in 1973, so the project as a whole spanned about seventeen years.

Two members of the Numerical Linear Algebra Group were directly involved in the development of the BLAS. Jack Dongarra wrote a number of the Level 1 BLAS routines, was involved in testing the routines on an IBM 370/195 and provided several efficient implementations of the routines, all of which was acknowledged in the published paper. Both Jack Dongarra and Sven Hammarling were authors of the Level 2 and 3 BLAS, together with Jeremy Du Croz and Richard Hanson for the Level 2 BLAS, and Jeremy Du Croz and Iain Duff for the Level 3 BLAS.

To take two quotes by Jack Dongarra from the Nature article:

“In effect, BLAS reduced matrix and vector mathematics to a basic unit of computation as fundamental as addition and subtraction … It provides the fabric on which we do computing.”

As well as providing a standard interface, it was hoped that computer manufacturers would provide optimised implementations and that hope has certainly been realised.

It should be said that the BLAS were very much a community project, with input from many people. The BLAS, especially the Level 3 BLAS, provided the basic high performance operations, particularly for the block partitioned methods, used by the LAPACK5 project, which started in 1987, before the actual publication of the Level 3 BLAS.

More recently, driven by modern parallel machines and the desire to solve larger and larger problems, a standard for Batched BLAS (BBLAS) operations has been proposed and has been accepted for publication by ACM ToMS6. The development of the BBLAS was done by the Numerical Linear Algebra Group as part of an EU project, NLAFET7, in collaboration with Jack Dongarra’s Innovative Computing Laboratory at the University of Tennessee.

1J. M. Perkel. Ten Codes that Transformed Science. Nature, 589:344–349, January 2021.
2C. L. Lawson, R. J. Hanson, D. Kincaid, and F. T. Krogh. Basic Linear Algebra Subprograms for FORTRAN usage. ACM Trans. Math. Software, 5:308–323, 1979.
3J. J. Dongarra, J. Du Croz, S. Hammarling, and R. J. Hanson. An extended set of FORTRAN Basic Linear Algebra Subprograms. ACM Trans. Math. Software, 14:1–32, 399, 1988.
4J. J. Dongarra, J. Du Croz, I. S. Duff, and S. Hammarling. A set of Level 3 Basic Linear Algebra Subprograms. ACM Trans. Math. Software, 16:1–28, 1990.
5E. Anderson, Z. Bai, C. H. Bischof, S. Blackford, J. Demmel, J. J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. C. Sorensen. LAPACK Users’ Guide. SIAM, Philadelphia, PA, USA, 3rd edition, 1999. ISBN 0-89871-447-8. (http://www.netlib.org/lapack/lug/).
6A Set of Batched Basic Linear Algebra Suprograms, ACM Trans. Math. Software. To appear.
7Deliverable D7.6, (https://www.nlafet.eu/public-deliverables/).

 

 

SIAM CSE21 MINISYMPOSIUM ON “Mixed Precision Algorithms for High Performance Scientific Computing”

The biannual SIAM Conference on Computational Science and Engineering (CSE) was conducted virtually between March 1 to 5, 2021. Theo Mary and I organised a two-part minisymposium on recent algorithmic and software advances of mixed precision methods in scientific computing. Below are the links to the slides of the talk.

Minisymposium description: The increasing support of lower precision arithmetics in hardware, such as fp16 and bfloat16, provides new opportunities for high performance scientific computing. However, even though low precision arithmetics can provide significant speed, communication, and energy benefits, their use in scientific computing poses the challenge of preserving the accuracy and stability of the computation. To address this issue, a variety of mixed precision algorithms that combine low and high precisions have emerged.

Nick Higham Named 2020 ACM Fellow

Professor Nick Higham has been named among the 2020 Association for Computing Machinery (ACM) Fellows, who are recognised for work underpinning contemporary computing.

The accomplishments of the 2020 ACM Fellows have driven innovations that have ushered in significant improvements across many areas of technology, industry, and personal life.

Nick has been recognised for his contributions to numerical linear algebra, numerical stability analysis, and communication of mathematics.

He is among 95 ACM Fellows, representing universities, corporations and research centres around the world, who are celebrated for their wide-ranging and fundamental contributions in areas including artificial intelligence, cloud computing, computer graphics, virtual reality, and more.

The ACM Fellows programme recognises the top 1% of ACM members for their outstanding accomplishments in computing and information technology and/or outstanding service to ACM and the larger computing community. Fellows are nominated by their peers, with nominations reviewed by a distinguished selection committee.

ACM President Gabriele Kotsis said: “The 2020 ACM Fellows have demonstrated excellence across many disciplines of computing. These men and women have made pivotal contributions to technologies that are transforming whole industries, as well as our personal lives. We fully expect that these new ACM Fellows will continue in the vanguard in their respective fields.”

Professor Nicholas J. Higham, University of Manchester

Numerical Linear Algebra Group Activities 2020

The Numerical Linear Algebra Group had a productive year in 2020, despite working remotely from March onwards because of the pandemic. 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.

200305-1133-38_cropped

Craig Lucas, Nick Higham, Xinye Chen, Steven Elsworth, Xiaobo Liu, Michael Connolly, Mantas Mikaitis, Len Freeman, Massimiliano Fasi, Pierre Blanchard, Sven Hammarling, Asad Raza Aitor Mehasi Mehasi, Stephanie Lai, Gian Maria Negri Porzio, Thomas McSweeney, Mawussi Zounon, Françoise Tisseur, Srikara Pranesh, Yuqing Zhang, Eleni Vlachopoulou, March 2020.

Software

We make our research codes available as open source, principally on GitHub; see the repositories of ConnollyFasiHighamLiuPranesh, Tisseur, and Zounon.

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

We welcomed new PhD students Xinye Chen and Thomas Seleiro.

Steven Elsworth successfully defended his PhD thesis Rational Krylov Methods and Machine Learning Approaches to Time Series Forecasting in March 2020 .

Michael Connolly took an internship with MathWorks from July to September 2020.

Postdoctoral Research Associates (PDRAs)

Mantas Mikaitis, previously an EPSRC Doctoral Prize Fellow in the group, is now working on the ICONIC project in the group.   During the year he successfully defended his PhD thesis Arithmetic Accelerators for a Digital Neuromorphic Processor in the Department of Computer Science.

Massimiliano Fasi left the group in September 2020 and is now working at Örebro University in Sweden.

Roberto Cahuantzi  was a member of the group from March to September 2020, working with Stefan Güttel.

Recognition and Service

Jack Dongarra received the 2020 IEEE Computer Society’s Computer Pioneer Award.

Srikara Pranesh and Michael Connolly won first and second best poster prizes, respectively, at the SIAM UKIE Section Meeting, Edinburgh, January 2020.

Françoise Tisseur received the London Mathematics Society’s Fröhlich Prize.

Theo Mary received an honourable mention for the 2020 Householder Prize and the 2021 SIAG/LA Early Career Prize. He also received a grant from the Faculty of Engineering Sciences of Sorbonne University for a project on”Mixed precision algorithms for HPC”.

Sixteen publications by members of the NLA group feature among the top 40 most read articles in two SIAM journals, both leading venues for publications in numerical linear algebra.

Stefan  Güttel was awarded the 2021 James H. Wilkinson Prize in Numerical Analysis and Scientific Computing.

Nick Higham received the IMA Gold Medal 2020.

Theo Mary has been awarded the 2021 SIAG/LA Early Career Prize by the SIAM Activity Group on Linear Algebra.

Grants

Stefan Güttel’s and Nick Higham’s Alan Turing Fellowships have been extended by one year to September 2021.

Stefan Güttel received a Small Project Grant from the Alan Turing Institute.

Nick Higham and Françoise Tisseur received funding for work on multi-precision algorithms from Lawrence Livermore National Laboratory under the Exascale Computing Project.

Nick Higham and Françoise Tisseur received funding from The MathWorks, Inc. to support a PhD student to work on exploiting multiprecision arithmetic.

Massimiliano Fasi is one of the participants of the 2020 INdAM-GNCS project “Low-rank methods for linear algebra problems with data-sparse structure” funded by the Scientific Computing Group of the Istituto Nazionale di Alta Matematica “Francesco Severi”.

External Presentations

SIAM UKIE Annual Meeting 2020, Edinburgh, January 10: Connolly, Liu, Negri Porzio, Pranesh, Higham, Pranesh and Tisseur.
SIAM Conference on Parallel Processing for Scientific Computing (PP20) in Seattle, Washington, US, February 12 – 15: Fasi, Mary, Mikaitis, Pranesh and Zounon.
Theo Mary, Performance and Accuracy of Mixed-Precision Matrix Factorizations, SIAM PP20, February, 2020.
Srikara Pranesh, Point Arithmetic for the Solution of Linear System of Equations, SIAM PP20, February, 2020.
Mawussi Zounon, Opportunities for Multi Precision Computation in Memory Bound Applications, SIAM PP20, February, 2020.
Nick Higham, Are Numerical Linear Algebra Algorithms Accurate at Extreme Scale and at Low Precisions?, in E-NLA Online seminar series on Numerical Linear Algebra, April 29, 2020.
Nick Higham, Random Orthogonal Matrices in High Performance Computing, Masked Guest Speaker, King Abdullah University of Science and Technology, 2020.
Nick Higham, The Anatomy of the World’s Fastest Linear Equation Solver, Online Distinguished Lecture, The Hong Kong Polytechnic University, September 2020.
Theo Mary, Mixed Precision Low Rank Compression of Data Sparse Matrices, Communications in NLA, online, September 2020.
Nick Higham, Rehabilitating Correlations, Leicester Actuarial Science Society and Students Union Mathematical Society, 2020.
Theo Mary, Mixed precision arithmetic: hardware, algorithms and analysis, London Mathematical Society Virtual Graduate Student Meeting, November, 2020.
Nick Higham, Mathematics of today’s floating-point arithmetic, London Mathematical Society Naylor Lecture, November 20, 2020.
Françoise Tisseur, Towards Reliable Eigensolvers for Nonlinear Eigenvalue Problems, in E-NLA Online seminar series on Numerical Linear Algebra, November 25, 2020.

Other Notable Tweets

Theo Mary Awarded the 2021 SIAG/LA Early Career Prize

Dr Theo Mary, a CNRS researcher at Sorbonne University (Paris) and a former postdoctoral researcher in the Numerical Linear Algebra Group (2018-2019), has been awarded the SIAG/LA Early Career Prize by the SIAM Activity Group on Linear Algebra.

The SIAM Activity Group on Linear Algebra (SIAG/LA) awards the SIAG/LA Early Career Prize every three years to one post-PhD early career researcher in the field of applicable linear algebra for outstanding contributions to the field within six years of receiving the PhD or equivalent degree as of January 1 of the award year. The selection committee wishes to recognize Theo for his “significant contributions to linear algebra topics, including block low rank methods, software development, probabilistic rounding error analysis, mixed precision arithmetic, and backward error analysis.”

The prize will be awarded at the 2021 SIAM Conference on Applied Linear Algebra (LA21), to be held on a virtual platform May 17-21, 2021.

Nick Higham Awarded the IMA Gold Medal 2020

Professor Nick Higham has been awarded the IMA Gold Medal 2020 by the Institute of Mathematics and its Applications. Institute Gold Medals are awarded every two years in recognition of outstanding contributions to mathematics and its applications.

This is the second such success for a member of the Department of Mathematics: Professor Fritz Ursell won the IMA Gold Medal 1994.

The full prize citation is available here.

O62A9943.jpg

Professor Nicholas J. Higham, University of Manchester

Read more

Stefan Güttel awarded the 2021 SIAM James H. Wilkinson Prize

Dr Stefan Güttel will receive the 2021 James H. Wilkinson Prize in Numerical Analysis and Scientific Computing. This prestigious prize, established in 1979, is awarded every four years by the Society for Industrial and Applied Mathematics (SIAM). SIAM is the world’s largest professional association devoted to applied mathematics with over 14,000 individual members.
 
Dr Güttel’s research is in computational mathematics, and in particular, in efficient numerical algorithms for high-dimensional problems. The prize recognizes his contributions to the analysis, implementation, and application of rational and block Krylov methods. These methods have recently become very popular for the efficient solution of large eigenvalue problems, matrix equations, and in model order reduction.
 
Dr Güttel’s work is applicable to a wide range of problems in science and engineering. He maintains active collaborations with other Departments and companies such as Arup, Autotrader, AspenTech, N Brown Group, and Schlumberger-Doll Research. He also holds a fellowship with the Alan Turing Institute, the UK’s national institute for data science and artificial intelligence.
 
Dr Güttel will deliver a prize lecture at the 2021 SIAM Conference on Computational Science and Engineering (CSE21), to be held on a virtual platform in March 2021.
 
guettel

NLA Group Articles Amongst Most Read In SIAM Journals

simax-siscSixteen publications by members of the NLA group feature among the top 40 most read articles in two SIAM journals, both leading venues for publications in numerical linear algebra. 

The following articles are amongst the 20 most read in the SIAM Journal on Matrix Analysis and Applications:

The following articles are amongst the 20 most read in the SIAM Journal on Scientific Computing:

The full lists (updated daily) are available here and here

CPFloat: A C library for emulating low-precision arithmetic

Detail of a replica of the mechanical computer Z1 on display at the German Museum of Techonolgy in Berlin. This machine, developed by Konrad Zuse between 1936 and 1938, could perform floating-point computations using a 24-bit representation. “Mechanischer Computer Z1, Nachbildung” by Stiftung Deutsches Technikmuseum Berlin is licensed under CC BY 4.0.

Computing machines with floating-point capabilities started appearing in the late 1940s, and despite being regarded as an optional feature for decades to come, floating-point hardware equipped a number of the mainframe computers produced in the 1960s and 1970s. At the time, there was no consensus on what features a number system ought to have, and the arithmetics implemented by any two vendors could differ widely in terms of word sizes, floating-point representations, rounding behaviour, and accuracy of the operations implemented in hardware. This lack of standardization was a major hindrance to the portability of the source code, as it made it significantly harder to write and maintain architecture-independent code.

The way out of this predicament was the establishment of the IEEE 754-1985 standard, which dictated word sizes, representations, and accuracy requirements for two default floating-point formats: single and double precision. For about three decades, hardware vendors conformed with the standard, and the large majority of general-purpose processing units came equipped with IEEE-compliant arithmetic units. Motivated by the low-precision requirements of machine learning applications, however, in recent years hardware manufacturers have started exploring the realm of low-precision arithmetics, commercialising a variety of highly optimised hardware units that pursue efficiency at the expense of accuracy. The high-performance computing community has attempted to channel the extreme performance of this hardware and utilise it in more traditional scientific computing applications, where more stringent accuracy needs typically require the use of higher precision.

The broad range of different formats available poses a serious challenge to those trying to develop mixed-precision algorithms, since studying the numerical behaviour of an algorithm in different working precisions may require access to a number of high-end hardware platforms, including supercomputer-grade CPUs and GPUs. In order to alleviate the problem, several software packages for simulating low-precision floating-point arithmetics in software have been developed. Some of these are described in the table below. All these solutions execute each arithmetic operation in hardware, and use the software layer only to round the results to the desired number of significant bits of precision.

Available software packages for simulating low-precision floating-pointarithmetic. The first three columns reports the name of the package, the main pro-gramming language in which the software is written, and what storage formats are supported. The following three columns describe the parameters of the target formats: whether the number of bits of precision in the significand is arbitrary (A) or limited to the number of bits in the significand of the storage format (R); whether the exponentrange can be arbitrary (A), must be the same as the storage format (R), or a sub-range thereof (S); whether the target format supports subnormal numbers (S), does not support them (N), supports them only for builtin types (P), or supports them but allows the user to switch the functionality off (F). The following column lists the floating-point formats that are built into the system. The last five columns indicate whetherthe software supports round-to-nearest wih ties-to-even (RNE), ties-to-zero (RNZ),or ties-to-away (RNA), the three directed rounding modes of the IEEE 754 standardround-toward-zero (RZ), round-to-+∞ and round-to-−∞ (RUD), round-to-odd (RO), and the two variants of stochastic rounding discussed in Section 3 (SR). The abbreviations bf16, tf32, fp16, fp32, and fp64 denote the formats bfloat16, TensorFloat-32, binary16, binary32, and binary64, respectively.

If the hardware and the software-simulated floating-point format are both IEEE compliant, rounding requires only standard mathematical library functions, but a straightforward implementation of the rounding formulae may potentially cause two kinds of issues. From a theoretical point of view, handling subnormals, underflow, and overflow demands special attention, and numerical errors can cause mathematically correct formulae to behave incorrectly when evaluated in finite arithmetic. In terms of performance, on the other hand, the algorithms obtained in this way are not necessarily efficient, as they build upon library functions that, being designed to handle a broad range of cases, might not be optimised for the specific needs of floating-point rounding functions.

In MATLAB, low-precision arithmetics can be simulated using the chop function, developed by Higham and Pranesh and discussed in a previous post. Mantas Mikaitis and I decided to port the functionalities of this MATLAB implementation to a lower level language, in order to obtain better performance. The scope of the project has progressively broadened, and we have recently released the first version of CPFloat, an open-source C library that offers a wide range of routines for rounding arrays of binary32 or binary64 numbers to lower precision. Our code exploits the bit-level representation of the underlying floating-point formats, and performs only low-level bit manipulation and integer arithmetic without relying on costly library calls.

The project is hosted in a GitHub repository where, along with the C code, we provide a MEX interface for MATLAB and Octave which is fully compatible with the chop function. The algorithms that underlie our implementation, as well as the design choices and the testing infrastructure of CPFloat are discussed in detail in a recent EPrint. In the numerical experiments shown there, CPFloat brings a considerable speedup (typically one order of magnitude or more) over existing alternatives in C, C++, and MATLAB. To the best of our knowledge, our library is currently the most efficient and complete software for experimenting with custom low-precision floating-point arithmetic available in any language.

Related articles


« Older Entries