Wilkinson Quotes

Wilkinson_021.jpg

by Sven Hammarling and Nick Higham

We collect here some quotes from the work of Jim Wilkinson. These reflect his unique perspective as a mathematician who was involved in designing and building one of the first digital computers and who subsequently developed and analyzed a variety of numerical algorithms

We have arranged the quotes under the following headings:

Program libraries | Floating-point arithmetic | Rounding error analysis | Conditioning | Backward error analysis | Polynomials | Interaction on Pilot ACE | Communication avoidance | Linear algebra on Pilot ACE

Program libraries

Since the programming is likely to be the main bottleneck in the use of an electronic computer we have given a good deal of thought to the preparation of standard routines of considerable generality for the more important processes involved in computation. By this means we hope to reduce the time taken to code up large-scale computing problems, by building them up, as it were, from prefabricated units. [W48, p. 286]

In spite of the self-contained nature of the linear algebra field, experience has shown that even here the preparation of a fully tested set of algorithms is a far greater task than had been anticipated. [W71a, p. v]

Floating-point arithmetic

At a time when the arithmetic provided on modern computers is often so disappointing, it is salutary to recall that the subroutines included provision for accumulating inner products in double-precision floating-point arithmetic and all rounding was immaculate! [W80, p. 105]

Rounding error analysis

The two main classes of rounding error analysis are not, as my audience might imagine, `backwards’ and `forwards’, but rather `one’s own’ and `other people’s’. One’s own is, of course, a model of lucidity; that of others serves only to obscure the essential simplicity of the matter in hand. [W85, p. 5]

In general, the statistical distribution of the rounding errors will reduce considerably the function of n occurring in the relative errors. We might expect in each case that this function should be replaced by something which is no bigger than its square root and is usually appreciably smaller. [W61, p. 38]

For me, then, the primary purpose of the rounding error analysis was insight. [W86, p. 197]

Conditioning

The system was mildly ill-conditioned, though we were not so free with such terms of abuse in those days, [W71, p. 144]

Backward error analysis

“You have been solving these damn problems better than I can pose them.” Sir Edward Bullard, Director NPL, in a remark to Wilkinson (mid 1950s) [W85, p. 11]

I first used backward error analysis in connection with simple programs for computing zeros of polynomials soon after the PILOT ACE came into use. [W85, p. 8]

There does seem to be some misunderstanding about the purpose of an a priori backward error analysis. All too often, too much attention is paid to the precise error bound that has been established. The main purpose of such an analysis is either to establish the essential numerical stability of an algorithm or to show why it is unstable and in doing so to expose what sort of change is necessary to make it stable. The precise error bound is not of great importance. [W74, p. 356]

The great stability of unitary transformations in numerical analysis springs from the fact that both the \ell_2-norm and the Frobenius norm are unitarily invariant. This means in practice that even when rounding errors are made, no substantial growth takes place in the norms of the successive transformed matrices. [W65, p. 77]

Although backward analysis is a perfectly straightforward concept there is strong evidence that a training in classical mathematics leaves one unprepared to adopt it. … I have even detected a note of moral disapproval in the attitude of many to its use and there is a tendency to seek a forward error analysis even when a backward error analysis has been spectacularly successful. [W85, p. 5]

Polynomials

The Fundamental Theorem of Algebra asserts that every polynomial equation over the complex field has a root. It is almost beneath the dignity of such a majestic theorem to mention that in fact it has precisely n roots. [W84, p. 21]

The cosy relationship that mathematicians enjoyed with polynomials suffered a severe setback in the early fifties when electronic computers came into general use. Speaking for myself I regard it as the most traumatic experience in my career as a numerical analyst. [W84, p. 3]

Interaction on Pilot ACE

Since the use of the punched-card equipment required the use of an operator, it encouraged user participation generally, and this was a distinctive feature of Pilot ACE operation. For example, various methods of accelerating the convergence of matrix iterative processes were left under the control of operators, and the skill with which these stratagems were used by young women with no more than high school mathematics qualifications was most impressive. Speaking for myself I gained a great deal of experience from user participation, and it was this that led to my own conversion to backward error analysis. [W80, p. 112]

Communication avoidance

Since all machines have stores of finite size often divided up into high speed and auxiliary sections, storage considerations often have a vitally important part to play. [W55, p. 188]

Linear algebra on Pilot ACE

An interesting feature of these codes is that they make a very intensive use of subroutines; the addition of two vectors, multiplication of a vector by a scalar, inner products, etc, are all coded in this way. [W80, p. 105]

From 1946–1948 a great deal of quite detailed coding was done.… The subroutines for floating-point arithmetic were … produced by Alway and myself in 1947 … They were almost certainly the earliest floating-point subroutines. [W80, pp. 104–105]

References

[W48]   J. H.Wilkinson, The Automatic Computing Engine at the National Physical Laboratory, Proc. Roy. Soc. London Ser. A 195, 285-286, 1948.

[W55]   J. H. Wilkinson, The use of iterative methods for finding the latent roots and vectors of matrices, Mathematical Tables and Other Aids to Computation 9, 184-191, 1955.

