Tricks and Tips in Numerical Computing

In a keynote talk at JuliaCon 2018 I described a variety of tricks, tips and techniques that I’ve found useful in my work in numerical computing.

The first part of the talk was about two aspects of complex arithmetic: the complex step method for approximating derivatives, and understanding multivalued functions with the help of the unwinding number. Then I talked about the role of the associativity of matrix multiplication, which turns out to be the key property that makes the Sherman-Morrison formula work (this formula gives the inverse of a matrix after a rank 1 update). I pointed out the role of associativity in backpropagation in neural networks and deep learning.

After giving an example of using randomization to avoid pathological cases, I discussed why low precision (specifically half precision) arithmetic is of growing interest and identified some issues that need to be overcome in order to make the best use of it.

Almost every talk at JuliaCon was livecast on YouTube, and these talks are available to watch on the Julia Language channel. The slides for my talk are available here.

Also at the conference, my PhD student Weijian Zhang spoke about the work he has been doing on evolving graphs in his PhD.

Lectures on Multiprecision Algorithms in Kácov

At the end of May, I was one of four lecturers at the ESSAM school on Mathematical Modelling, Numerical Analysis and Scientific Computing, held in Kácov, about a hour’s drive south-east of Prague in the Czech Republic.

The event was superbly organized by Josef Malek, Miroslav Rozlozník, Zdenek Strakos and Miroslav Tuma. This was a relaxed and friendly event, and the excellent weather enabled most meals to be taken on the terrace of the family-run Sporthotel Kácov in which we were staying.

Françoise Tisseur lecturing on the nonlinear eigenvalue problem.

I gave three lectures of about one hour each on Multiprecision Algorithms. The slides are available from this link. Here is an abstract for the lectures:

Today’s computing environments offer multiple precisions of floating-point arithmetic, ranging from quarter precision (8 bits) and half precision (16 bits) to double precision (64 bits) and even quadruple precision (128 bits, available only in software), as well as arbitrary precision arithmetic (again in software). Exploiting the available precisions is essential in order to reduce the time to solution, minimize energy consumption, and (when necessary) solve ill-conditioned problems accurately.

In this course we will describe the precision landscape, explain how we can exploit different precisions in numerical linear algebra, and discuss how to analyze the accuracy and stability of multiprecision algorithms.

Lecture 1. IEEE standard arithmetic and availability in hardware and software. Motivation for low precision from applications, including machine learning. Exploiting reduced communication cost of low precision. Issued relating to rounding error analyses in low precision. Simulating low precision for testing purposes. Challenges of implementing algorithms in low precision.

Lecture 2. Basics of rounding error analysis, illustrated with summation. Why increasing precision is not a panacea. Software for high precision and its cost. Case study: the matrix logarithm in high precision.

Lecture 3. Solving very linear systems (possibly very ill conditioned and/or sparse) using mixed precision: iterative refinement in three precisions. A hybrid direct-iterative method: GMRES-IR.

I gave an earlier version of these lectures in March 2018 at the EU Regional School held at the Aachen Institute for Advanced Study in Computational Engineering Science (AICES), Germany. This single two and a half hour lecture was recorded and can be viewed on YouTube. The slides are available here.

Conference in Honour of Walter Gautschi

Last week I had the pleasure of attending and speaking at the Conference on Scientific Computing and Approximation (March 30-31, 2018) at Purdue University, held in honour of Walter Gautschi (Professor Emeritus of Computer Science and Mathematics at Purdue University) on the occasion of his 90th birthday.

The conference was expertly organized by Alex Pothen and Jie Shen. The attendees, numbering around 70, included many of Walter’s friends and colleagues.

The speakers made many references to Walter’s research contributions, particularly in the area of orthogonal polynomials. In my talk, Matrix Functions and their Sensitivity, I emphasized Walter’s work on conditioning of Vandermonde matrices.

A Vandermonde matrix $V_n$ is an $n\times n$ matrix depending on parameters $x_1,x_2,\ldots,x_n$ that has $j$ th column $[1, x_j, \ldots, x_j^{n-1}]^T$ . It is nonsingular when the $x_i$ are distinct. This is a notoriously ill conditioned class of matrices. Walter said that he first experienced the ill conditioning when he computed Gaussian quadrature formulas from moments of a weight function.

Walter has written numerous papers on Vandermonde matrices that give much insight into their conditioning. Here is a very a brief selection of Walter’s results. For more, see my chapter Numerical Conditioning in Walter’s collected works.

