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.

180330-2051-24_5956.jpg

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.

180330-0955-28_8866.jpg

Ron DeVore speaking on Optimal Data Assimilation

180329-1542-29_5725.jpg

Photo of Nick Higham’s talk by David Gleich.

This entry was posted in conferences and tagged . Bookmark the permalink.

One Response to Conference in Honour of Walter Gautschi

  1. José-Javier Martínez says:

    Dear Professor Higham,

    It is a pleasure to read your new post in which you look back to classic subjects (and to the very important work of Walter Gautschi). With your reference to chapter 22 of your book you are implicitly remembering your milestone paper of 1987 on the error analysis of Björck-Pereyra algorithms for Vandermonde systems, which you extended (the analysis and the algorithms) in your book.
    I would like to remark the important role of the total positivity of the Vandermonde matrix (if positive nodes are increasingly ordered), which implies the inverse matrix has a checkerboard sign pattern. These facts are briefly recalled in the recent book of Björck “Numerical Methods in Matrix Computations”.
    Unfortunately, so many years after your work (and the work of Boros, Kailath and Olshevsky for Cauchy matrices, and of Demmel and Koev for general totally nonnegative matrices) we still must sadly read (for example in a recent paper on interpolation by Mark Ainsworth and Manuel A. Sánchez) that “the interplay between the ideas of total positivity and Neville elimination are not part of the standard armory of many nonspecialists”. So I would be glad to read in the future some detailed comment from you on these subjects (extending your sentence “appropriate algorithms that exploit structure can nevertheless obtain accurate solutions”), which from my humble point of view should already be basic facts in the numerical linear algebra field.
    Thank you very much for your work.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s