[W65]   J. H. Wilkinson, Error Analysis of Transformations Based on the Use of Matrices of the Form I-2ww^H, pages 77-101, in Louis Rall, ed., Error in Digital Computation, vol. 2, Wiley, 1965.

[W61]   J. H. Wilkinson. Error analysis of direct methods of matrix inversion. J. ACM, 8:281-330, 1961.

[W71]   J. H. Wilkinson. Some comments from a numerical analyst. J. ACM, 18:137–147, 1971. (The 1970 A. M. Turing lecture).

[W71a]   J. H. Wilkinson and C. Reinsch, eds, Linear Algebra, II, Springer, 1971.

[W74]   J. H. Wilkinson, Numerical linear algebra on digital computers, IMA Bull. 10, 354-356, 1974.

[W80]   J. H. Wilkinson, Turing’s work at the National Physical Laboratory and the construction of Pilot ACE, DEUCE, and ACE, pages 101-114, in N. Metropolis, J. Howlett and G.-C. Rota, eds, A History of Computing in the Twentieth Century: A Collection of Essays, Academic Press, 1980.

[W84]   James Wilkinson, The Perfidious Polynomial, in G. H. Golub, ed., Studies in Numerical Analysis, Mathematical Association of America, Washington, D.C., 24, pp 1-28, 1984.

[W85]   J. H. Wilkinson. The state of the art in error analysis. NAG Newsletter, 2/85:5–28, 1985. (Invited lecture for the NAG 1984 Annual General Meeting).

[W86]   J. H. Wilkinson, Error Analysis Revisited, IMA Bull. 22, 192-200, 1986

Françoise Tisseur elected as SIAM UKIE Section President

Professor Françoise Tisseur has been elected as the new SIAM United Kingdom and Republic of Ireland Section President (SIAM UKIE) for 2 years starting in May 2019.  She previously served as Vice President, 2013-2015.

In her candidate statement for the election, Françoise said “I would like to grow SIAM membership in our region. I will support the 14 SIAM student chapters, encourage the establishment of new ones, continue the recent SIAM-IMA cooperation and promote joint meetings between the two societies. I will work to ensure that the annual meeting is successful and has a suitably diverse program that includes industrial involvement.”

The SIAM UKIE Section was formed in 1996 by the Society for Industrial and Applied Mathematics (SIAM) with the aim of promoting and supporting applied and industrial mathematics in the UK and the Republic of Ireland.

IMG_8330.CR2

Françoise Tisseur

A Class of Fast and Accurate Summation Algorithms

Summing n numbers is a key computational task at the heart of many numerical algorithms. When performed in floating-point arithmetic, summation is subject to rounding errors: for a machine precision u, the error bound for the most basic summation algorithms, such as recursive summation, is proportional to nu.

Nowadays, with the growing interest in low floating-point precisions and ever increasing n in applications, such error bounds have become unacceptably large. While summation algorithms leading to smaller error bounds are known (compensated summation is an example), they are computationally expensive.

In our recent preprint, Pierre Blanchard, Nick Higham and I propose a class of fast and accurate summation algorithms called FABsum. We show that FABsum has an error bound of the form bu+O(u^2), where b is a block size, which is independent of n to first order. As illustrated by the figure below, which plots the measured error using single precision as a function of n, FABsum can deliver substantially more accurate results than recursive summation. Moreover, FABsum can be easily incorporated in high-performance numerical linear algebra kernels in order to boost accuracy with only a modest drop in performance, as we demonstrate in the paper with the PLASMA library.

Our Alumni – Ramaseshan Kannan

In this blog post, we asked one of our alumni, Ramaseshan Kannan, a few questions about his time with the Numerical Linear Algebra Group.

Ramaseshan Kannan SQ

Please can you introduce yourself and tell us a bit about your experience before attending University of Manchester?

I studied an Undergraduate and a Master’s in Civil and Structural Engineering at the Indian Institute of Technology in Chennai. Upon graduation I started working for Arup in India, developing finite element-based structural engineering software. In due course I became very interested in the “solver” stack of the code, which is the linear algebra layer. I asked if my employer would support my PhD in this area and, to my surprise, they agreed. However the funding I was being offered only covered a fraction of my tuition and expenses as I was a non-EU candidate. At this point the School of Maths and in particular my supervisors helped out and I was offered a school scholarship to do a collaborative PhD in the NLA group. That’s how I landed up in sunny Manchester.

What was your PhD thesis on?

I worked on a range of sparse linear algebra problems that originated in the software I was developing. The mainstay of my research was a new eigenvector clustering algorithm that allowed engineers to debug errors in their mathematical models. Other parts concerned the execution performance of matrix algorithms on parallel computers.

During the PhD I continued working for Arup as a technology translator implementing my own research back into commercial software. As a result I was able to see most parts of my PhD being used on real world problems, which was very satisfying.

Why did you choose to study your PhD in Manchester?

Having secured my employer’s funding we started scouting for research groups and centres of expertise around the world in the area of eigenvalue problems. Very soon it became clear that Manchester was a leader in both theory and numerical software so it was an obvious choice. In addition, my supervisors Nick Higham and Francoise Tisseur were open to making my rather bespoke arrangement work, all of which contributed to the decision.

