NOTES Matrices for testing of numeric calculus routines

By Foxes & C

As we have finished same numeric routines for linear algebra - such as matrix inversion, linear system, etc. - we need something to perform our tests. Better if we know the exact solution in order to evaluate the approximation errors.

We have collected here same useful matrices used in our testing activity. Hope these help same other developers or mathematics

Hilbert matrices

Combination matrices

Sparse matrices

Wandermonde matrices

Singular matrices

Tartaglia matrices

 

Example 1: Hilbert's matrices

Very easy to generate: a(i,j) = 1/(i+j-1)

 

Despite of their clean aspect this kind of matrices are very ill-conditioned also for moderate dimension. The exact determinants and inverse matrices for order 6,7,8 are listed below:

6° order Hilbert matrix: Determinant of = 1/186313420339200000 @ 5.367E-18

 

7° order Hilbert matrix: Determinant of = 1/2067909047925770649600000 @ 4.835E-25

 

8° order Hilbert matrix: Determinant of = 1/365356847125734485878112256000000 @ 2.737E-33

 

Example 2: Combination's matrices

This class of matrices is very useful because it can be easy generate but - this is very important - we can predict the exact results of the system Ax=b for any dimension. Another features very important is that they have lots of decimal values, very useful for testing the round-off error. Moreover the exact results are always integer and this facilitates the comparing.

They are defined with:

a(1,j) = 1 a(i,1) = 1/i	for j =1 ...n for i=1 ..n
a(i,j) = a(i,j-1)+a(i-1,j-1)		for i=2 ..n , j=2 ..n

The matrix can be built starting from the first row - all 1 - and the first column - inverses of natural numbers.
After that, each cells is the sum of the two left and left-upper cells

These matrices are unitary: that is, DET=1. Here is a matrix of 7° order

 

If we solve the linear system A x = b , where b is the vector: b = [0, 0, .....0, 1]^T

The exact solution is given by the following simple formula

x(i) = (-1)n+i *Comb(n-1,i-1)

for i=1 ..n

In this case the values of the solution are:

For a 10° order we have:

For a 15° order we have:

And so on...

We can use also this results to measure the general accuracy of the invert matrix; we have only to check the combination's vector in the last column.

This matrices are suitable to build test-case for high dimension > 20.

The round-off error measured for several matrix dimension is show in the following table

 

 Example 3: Sparse matrices

A useful class is generate as following:

 

The first element a₁₁ is computed at the end by the formula:

a11 = 1+Si aii

for i= 2...n

for n = 6 we have a₁₁ = 3+2/7 = 3.283333...

Determinant of this class can be easy computed as DET = (n-1)! . for n = 6 , DET = 120

Also the inverse is always note, being this integer, simply matrix:

 

Example 4: Wandermonde's matrices

This is a note class of difficult matrices. An interesting feature about building test matrices is that round-off error can be modulate by a single parameter.

 

For example, giving x = 0 and n= 6 we get the following matrix

 

This matrix can be used as test for solving linear system Ax = b , where b is given by the sum of each row

bi = Sj aij

for j= 1...n, for i= 1...n

In our example: b^T = [ 6 , 15 , 55 , 225 , 979 , 4425 ]

With this values, the exact solution x is always unitary; that is x = [ 1, 1 , 1 , 1 , 1 , 1 ]

The difference between a numerical solution and the exact one, gives the general accuracy of the algorithm used. If we want to increase the difficult without change the matrix order, we simply increase the parameter x . The following table shows the round-off error for several values of x

 

 

Example 5: Singular matrices

 

This simple 3 x 3 matrix is singular; DET = 0

Probably, with any 32bit numeric program you can't prove it! You will get a (wrong!) inverse

See also Limit in matrix computation

 

Example 6: Tartaglia's matrices

This class of matrices is very useful because it can be easy generate but - this is very important - we can predict the exact results of the inverse for any dimension. Another features very important is that they both Tartaglia’s matrix and its inverse have always integer values, very useful for testing the round-off error.

They are defined with:

a(1,j) = 1 a(i,1) = 1	for j =1 ...n for i=1 ..n		(all 1 in the first row) (all 1 in the first column)
a(i,j) = Sj a(i-1, j)		for j=2 ..n

The matrix can be built starting from the first row - all 1 - and the first column – all 1.
After that, each cells is the sum of all left cells of the  upper row. Example

a(4,4) = a(3,4)+a(3,3)+a(3,2)+a(3,1) = 10+6+3+1

Here is a 6x6 Tartaglia’s matrix

And here is its inverse

As we can see both matrices are integer.
Any round-off error of the inverse matrix must be regard as a round-off error and immediately detected.
This trick can be used to evaluate the round-off errors introduced by an algorithm for inverting matrices without to know exactely the result. For example, assume that in the inversion of a Tartaglia’s matrix you find an element like this

A(1,1) = 5.99999999999985

Clearly, the exact value is 6 end  the error will easily compute in the following  way: 

Err(1,1) = | A(1,1) – Round(A(1,1),0)| =  0.000000003456    @ 1.518E-13

If we take the average of errors of all matrix elements, repeating for different dimension of Tartaglia’s matrices, we have te following result:

As we can see the round-off errors became evident also for moderate dimension.

 

 

   

TOP

Home