Linear systems by hand

A dense linear system is the other half of numerical work, and the algorithm is short enough to write in one subroutine: eliminate the entries below the diagonal column by column, then substitute back from the last equation. What makes it production code is not the arithmetic but three details: the pivot choice, the check for a zero pivot, and the residual that tells the caller whether the answer is worth anything.

The system

The program builds a 3 by 3 matrix, chooses the solution it wants, computes the right-hand side from it, and then asks the solver to recover the solution. That order matters: a hand-written problem whose right-hand side is rounded independently has no exact answer to compare against, and a test needs one.

The file lin.f90:

module linsys implicit none private public :: solve contains subroutine solve(a, b, x, info) real, intent(in) :: a(:, :), b(:) real, intent(out) :: x(:) integer, intent(out) :: info real :: m(size(a, 1), size(a, 2)), rhs(size(b)), tmp integer :: n, i, j, k, p n = size(b) m = a rhs = b info = 0 do k = 1, n - 1 p = k - 1 + maxloc(abs(m(k:, k)), 1) if (m(p, k) == 0.0) then info = k return end if if (p /= k) then tmp = rhs(k) rhs(k) = rhs(p) rhs(p) = tmp do j = 1, n tmp = m(k, j) m(k, j) = m(p, j) m(p, j) = tmp end do end if do i = k + 1, n tmp = m(i, k) / m(k, k) m(i, k) = 0.0 do j = k + 1, n m(i, j) = m(i, j) - tmp * m(k, j) end do rhs(i) = rhs(i) - tmp * rhs(k) end do end do if (m(n, n) == 0.0) then info = n return end if do i = n, 1, -1 x(i) = rhs(i) do j = i + 1, n x(i) = x(i) - m(i, j) * x(j) end do x(i) = x(i) / m(i, i) end do end subroutine solve end module linsys program lindemo use linsys implicit none real :: a(3, 3), x_true(3), b(3), x(3) integer :: info a = reshape([3.0, 2.0, -1.0, 1.0, 4.0, 2.0, -1.0, 1.0, 5.0], [3, 3]) x_true = [1.0, 2.0, -1.0] b = matmul(a, x_true) print '(a,3f8.2)', 'b =', b call solve(a, b, x, info) print '(a,i0)', 'info = ', info print '(a,3f10.4)', 'x =', x print '(a,es12.4)', 'max error = ', maxval(abs(x - x_true)) print '(a,es12.4)', 'residual = ', maxval(abs(matmul(a, x) - b)) a(3, :) = 2.0 * a(1, :) b = matmul(a, x_true) call solve(a, b, x, info) print '(a,i0)', 'singular info = ', info print '(a,a)', 'x is untouched: a singular system has no answer' end program lindemo

gfortran -Wall -Wextra -std=f2018 lin.f90 -o lin

lin.f90:21:10:

21 | if (m(p, k) == 0.0) then
| 1
Warning: Equality comparison for REAL(4) at (1) [-Wcompare-reals]

That warning is the one from lesson 091 and it is deliberate here: a pivot is singular when it is exactly zero, and this test is about a structural property of the matrix rather than about a computed value. The build succeeds and the program runs:

./lin

b = 6.00 9.00 -2.00
info = 0
x = 1.0000 2.0000 -1.0000
max error = 2.3842E-07
residual = 9.5367E-07
singular info = 3
x is untouched: a singular system has no answer

Gaussian elimination

For each column k the subroutine computes the multipliers m(i,k)/m(k,k) and subtracts that multiple of row k from every row below it, which zeroes the column. After k = n-1 the matrix is upper triangular. The loop that does the subtraction starts at j = k+1 and skips the entry it knows becomes zero, which saves a third of the work and makes the m(i,k) = 0.0 line explicit rather than a result of rounding.

The work is n^3/3 multiplications for the elimination and n^2/2 for the substitution, so almost all of the cost is in the first loop. That is why every serious library stops at the factorisation: the same upper triangular matrix solves for many right-hand sides with one elimination.

Partial pivoting

maxloc(abs(m(k:, k)), 1) finds the largest pivot in the column at or below the diagonal, and the rows are swapped so that this value becomes the divisor. Without the swap a small pivot divides everything below it and the rounding error grows; with it the multipliers are never larger than one, which bounds the growth of the intermediate values.

The expression k - 1 + maxloc(...) is the index conversion: maxloc counts from one in the section, and the section starts at row k. The 1 is the dimension argument of maxloc, the subject of lesson 043, and it is what makes the result a scalar rather than an array of length one.

Back substitution

