Massimiliano Fasi awarded PhD

Congratulations to Massimiliano Fasi for being awarded his PhD, which was supervised by Nick Higham. We asked him a few questions about his thesis, title Computing Matrix Functions in Arbitrary Precision Arithmetic.

Please can you introduce yourself and tell us a bit about your experience before attending University of Manchester?
I was born in Assisi, a smallish town in central Italy chiefly known for having been home to Saint Francis. I thought I would become a philologist, and during my teen years I studied mostly linguistics and ancient languages, while taking plenty of courses at the local music conservatory. After much pondering, I decided to start my university career with a scientific discipline and I chose computer science. I found that I really enjoyed the subject, and after graduating from the University of Perugia I pursued a Master’s degree at the University of Bologna and, at the same time, one at the École Normale Supérieure of Lyon.

What is your thesis on?
My thesis investigates the computation of matrix functions in arbitrary precision arithmetic, and is in fact a collection of results that are somewhat connected to this topic. We started by revisiting several well-known techniques for two very general problems: the evaluation of rational functions at a matrix argument and the solution of rational matrix equations. We developed new numerical methods and provided some theoretical insights, and used these as building blocks to design multiprecision algorithms to evaluate matrix functions that are of interest in applications. We focused mainly on the matrix exponential and the matrix logarithm, but the machinery we developed is more general and can be used for a much broader range of problems.

Why did you choose to study your PhD in Manchester?
Numerical analysis was my favourite module as an undergraduate student. I decided to do an internship with the lecturer teaching that course, and the subject happened to be the matrix Lambert W function. I’ve been interested in matrix functions ever since, and when the time came to choose where to do a PhD, I thought that it would be great to join the strongest linear algebra group I was aware of. I was lucky enough to be admitted at The University of Manchester, where I could do research with Professor Nick Higham, who is a leading expert in this field.

How did you find Manchester?
Manchester is a lively city and is well connected to the rest of the world. The postgraduate community I was part of is very dynamic, and somewhat larger than I was used to. A PhD can be rather difficult at times, but the many people I had the chance to meet here made my Mancunian experience unforgettable.

What’s your next step?
My long-term plan is to remain in academia, and I will try to follow the path that leads to a permanent position. For the moment, I am a research associate in the group here in Manchester, and am trying my best to deepen my understanding of the current trends in numerical linear algebra.

IMG_8801.CR2

Massimiliano Fasi

 

 

Nick Higham awarded the LMS Naylor Prize and Lectureship

Professor Nick Higham has been awarded the London Mathematics Society’s Naylor Prize and Lectureship for his leadership in numerical linear algebra, numerical stability analysis, and communication of mathematics.

The Naylor Prize and Lectureship is awarded every two years in memory of Dr V. D. Naylor. The grounds for the award may include work in, and influence on, and contributions to applied mathematics and/or the applications of mathematics, and lecturing gifts.

The full prize citation is available here.

Higham, Nicholas FRS, 2015 DSC_3580 ed_cropped

Determinants of Bohemian matrix families

Density plots of eigenvalues of matrices from various Bohemian families. Collection of images by Steven Thornton. To find out more about these figures, or to create your own, check out the gallery at the Bohemian Matrices website.

The adjective “Bohemian” was used for the first time in a linear algebra context by Robert Corless and Steven Thornton to describe the eigenvalues of matrices whose entries are taken from a finite discrete set, usually of integers. The term is a partial acronym for “BOunded Height Matrix of Integers”, but the origin of the term was soon forgotten, and the expression “Bohemian matrix” is now widely accepted.

As Olga Taussky observed already in 1960, the study of matrices with integer elements is “very vast and very old”, with early work of Sylvester and Hadamard that dates back to the second half of the nineteenth century. These names are the first two in a long list of mathematicians that worked on what is now known as the “Hadamard conjecture”: for any positive integer n multiple of 4, there exists an n by n matrix H, with entries -1 and +1, such that HH^T = nI.

If this is the best-known open problem surrounding Bohemian matrices, it is far from being the only one. During the 3-day workshop “Bohemian Matrices and Applications” that our group hosted in June last year, Steven Thornton released the Characteristic Polynomial Database, which collects the determinants and characteristic polynomials of billions of samples from certain families of structured as well as unstructured Bohemian matrices. All the available data led Steven to formulate a number of conjectures regarding the determinants of several families of Bohemian upper Hessenberg matrices.

Gian Maria Negri Porzio and I attended the workshop, and set ourselves the task of solving at least one of these open problems. In our recent preprint, we enumerate all the possible determinants of Bohemian upper Hessenberg matrices with ones on the subdiagonal. We consider also the special case of families with main diagonal fixed to zero, whose determinants turn out to be related to some generalizations of Fibonacci numbers. Many of the conjectures stated in the Characteristic Polynomial Database follow from our results.

Highlights of Advances in Numerical Linear Algebra Conference

by Sven Hammarling, Nick Higham and Françoise Tisseur

The conference Advances in Numerical Linear Algebra: Celebrating the Centenary of the Birth of James H. Wilkinson, took place at the University of Manchester, May 29-30, 2019.  The purpose of the conference was to discuss recent developments and future challenges in numerical linear algebra and to celebrate the centenary of the birth of James H. Wilkinson FRS (1919-1986).

The 60 attendees heard reminiscences about Wilkinson and his work from several attendees who knew him.  Sven Hammarling opened the proceedings with personal reflections on Wilkinson. Margaret Wright discussed some of the treasures in lecture notes from courses that Wilkinson taught at Stanford University (1977-1982). We have recently added these notes to our Wilkinson web page. Nick Higham announced the availability of the Argonne tapes, which are videos of Wilkinson and Cleve Moler lecturing at an Eigensystem Workshop held at Argonne National Laboratory, Illinois, USA, in June 1973.

