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.

One thought on “Conference in Honour of Walter Gautschi”

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.

Share this:

Related

One thought on “Conference in Honour of Walter Gautschi”

Leave a Reply Cancel reply