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
- Solve the same system with two different right-hand sides by calling solve twice. How many eliminations does a factorisation would save?
- Remove the pivot search and use p = k. Does the answer change for this matrix, and what would make it change?
- 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?
- 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.
-
What does partial pivoting do?
Answer
Swaps rows so the largest available pivot divides the column
It keeps the multipliers at or below one.
-
How much work is the elimination step?
Answer
About n cubed over three multiplications
Two loops over the rows and columns below the pivot.
-
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 pAnswer
2.5
Five divided by two is two and a half.
-
What does
inforeport?Answer
Zero for success, and the column of the zero pivot otherwise
It is the third way out of the subroutine.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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