Company
Mathematica Solutions to the ISSAC' 97 Systems Challenge

Wolfram Research, Inc.


Problem 1

What is the 4-significant-digit approximation to the condition number of the 256 by 256 Hilbert matrix?

Result
[Graphics:ISSACChallengegr1.gif]


Method 1: Calculate the ratio of the eigenvalues explicitly, using brute force (the straightforward way).

The condition number for the matrix under consideration is the ratio of the largest to the smallest eigenvalue.

The condition number of a Hilbert matrix of dimension [Graphics:ISSACChallengegr2.gif] is roughly equal to [Graphics:ISSACChallengegr3.gif](see [1]); for [Graphics:ISSACChallengegr4.gif] this is approximately [Graphics:ISSACChallengegr5.gif]. We expect to multiply and subtract expressions in intermediate stages, so to be on the safe side we'll use about twice as many digits.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr6.gif]

Here is a plot of the 256 eigenvalues.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr8.gif]
[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr9.gif]

This is the answer.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr10.gif]
[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr11.gif]


Method 2: Use the power method for the matrix and its inverse (the fast way).

Fortunately, there is a closed-form expression for the matrix elements of the inverse of a Hilbert matrix (see [2]). This allows us to iterate toward the smallest and the largest eigenvalues using the power method.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr12.gif]

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr13.gif]

As an aside, we note that the elements of this matrix have an interesting distribution.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr14.gif]
[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr15.gif]

Again, about 800 digits should be enough.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr16.gif]

We define two functions, N to normalize an eigenvector and RayleighQuotient to calculate an eigenvalue.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr17.gif]

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr18.gif]

We iterate until the ratio of the two eigenvalues remains constant up to the required precision.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr19.gif]

Here are plots of the components of these two eigenvectors.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr20.gif]
[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr21.gif]

This is the ratio of the two eigenvalues.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr22.gif]
[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr23.gif]


Method 3: Use LUDecomposition (the general way).

This method works for arbitrary matrices; we don't have to know the inverse explicitly.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr24.gif]

An LU decomposition is more stable than an eigenvalue calculation, so we don't have to use 800 digits. It is enough to have somewhat more digits than the expected size of the condition number.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr25.gif]

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr26.gif]

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr27.gif]

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr28.gif]
[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr29.gif]