The last equation has one unknown, the second to last has two, and the loop walks upwards subtracting what it already knows. x(i) = (rhs(i) - sum of the known terms) / m(i,i), which is the three lines at the end of the subroutine. The writes run from n down to one, so every x(j) in the sum was computed in an earlier pass.

The solution printed is exactly 1, 2, -1 to four decimals, and the error against the chosen solution is 2.4e-07, which is the single-precision roundoff of the elimination. That agreement is the strongest check a solver can have on a problem whose answer is known, and it is why the test data are built from a solution rather than from random coefficients.

The residual

The residual is maxval(abs(matmul(a, x) - b)) and it is 9.5e-07, one order larger than the error in x because the matrix amplifies it. A program that has only the residual knows that the equations are nearly satisfied, which is all the data can prove; a program that also has a known solution knows how far the answer is, which is what a test needs.

The two numbers are worth keeping apart. A small residual with a large error in x is the signature of an ill-conditioned matrix: the equations are satisfied, but many solutions satisfy them almost equally well, and no solver can pick the right one. The condition number is what measures that, and it is one matmul away from this program in any numerical library.

A singular system

The second half of the program makes the matrix singular by setting the third row to twice the first. The elimination finds a zero pivot at k = 3, sets info = 3 and returns without touching x. A caller that ignores info then reads a vector full of whatever was there before, which is why the argument is the fourth of four and not an afterthought.

A zero pivot is the easy case. A pivot of 1e-20 in a matrix whose entries are of order one is just as fatal and does not compare equal to zero, which is why a production solver also tests the pivot against the size of the matrix and reports a condition estimate rather than a flag.

A rank mismatch

The dummy declarations carry the shapes the solver needs, and a caller that swaps two arguments gets a compile error rather than a wrong answer:

program badrank implicit none real :: a(3, 3), b(3), x(3) integer :: info a = 1.0 b = 1.0 call solve(b, a, info) print *, x contains subroutine solve(m, rhs, info) real, intent(in) :: m(:, :), rhs(:) integer, intent(out) :: info info = 0 if (size(rhs) + size(m) > 0) info = 1 end subroutine solve end program badrank

gfortran -Wall -Wextra -std=f2018 badrank.f90 -o badrank

badrank.f90:8:13:

8 | call solve(b, a, info)
| 1
Error: Rank mismatch in argument 'm' at (1) (rank-2 and rank-1)

The message gives both ranks in the order the compiler compared them: the dummy is rank two, the actual is rank one. A mistake like this is exactly the kind the compiler can catch only because the subroutine is in a module and its interface is explicit.

Exercises

  1. Solve the same system with two different right-hand sides by calling solve twice. How many eliminations does a factorisation would save?
  2. Remove the pivot search and use p = k. Does the answer change for this matrix, and what would make it change?
  3. Print info after the singular call and test it in the program with a message. Which line of the output then replaces the last one?
  4. Change the matrix to a 4 by 4 and the solution to four values. What has to change in the declaration of a, and what stays the same?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does partial pivoting do?

    Answer

    Swaps rows so the largest available pivot divides the column

    It keeps the multipliers at or below one.

  2. How much work is the elimination step?

    Answer

    About n cubed over three multiplications

    Two loops over the rows and columns below the pivot.

  3. What does this program print? program p implicit none real :: a(2, 2), b(2), x(2) a = reshape([2.0, 1.0, 1.0, 3.0], [2, 2]) b = [5.0, 10.0] x(1) = (b(1) - a(1, 2) * 0.0) / a(1, 1) print *, x(1) end program p

    Answer

    2.5

    Five divided by two is two and a half.

  4. What does info report?

    Answer

    Zero for success, and the column of the zero pivot otherwise

    It is the third way out of the subroutine.

  5. Why is the right-hand side computed from a chosen solution?

    Answer

    So the test has an exact answer to compare with

    A known solution is what turns a run into a test.

  6. What does a small residual with a large error in x mean?

    Answer

    The matrix is ill-conditioned

    Many solutions satisfy the equations nearly equally well.

  7. What is maxloc(abs(m(k:, k)), 1) used for?

    Answer

    Finding the row with the largest pivot in the column

    The dim argument makes the result a scalar index.

  8. Why is a pivot of 1e-20 as fatal as a zero pivot?

    Answer

    Dividing by it amplifies rounding error, and it is not equal to zero

    The zero test cannot see it.

  9. What does gfortran report for a rank-one actual argument to a rank-two dummy?

    Answer

    Error: rank mismatch in argument

    The explicit interface gives the compiler the rank.

  10. Why keep the factorisation instead of solving each right-hand side from scratch?

    Answer

    The elimination is the expensive part and can be reused

    n cubed over three against n squared per extra right-hand side.

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