In a 1962 paper he showed that

$\displaystyle\|V_n^{-1}\|_{\infty} \le \max_i \prod_{j\ne i}\frac{ 1+|x_j| }{ |x_i-x_j| }.$

In 1978 he obtained

$\displaystyle\|V_n^{-1}\|_{\infty} \ge \max_i \prod_{j\ne i} \frac{ \max(1,|x_j|) }{ |x_i-x_j| },$

which differs from the upper bound by at most a factor $2^{n-1}$ . A 1975 result is that for $x_i$ equispaced on $[0,1]$ ,

$\displaystyle\kappa(V_n)_{\infty} \sim \frac{1}{\pi} e^{-\frac{\pi}{4}} (3.1)^n.$

A 1988 paper returns to lower bounds, showing that for $x_i \ge 0$ and $n\ge 2$ ,

$\displaystyle\kappa(V_n)_{\infty} > 2^{n-1}.$

When some of the $x_i$ coincide a confluent Vandermonde matrix can be defined, in which columns are “repeatedly differentiated”. Walter has obtained bounds for the confluent case, too.

These results quantify the extreme ill conditioning. I should note, though, that appropriate algorithms that exploit structure can nevertheless obtain accurate solutions to Vandermonde problems, as described in Chapter 22 of Accuracy and Stability of Numerical Algorithms.

Ron DeVore speaking on Optimal Data Assimilation

Photo of Nick Higham’s talk by David Gleich.

Photo Highlights of 2017

Here are some of my favourite photos taken at events that I attended in 2017.

Atlanta (January)

This was the first time I have attended the Joint Mathematics Meetings, which were held in Atlanta, January 4-7, 2017. It was a huge conference with over 6000 attendees. A highlight for me was the launch of the third edition of MATLAB Guide on the SIAM booth, with the help of The MathWorks: Elizabeth Greenspan and Bruce Bailey looked after the SIAM stand: If you are interested in writing a book or SIAM, Elizabeth would love to hear from you!

The conference was held in the Marriott Marquis Hotel and the Hyatt Regency Hotel, both of which have impressive atriums. This photo is taken taken with a fish-eye lens, looking up into the Marriott Marquis Hotel’s atrium (For more photos, see Fuji Fisheye Photography: XT-2 and Samyang 8mm).

Atlanta (March)

I was back in Atlanta for the SIAM Conference on Computational Science and Engineering, February 27-March 3, 2017. A highlight was a 70th birthday dinner celebration for Iain Duff, pictured here speaking at the Parallel Numerical Linear Algebra for Extreme Scale Systems minisymposium: Here is Sarah Knepper of Intel speaking in the Batched Linear Algebra on Multi/Many-Core Architectures symposium (a report on which is given in the blog post by Sam Relton) Torrential rain one night forced me to take shelter on the way back from dinner, allowing a moment to capture this image of Peach Tree Street.

Washington (April)

The National Math Festival was held at the Walter E. Washington Convention Center in Washington DC on April 22, 2017: I caught the March for Science on the same day:

Pittsburgh (July)

The SIAM Annual Meeting, held July 10-14, 2017 at the David Lawrence Convention Center in Pittsburgh, was very busy for me as SIAM president. Here is conference co-chair Des Higham speaking in the minisymposium “Advances in Mathematics of Large-Scale and Higher-Order Networks”: Emily Shuckburgh gave the I.E. Block Community Lecture “From Flatland to Our Land: A Mathematician’s Journey through Our Changing Planet”: The Princeton Companion to Applied Mathematics was on display on the Princeton University Press stand: Here are Des and I on the Roberto Clemente bridge over the Allegheny River, the evening before the conference started:

SIAM Annual Meeting 2017 Highlights

Emily Shuckburgh delivering the I. E. Block Community Lecture “From Flatland to Our Land: A Mathematician’s Journey through Our Changing Planet”. A recording of her lecture is available at https://www.pathlms.com/siam/courses/4988/sections/7425.

It’s a couple of weeks since the 2017 SIAM Annual Meeting, which I previewed in an earlier post. The meeting was held at the David Lawrence Convention Center in Pittsburgh and was co-chaired by Des Higham (University of Strathclyde) and Jennifer Mueller (Colorado State University).

The approximately 1150 attendees enjoyed five days packed from morning to evening with lectures, panel sessions, careers events, professional development sessions, and other activities.

You can catch up with what went on at the meeting in several ways.

SIAM News Articles

