Capstone 2: tests with tolerances
The solver of the previous lesson was checked by reading its output, which is not a test. A test is a program that knows the answer in advance, compares it with the computed one, and leaves a status a build can read. This lesson closes the matrix capstone with such a program: four systems, four tolerances, a table of what came out, and a case whose tolerance is below what double precision can reach, which the suite has to fail rather than pass.
A table of systems
Each case is a matrix, an exact answer and a tolerance. The driver builds the right-hand side from the exact answer, b = A x, solves, and compares the solution with the answer it started from. That order is what makes the test possible at all: a system taken from a book has an answer nobody has in the program.
Four cases cover the shapes that matter. A tridiagonal 3 by 3 with an exact answer of integers, a 2 by 2 that needs no pivot, a 4 by 4 Hilbert matrix whose entries are 1/(i+j-1) and which is famously ill-conditioned, and a 5 by 5 Hilbert matrix with an answer of one to five. The two Hilbert cases are the interesting ones, and the section on tolerances explains why their tolerance is not the same as the others.
How the error is measured
MAX_ERROR returns maxval(abs(x - exact)) / max(1, maxval(abs(exact))): the largest component of the difference, divided by the size of the answer when the answer is larger than one. For an answer of ones it is the absolute error and for an answer of millions it is a relative one, which is the form that means the same thing in both cases (lesson 119 has the same function with the same reasoning).
The table also prints the residual, max(abs(A x - b)). The two measures answer different questions: the error says how far the computed answer is from the true one, and the residual says how well the answer satisfies the equation. An ill-conditioned system can have a tiny residual and a large error, and that is exactly what the Hilbert rows show.
A tolerance per case
The tolerance is written in the table with the case, not in one place for the whole suite, because it depends on the matrix. A well-conditioned system solved in double precision gives an answer accurate to about 1.0e-15, so 1.0e-12 is a strict test that still has three orders of margin. A 4 by 4 Hilbert matrix has a condition number of about 1.5e4, which turns the same 1.0e-16 of machine precision into an error of about 1.0e-12 in the answer, and the suite allows 1.0e-8.
Those numbers are not estimated from theory on this page: they are the errors the run below prints, and the tolerance of each case was set after the first run showed them. That is the honest way to set a tolerance in a numerical test: run the code, see the error, write a bound that leaves a margin for another machine, and state why it is what it is.
The passing run
The file tests.f90, the matrix module with the case table added and a program that runs it:
module matrix_mod
use, intrinsic :: iso_fortran_env, only: dp => real64
implicit none
private
public :: matrix, from_array, hilbert, lu_factor, lu_solve, residual, max_error
type :: matrix
real(dp), allocatable :: a(:,:)
end type matrix
contains
pure function from_array(values, nrows, ncols) result(m)
real(dp), intent(in) :: values(:)
integer, intent(in) :: nrows, ncols
type(matrix) :: m
m%a = reshape(values, [nrows, ncols])
end function from_array
pure function hilbert(n) result(m)
integer, intent(in) :: n
type(matrix) :: m
integer :: i, j
allocate(m%a(n, n))
do j = 1, n
do i = 1, n
m%a(i, j) = 1.0_dp / real(i + j - 1, dp)
end do
end do
end function hilbert
subroutine lu_factor(m, perm, sign)
type(matrix), intent(inout) :: m
integer, intent(out) :: perm(:)
integer, intent(out) :: sign
integer :: i, k, p, n
real(dp) :: pivot, factor
n = size(m%a, 1)
perm = [(i, i = 1, n)]
sign = 1
do k = 1, n - 1
p = k - 1 + maxloc(abs(m%a(k:, k)), dim=1)
if (abs(m%a(p, k)) <= 0.0_dp) error stop 'lu_factor: singular matrix'
if (p /= k) then
m%a([k, p], :) = m%a([p, k], :)
perm([k, p]) = perm([p, k])
sign = -sign
end if
pivot = m%a(k, k)
do i = k + 1, n
factor = m%a(i, k) / pivot
m%a(i, k) = factor
m%a(i, k + 1:n) = m%a(i, k + 1:n) - factor * m%a(k, k + 1:n)
end do
end do
if (abs(m%a(n, n)) <= 0.0_dp) error stop 'lu_factor: singular matrix'
end subroutine lu_factor
function lu_solve(lu, perm, b) result(x)
type(matrix), intent(in) :: lu
integer, intent(in) :: perm(:)
real(dp), intent(in) :: b(:)
real(dp) :: x(size(b))
integer :: i, k, n
real(dp) :: s
n = size(b)
do i = 1, n
x(i) = b(perm(i))
end do
do k = 2, n
do i = k, n
x(i) = x(i) - lu%a(i, k - 1) * x(k - 1)
end do
end do
do i = n, 1, -1
s = x(i)
do k = i + 1, n
s = s - lu%a(i, k) * x(k)
end do
x(i) = s / lu%a(i, i)
end do
end function lu_solve
pure function residual(a, x, b) result(r)
type(matrix), intent(in) :: a
real(dp), intent(in) :: x(:), b(:)
real(dp) :: r
r = maxval(abs(matmul(a%a, x) - b))
end function residual
pure function max_error(x, exact) result(e)
real(dp), intent(in) :: x(:), exact(:)
real(dp) :: e
e = maxval(abs(x - exact)) / max(1.0_dp, maxval(abs(exact)))
end function max_error
end module matrix_mod
program matrix_tests
use matrix_mod
use, intrinsic :: iso_fortran_env, only: dp => real64, output_unit
implicit none
integer :: n, i, passed, failed
real(dp), allocatable :: exact(:), b(:), x(:)
type(matrix) :: a, lu
integer, allocatable :: perm(:)
integer :: sign
real(dp) :: tol, err, res
character(len=16) :: mode
call get_command_argument(1, mode)
passed = 0
failed = 0
print '(a)', 'case n tol error residual result'
do i = 1, 4
call build_case(i, a, exact, tol)
n = size(exact)
if (allocated(perm)) deallocate(perm)
allocate(perm(n))
b = matmul(a%a, exact)
lu = a
call lu_factor(lu, perm, sign)
x = lu_solve(lu, perm, b)
err = max_error(x, exact)
res = residual(a, x, b)
if (err <= tol) then
passed = passed + 1
print '(a18,2x,i2,2x,es9.2,2x,es10.3,2x,es10.3,2x,a)', case_name(i), n, tol, err, res, 'ok'
else
failed = failed + 1
print '(a18,2x,i2,2x,es9.2,2x,es10.3,2x,es10.3,2x,a)', case_name(i), n, tol, err, res, 'FAIL'
end if
end do
print '(a,i0,a,i0,a)', '# ', passed + failed, ' systems, ', failed, ' failures'
flush (output_unit)
if (trim(mode) == 'strict') then
a = hilbert(6)
deallocate(exact, perm)
allocate(exact(6), perm(6))
exact = 1.0_dp
b = matmul(a%a, exact)
lu = a
call lu_factor(lu, perm, sign)
x = lu_solve(lu, perm, b)
err = max_error(x, exact)
print '(a,es10.3,a,es9.2)', 'hilbert 6 with tol 1.0e-16: error ', err, ' tolerance ', 1.0e-16_dp
if (err > 1.0e-16_dp) then
print '(a)', '# the tolerance is below what double precision can reach'
error stop 1
end if
end if
contains
function case_name(which) result(name)
integer, intent(in) :: which
character(len=18) :: name
select case (which)
case (1)
name = 'tridiagonal 3'
case (2)
name = '2 by 2'
case (3)
name = 'hilbert 4'
case default
name = 'ones 5'
end select
end function case_name
subroutine build_case(which, m, exact, tol)
integer, intent(in) :: which
type(matrix), intent(out) :: m
real(dp), allocatable, intent(out) :: exact(:)
real(dp), intent(out) :: tol
select case (which)
case (1)
m = from_array([4.0_dp, -2.0_dp, 1.0_dp, -2.0_dp, 4.0_dp, -2.0_dp, 1.0_dp, -2.0_dp, 4.0_dp], 3, 3)
exact = [1.0_dp, 2.0_dp, 3.0_dp]
tol = 1.0e-12_dp
case (2)
m = from_array([2.0_dp, 1.0_dp, 1.0_dp, 3.0_dp], 2, 2)
exact = [1.0_dp, -1.0_dp]
tol = 1.0e-12_dp
case (3)
m = hilbert(4)
exact = [1.0_dp, 1.0_dp, 1.0_dp, 1.0_dp]
tol = 1.0e-8_dp
case default
m = hilbert(5)
exact = [1.0_dp, 2.0_dp, 3.0_dp, 4.0_dp, 5.0_dp]
tol = 1.0e-10_dp
end select
end subroutine build_case
end program matrix_tests
gfortran -Wall -Wextra -std=f2018 tests.f90 -o tests
./tests
case n tol error residual result
tridiagonal 3 3 1.00E-12 0.000E+00 0.000E+00 ok
2 by 2 2 1.00E-12 0.000E+00 0.000E+00 ok
hilbert 4 4 1.00E-08 6.114E-13 4.441E-16 ok
ones 5 5 1.00E-10 6.922E-13 0.000E+00 ok
# 4 systems, 0 failures
The two integer systems come out exactly, which is what a small well-conditioned system does. The Hilbert rows show the conditioning: the 4 by 4 answer is wrong in the twelfth digit and its residual is forty times smaller than the error, and the 5 by 5 answer is wrong in the twelfth digit again with a residual of exactly zero. A test that only looked at the residual would pass a solution with no correct digits left.
A tolerance nothing can reach
The second argument adds a 6 by 6 Hilbert matrix with a tolerance of 1.0e-16, which is below the machine precision of a double. The suite has to fail, and it does:
GFORTRAN_ERROR_BACKTRACE=0 ./tests strict
echo $?
...
# 4 systems, 0 failures
hilbert 6 with tol 1.0e-16: error 5.260E-10 tolerance 1.00E-16
# the tolerance is below what double precision can reach
ERROR STOP 1
1
The first five lines repeat the table above, which the page leaves out. The 6 by 6 Hilbert matrix has a condition number near 1.5e7, so a perfect algorithm in double precision still lands about 1.0e-9 away from the exact answer, and the run prints 5.260e-10. The status is 1, so a build that runs this mode fails, which is the point: a test whose tolerance nobody can meet is a broken test, and the suite says so instead of passing.
FLUSH (OUTPUT_UNIT) before the strict section is what keeps this log in order when it is redirected to a file, the same detail as lesson 119: the buffered table would otherwise appear after the ERROR STOP line that belongs below it.
Rules for numerical tests
Build the case from a known answer, never the other way round. Give every case its own tolerance and write down why it is that number. Print both the error and the residual, and do not accept one as evidence for the other. Compare with a relative measure when the magnitude varies. Include a case that must fail, so that the suite proves it can fail at all. And keep the whole thing in the build: ./tests with a status of 0 is a test, the same output read by a person is a demonstration.
The matrix capstone is finished: a type, a factorisation, a solver and a suite. The next capstone has nothing to do with floating point: a batch program that reads records from a file, sorts them and writes a grouped report, which is the other half of the work a Fortran programmer is paid for.
Exercises
- Add a 10 by 10 Hilbert case with a tolerance you choose after seeing its error. Which power of ten is honest?
- Set the tolerance of the tridiagonal case to 1.0e-16. Does it still pass, and why does the answer of an integer system come out exact?
- Make the suite print the condition number instead of the tolerance. How would you estimate it without a library?
- Run the suite on the build with -fcheck=all -g. Does anything change, and what would a failure there mean?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Where does the right-hand side of each case come from?
Answer
From the matrix multiplied by the known answer
A system needs an answer the program knows.
-
What does MAX_ERROR compute?
Answer
The largest component of the difference, scaled by the size of the answer
A relative measure that works at any magnitude.
-
What was the error of the 4 by 4 Hilbert case?
Answer
6.114E-13
The residual was 4.441E-16.
-
Why is the Hilbert tolerance 1e-8 and not 1e-12?
Answer
Its condition number turns machine precision into a much larger error
The tolerance follows the conditioning.
-
What can a tiny residual hide?
Answer
A large error in the answer, when the system is ill-conditioned
The two measures answer different questions.
-
What is the error of the 6 by 6 Hilbert case?
Answer
5.260E-10
And the tolerance of 1e-16 cannot be met.
-
Why include a case that must fail?
Answer
So the suite proves it can fail at all
A suite that cannot fail proves nothing.
-
What status does the strict run leave?
Answer
1
ERROR STOP 1.
-
When is a numerical result a test?
Answer
When a program compares it with a known answer and the status says so
The status is what a build reads.
-
Which two measures does the table print?
Answer
The error against the exact answer and the residual
Both are needed for an ill-conditioned case.
The programs on this page were built with GNU Fortran (Alpine 15.2.0) 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev