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

  1. Add a 10 by 10 Hilbert case with a tolerance you choose after seeing its error. Which power of ten is honest?
  2. 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?
  3. Make the suite print the condition number instead of the tolerance. How would you estimate it without a library?
  4. 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.

  1. 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.

  2. 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.

  3. What was the error of the 4 by 4 Hilbert case?

    Answer

    6.114E-13

    The residual was 4.441E-16.

  4. 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.

  5. 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.

  6. What is the error of the 6 by 6 Hilbert case?

    Answer

    5.260E-10

    And the tolerance of 1e-16 cannot be met.

  7. Why include a case that must fail?

    Answer

    So the suite proves it can fail at all

    A suite that cannot fail proves nothing.

  8. What status does the strict run leave?

    Answer

    1

    ERROR STOP 1.

  9. 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.

  10. 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

Banner image