SIAM News staff Karthika Cohen and Lina Sorg were on hand to write up articles on selected talks:

Reports on prizes and other events are also available on the SIAM News site:

SIAM Annual Meeting 2017 Preview

It’s a month to the 2017 SIAM Annual Meeting at the David Lawrence Convention Center in Pittsburgh. We’re returning to the location of the 2010 meeting. The meeting is co-chaired by Des Higham (University of Strathclyde) and Jennifer Mueller (Colorado State University).

Here are a few highlights and things it’s useful to know. If you haven’t already made plans to attend it’s not too late to register. Be sure to take in the view from the roof of the convention center, as shown here.

Block Lecture by Emily Shuckburgh

The I. E. Block Community Lecture on Wednesday evening will be given by Emily Shuckburgh on From Flatland to Our Land: A Mathematician’s Journey through Our Changing Planet. Emily, from the British Antarctic Survey, is a co-author of the recent book Climate Change, which she wrote with HRH Prince Charles and Tony Juniper.

Prize Lectures

As always, a number of prize lectures will be given at the meeting. These include the four-yearly James H. Wilkinson Prize in Numerical Analysis and Scientific Computing, which will be awarded to Lek-Heng Lim. His lecture is titled Tensors in Computational Mathematics. See this article about Lek-Heng.

Joint with Activity Group Conferences and Workshops

The meeting is held jointly with the SIAM Conference on Industrial and Applied Geometry (GD17) and the SIAM Conference on Control and Its Applications (CT17), in the same location. One registration fee gains you access to all three meetings!

In addition, the SIAM Workshop on Parameter Space Dimension Reduction (DR17) and the SIAM Workshop on Network Science (NS17) are taking place just before and just after the conference, respectively.

Funding

Funding of mathematics, and other subjects, is in a state of uncertainty under the current US administration. In the minisymposium How Changing Implementations of National Priorities Might Affect Mathematical Funding a panel of representatives from funding agencies will describe the current situation and future opportunities. This is a great chance to hear the latest news from Washington from those in the know.

Students

SIAM provides a host of activities for students, beginning with an orientation session on Sunday evening and including a career fair, a session on career opportunities in business, industry and government (BIG), and the chance to meet and talk to invited speakers and co-chairs.

Hidden Figures

An evening session will include Christine Darden, who was one of the human computers included in the book “Hidden Figures” by Margot Lee Shetterly, on which the recent Hollywood movie of the same title was based.

SIAM Business Meeting

The Business Meeting (Tuesday at 6.15pm) provides an opportunity to hear the president (that’s me!) and SIAM staff report on SIAM’s activities over the past year and to ask questions. The 2017 SIAM Fellows will be recognized, and a reception in their honor follows the Business meeting.

Website

SIAM is developing a new website. A preliminary version will be available on laptops in the exhibit hall for participants to try. Feedback will be much appreciated and SIAM staff will be on hand to receive your comments.

Baseball Match

If you are staying in Pittsburgh on the Friday night, consider attending a baseball match. The Pittsburgh Pirates play the St Louis Cardinals at home at PNC Park on Friday July 14. I went to the Friday match after SIAM AN10 and really enjoyed it; the views from the ground are spectacular.

Twitter

If you are not able to attend you can get a feel for what’s going on by following the hashtag #SIAMAN17 on Twitter.

Pittsburgh

There’s plenty to do and see in Pittsburgh, as the following images illustrate. As well as the impressive bridges over the Allegheny and Monongahela rivers, and some interesting downtown architecture and murals, there’s the Andy Warhol Museum (a short walk from the convention center). Here are some images I took in 2010.

Parallel Numerical Linear Algebra for Extreme Scale Systems

A minisymposium Parallel Numerical Linear Algebra for Extreme Scale Systems was held at the SIAM Conference on Computational Science and Engineering, Atlanta on February 28, 2017.

Today’s most powerful supercomputers are composed of hundreds of thousands of computing cores (CPUs and accelerators) connected in high speed networks that make up a massively parallel high performance computing (HPC) system. These systems are placing new demands on effective scalable numerical algorithms and software libraries, which will only increase in the future as we move towards increasingly heterogeneous systems with millions of compute cores. This minisymposium, which I organized jointly with Bo Kågström (Umeå University, Sweden), focused on addressing these challenges in the context of linear algebra problems through developing novel parallel algorithms, exploring advanced scheduling strategies and runtime systems, carrying out offline and online autotuning, and avoiding communication and synchronization bottlenecks.