How did you find Manchester?

I liked it so much that I haven’t left! I find it a great mix of practicality and opportunity. We have some of the best schools in the country. Plus we have the Peak District, the Lake District, and Yorkshire Dales all within a day-trip’s distance.

Can you tell us about your career since leaving Manchester?

After finishing my PhD I have continued to work for Arup in our Manchester office. Over the years I have been involved in a gamut of activities such as internal and external research including sponsored MSc and PhDs, writing numerical software, publishing and peer reviewing and consulting with engineers to understand their technical problems, to name a few.

What is your current role?

As above, I don multiple hats although my primary role is centred around developing numerical software with the eventual aim of making simulations faster, more accurate, or more productive for the end-user. I am also tasked with blue sky activities so, as an example, I’m looking at ways in which machine learning can be symbiotically used with traditional numerical analysis/engineering simulation to help engineers.

Jack Dongarra elected as Foreign Member of the Royal Society

Jack Dongarra


Professor Jack Dongarra

Jack Dongarra, Professor and Turing Fellow in the School of Mathematics and member of the Numerical Linear Algebra Group, has been elected as a Foreign Member of the Royal Society.  This honour recognizes his 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.

Dongarra’s software and libraries, which include LINPACK, EISPACK, LAPACK, the BLAS, MPI, ATLAS, PLASMA, MAGMA, and PAPI, are universally considered as standards, both in academia and industry. They excel in the accuracy of the underlying numerical algorithms and the reliability and performance of the software. They benefit a very wide range of users through their incorporation into software including MATLAB, Maple, Mathematica, Octave, R, SciPy, and vendor libraries.

The Royal Society is the oldest scientific academy in continuous existence, going back to 1663. Each year the Royal Society elects up to 52 new Fellows and up to 10 new Foreign Members. Fellows and Foreign Members are elected for life on the basis of excellence in science. Each candidate is considered on their merits and can be proposed from any sector of the scientific community.

The full list of the newly elected Fellows and Foreign Members of the Royal Society is available here.

Our Alumni – Sam Relton

In this blog post, we asked one of our alumni, Sam Relton, a few questions about his time with the Numerical Linear Algebra Group.

srelton.jpg

Please can you introduce yourself and tell us a bit about your experience before attending University of Manchester?

I was always pretty good at maths, because I liked understanding how things worked, and so I went to Manchester for my BSc. During that course I really enjoyed the numerical analysis and linear algebra modules because they underpin how all other mathematics is implemented in practice. I loved living in Manchester so I wanted to stick around, and I was lucky enough to be able to skip an MSc and go straight to a PhD in the NLA group.

What was your PhD thesis on?

My thesis was supervised by Nick Higham and called “Algorithms for Matrix Functions, their Frechet Derivatives, and Condition Numbers”. It consisted of four research papers covering theoretical and algorithmic advances in the computation of matrix functions, all woven together. Along with Nick, a few of these papers were co-authored with Awad Al-Mohy (a previous PhD student of Nick’s who was interested in similar problems).

Why did you choose to study your PhD in Manchester?

Manchester is a world-leading research group for numerical linear algebra and it was a privilege to learn from (and work with) the greatest researchers in the field. This also opens up a lot of opportunities in terms of attending conferences, visiting other institutions, and when looking for postdoctoral positions. Manchester is also a fantastic place to live, with plenty going on and a thriving community of PhD and post-doc researchers. I also had a few friends studying other courses that I shared a house with during my undergraduate degree and PhD.

How did you find Manchester?

I loved Manchester, it’s a large busy city full of interesting things to see and do whilst the cost of living is nowhere near that of London. Despite that, you can easily get into the countryside with a 30 minute drive! The maths department was brilliant with plenty of strong research groups to chat with, lots of seminars to attend, and a friendly and open atmosphere between all the staff and students.

Can you tell us about your career since leaving Manchester?

After doing a BSc, PhD, and 2 post-docs in high-performance computing at Manchester I decided to try something new. I now work in the School of Medicine at Leeds, applying complex statistical models and machine learning to electronic healthcare records (taken from GP and hospital databases) with collaborators in the School of Computing. Statistics and machine learning are really just a practical application of linear algebra / HPC, so much of what I learnt during my years in Manchester is still very relevant! Working with large interdisciplinary teams of doctors and nurses is an interesting change, and it’s nice to have direct impact on NHS policy decisions.

Version 4.0 of NLEVP Collection of Nonlinear Eigenvalue Problems

nlevpA new release, version 4.0, is available of the NLEVP MATLAB toolbox, which provides a collection of nonlinear eigenvalue problems. The toolbox has become a standard tool for testing algorithms for solving nonlinear eigenvalue problems.

When it was originally released in 2008, the toolbox contained 26 problems.  The new release contains 74 problems. It is now distributed via GitHub and is available at https://github.com/ftisseur/nlevp.

Further details are given in An Updated Set of Nonlinear Eigenvalue Problems. The collection will grow and contributions are welcome.

The following table shows the 22 new problems in version 4.0 of the toolbox .4.0 NLEVP problems

« Older Entries