We were pleased to welcome two of Jim Wilkinson’s nephews, John Liebman and Danny Liebman, together with John’s wife Liz.

Attendees were able to wish speaker Cleve Moler a happy 80th birthday and share two birthday cakes with him.

Photos from the conference appear below. Click on a photo to enlarge it.

Slides of the talks are available at the conference web page. The first day’s lectures were professionally videoed and the videos are available on the NLA group’s YouTube channel: here is a link to the playlist.

Thank you to all the speakers and attendees for their participation.

We gratefully acknowledge sponsorship from the Royal Society, The Alan Turing Institute, The QJMAM Fund for Applied Mathematics, The Numerical Algorithm Group and National Physical Laboratory.

 

The Contribution of Dr. J. H. Wilkinson to Numerical Analysis

Wilkinson_033.jpg

President HRH Duke of Edinburgh presenting honorary fellowship of The Institute of Mathematics and its Applications to James Wilkinson in 1977 (© The IMA).

The title of this post is the same as that of a symposium organized by Michael J. D. Powell and the Institute of Mathematics and its Applications (IMA) at the Royal Society in London on July 6th, 1977. The meeting commemorated the election of James Hardy Wilkinson to an Honorary Fellowship of the IMA.

The proceedings of the meeting were published by the IMA in a 91-page A5 booklet. As far as I am aware, few copies of the booklet survive and its contents have not previously been made available online. I am grateful to David Youdan, Executive Director of the IMA, for giving me permission to provide here a scan of the booklet. It is timely to do so, because this year marks the 100th anniversary of the birth of Wilkinson.

Here are the individual chapters, with comments from Mike Powell’s preface in quotes.

  • About Jim Wilkinson, with a Commemorative Snippet on Backward Error Analysis, L. Fox (Oxford University Computing Laboratory). “Leslie Fox describes many of Jim Wilkinson’s achievements that have not been published before and he exposes the accuracy of some ill-conditioned least squares calculations.”
  • Inverse Iteration, Newton’s Method, and Non-linear Eigenvalue Problems, M. R. Osborne (Australian National University). “Mike Osborne unifies the convergence properties of a main class of iterative methods for calculating eigenvalues.”
  • A New Look at Error Analysis, C. W. Clenshaw (University of Lancaster). “Charles Clenshaw develops an idea, due to Frank Olver, for treating the accumulation of errors in floating point arithmetic.”
  • A Problem in Numerical Linear Algebra, J. H. Wilkinson (National Physical Laboratory). “Jim Wilkinson shows the relevance in practice of the equivalence of repeated matrix eigenvalues, the ill-conditioning of the matrix eigenvector calculation, and the orthogonality of left and right hand eigenvectors that have a common eigenvalue.”

For more information about Wilkinson, see this web page that Sven Hammarling and I have created.

ima78_cover.jpg

Our Alumni – Pythagoras Papadimitriou

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

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

I was born in Athens and grew up there.  I studied Mathematics (B.Sc.) at Athens University. Then I did my national service and I moved to Manchester in September 1990 to attend the M.Sc. course “Numerical Analysis & Computing” at Manchester University.

What was your PhD thesis on?

The title of my Ph.D. is “Parallel Solution of SVD-Related Problems, with Applications”. The main part of my research dealt with the development of parallel algorithms for computing the Singular Value Decomposition and the Polar Decomposition. The algorithms were designed for the particular architecture of the KSR1, which was a virtual shared-memory parallel computer, a leading-edge parallel computer technology of the 90s.

Why did you choose to study your PhD in Manchester?

My initial plan was to complete my M.Sc. and work in industry. But when Nick Higham asked me to do a Ph.D. with him with a scholarship from S.E.R.C. I did not think twice. I am very proud that Nick was my supervisor.

How did you find Manchester?

It was an invaluable experience, three wonderful years. I made good friends and I am still in touch with most of them. When I left Manchester in October 1993 I took only good memories with me, including some of the best moments in my life. They say that Manchester has changed and the city is more beautiful now. I hope my sons will have the opportunity to study in Manchester.

Can you tell us about your career since leaving Manchester?

I joined the IT industry as a software engineer a few days after the submission of my Ph.D. thesis in October 1993. My first employer was a start-up in Greece. I joined Intrasoft SA, the then largest Systems Integrator in southeast Europe, in 1995. At Intrasoft SA, I moved from SW Development to Project Management in 1997 and to Sales in 1999. I joined Nortel Networks in Athens in January 2001 as Sales Director for Greece and Cyprus. A dream came true in October 2005 when I joined Sun Microsystems, a company that I admired from my Manchester days when I used Sun Unix workstations for carrying out my research. I headed the SW Business Unit of Sun Microsystems for 5 years, being responsible for a huge geography, from Saint Petersburg to Cape Town and from Vienna to Vladivostok! In January 2011 I joined HP in Athens as Managing Director. I moved to Vienna in September 2014 to join Oracle as Senior Sales Director responsible for Central Eastern Europe, Russia, Turkey and Central Asia. Today my organisation is responsible for the Systems partners of Oracle in this region plus in Italy, France and Iberia.

What is your current role?

I head the Systems Alliance and Channel organisation of Oracle for Italy, France, Iberia, Central Eastern Europe, Russia, Turkey and Central Asia. We are responsible for driving with our channel partners (Value Added Distributors, Value Added Resellers, Systems Integrators and Independent Software Vendors) the hardware business of Oracle in this region.

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

« Older Entries