Iain Duff showing the new second edition of Direct Methods for Sparse Matrices.

The speakers were all members of the NLAFET (Parallel Numerical Linear Algebra for Future Extreme-Scale Systems) project, which is one of the high-profile extreme-scale computing research projects funded by the European Commission within the Future and Emerging Technologies (FET) program under Horizon 2020. Much of the work described in the minisymposium was carried out within NLAFET.

Around 75 people attended and there was standing room only. Here are the talks, with links to the slides. The names of the speakers are italicized.

The Design and Implementation of a Dense Linear Algebra Library for Extreme Parallel Computers (abstract), Jack J. Dongarra, University of Tennessee and Oak Ridge National Laboratory, USA; Nicholas Higham, Mawussi Zounon, and Samuel Relton, University of Manchester, United Kingdom.
Computing the Low Rank Approximation of a Sparse Matrix (abstract), Laura Grigori and Sebastien Cayrols, Inria, France; James W. Demmel, University of California, Berkeley, USA; Alan Ayala, Inria, France.
Sparse Direct Solvers for Extreme Scale Computing (abstract), Iain Duff, Science & Technology Facilities Council, United Kingdom and CERFACS, Toulouse, France; Jonathan Hogg, Florent Lopez, and Stojce Nakov, Rutherford Appleton Laboratory, United Kingdom.
Extreme-Scale Eigenvalue Reordering in the Real Schur Form (abstract), Lars Karlsson, Carl Christian Kjelgaard Mikkelsen, Mirko Myllykoski, and Bo T. Kågström, Umeå University, Sweden.

Related to this minisymposium was the two-day Workshop on Batched, Reproducible, and Reduced Precision BLAS, held a couple of days beforehand at Georgia Tech. The workshop included presentations from both academia and industry and the program contains links to the speakers’ slides.

Corless, Knuth and Lambert W

Attendees at the SIAM Annual Meeting in Boston last month had the opportunity to meet Donald Knuth. He was there to give the John von Neumann lecture, about which I reported at SIAM News.

At the Sunday evening Welcome Reception I captured this photo of Don and Rob Corless (whose graduate textbook on numerical analysis I discussed here).

Don and Rob are co-authors on the classic paper

Robert M. Corless, Gaston N. Gonnet, D. E. G. Hare and David J. Jeffrey and Donald Knuth, On the Lambert $W$ Function, Adv. in Comput. Math. 5, 329-359, 1996

The Lambert W function is a multivalued function $W_k(x)$ , with a countably infinite number of branches, that solves the equation $x e^x = a$ . According to Google Scholar this is Don’s most-cited paper. Here is a diagram of the ranges of the branches of $W_k(x)$ , together with values of $W_k(1)$ (+), $W_k(10 + 10i)$ (×), and $W_k(-0.1)$ (o).

This is to be compared with the the corresponding plot for the logarithm, which consists of horizontal strips of height $2\pi$ with boundaries at odd multiples of $\pi$ .

Following the Annual Meeting, Rob ran a conference Celebrating 20 years of the Lambert W function at the University of Western Ontario.

Rob co-authored with David Jeffrey an article on the Lambert W function for the Princeton Companion to Applied Mathematics. The article summarizes the basic theory of the function and some of its many applications, which include delay differential equations. Rob and David note that

The Lambert $W$ function crept into the mathematics literature unobtrusively, and it now seems natural there.

The article is one of the sample articles that can be freely downloaded from this page.

I have worked on generalizing the Lambert W function to matrices, as discussed in

Robert M. Corless, Hui Ding, Nicholas J. Higham and David J. Jeffrey, The solution of S exp(S) = A is not always the Lambert W function of A. in ISSAC ’07: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, ACM Publications, pp. 116-121, 2007.

Massimiliano Fasi, Nicholas J. Higham and Bruno Iannazzo, An Algorithm for the Matrix Lambert W Function, SIAM J. Matrix Anal. Appl., 36, 669-685, 2015.

The diagram above is from the latter paper.

Conference Photo Highlights of 2015

Here are my five favourite photos taken at conferences that I attended in 2015.

Salt Lake City

The SIAM Conference on Computational Science and Engineering, held in Salt Lake City in March, was the largest SIAM conference ever, with almost 1600 attendees. This photo shows co-chair Chris Johnson being interviewed for a SIAM video. Sonja Stark (PilotGirl Productions) is on the camera, Adam Bauser (Bauser Media Group) is conducting the interview, and SIAM Public Awareness Officer Karthika Swamy Cohen is standing far right. This team has produced many excellent videos, which can be found on SIAM’s YouTube channel. See, in particular, CSE15 Poster Sizzle and I Use Math For….

Atlanta

The SIAM Conference on Applied Linear Algebra was held in Atlanta in October at the Hyatt Regency hotel. The hotel has a very impressive design with a large atrium overlooked by walkways off which the rooms are situated. This photo was taken looking down into the atrium from one corner, showing the pink light that illuminated this structure during the hours of darkness. I rarely take wildlife photographs, not least due to lack of time, but occasionally an opportunity presents itself. The next image was captured just two blocks from the conference hotel, thanks to an unusually tame buzzard who was happy to pose for my camera.

Glasgow

I gave the after-dinner talk at the 26th Biennial Conference on Numerical Analysis in Glasgow last June (see this post for more details, and this Storify of the conference). The conference dinner was held in the Òran Mór, a converted church in the west end of Glasgow. The next photo shows the impressive venue as it was being set up.

Oxford

In August, many of us gathered in Oxford to celebrate Nick Trefethen’s 60th birthday, at the New Directions in Numerical Computation conference. I very much like this photo, which shows Andy Wathen contemplating one of life’s deeper questions: the linear system of equations $Ax=b$ . A Storify of the conference is available.

50 Years of the Biennial Conference on Numerical Analysis

Last week (June 23-26, 2015) around 200 numerical analysts congregated in Glasgow for the 26th Biennial Conference on Numerical Analysis, held at the University of Strathclyde. This was the 50th anniversary of this biennial conference, the first of which was held in 1965 at St. Andrews University. The original meeting, organized by Ron Mitchell, Mike Osborne, Donald Kershaw and Jack Lambert, was titled Symposium on the Solution Of Differential Equations, lasted two days, and attracted about 25 people. Ron Mitchell moved in 1967 to a chair at Queen’s College, Dundee, which become the University of Dundee in the same year, so the conference continued at Dundee, where it stayed until 2007, organized by Alistair Watson and David Griffiths.

Since 2009 the meeting has been hosted at the University of Strathclyde. The Conference Organizing Committee of Philip Knight, John Mackenzie, and Alison Ramage have introduced various innovations, such as minisymposia and, this year, Scottish country dancing (optional!). This year also saw the introduction of the Fletcher-Powell Lecture, honouring Mike Powell (who sadly passed away earlier this year) and Roger Fletcher, given by Michael Saunders (Stanford). In his introduction to the lecture, Nick Gould emphasized the crucial role that Fletcher and Powell played in developing the field of nonlinear optimization, starting in the 1960s. A Storify is available summarizing tweets about the conference.

An excellent history of the conference was written by Alistair Watson in 2006 and is available on his website. Alistair’s article was invaluable in preparing my after-dinner speech. The conference dinner was held in the impressive Òran Mór, a converted church in the west end of Glasgow. The dining area is seen in the photo below, from the vantage point of a balcony.

Category: conferences

Tricks and Tips in Numerical Computing

Lectures on Multiprecision Algorithms in Kácov

Conference in Honour of Walter Gautschi

Photo Highlights of 2017

Atlanta (January)

Atlanta (March)

Washington (April)

Pittsburgh (July)

SIAM Annual Meeting 2017 Highlights

SIAM News Articles

Other Links

SIAM Annual Meeting 2017 Preview

Block Lecture by Emily Shuckburgh

Prize Lectures

Joint with Activity Group Conferences and Workshops

Funding

Students

Hidden Figures

SIAM Business Meeting

Website

Baseball Match

Twitter

Pittsburgh

Parallel Numerical Linear Algebra for Extreme Scale Systems

Corless, Knuth and Lambert W

Conference Photo Highlights of 2015

Salt Lake City

Atlanta

Glasgow

Oxford

50 Years of the Biennial Conference on Numerical Analysis

Share this:

Share this:

Share this:

Atlanta (January)

Atlanta (March)

Washington (April)

Pittsburgh (July)

Share this:

SIAM News Articles

Other Links

Share this:

Block Lecture by Emily Shuckburgh

Prize Lectures

Joint with Activity Group Conferences and Workshops

Funding

Students

Hidden Figures

SIAM Business Meeting

Website

Baseball Match

Twitter

Pittsburgh

Share this:

Share this:

Share this:

Salt Lake City

Atlanta

Glasgow

Oxford

Share this:

Share this: