Capstone 2: LU decomposition and solve

A linear solve is two triangular solves around one factorisation. The factorisation writes A = P L U, with a permutation, a unit lower triangle and an upper triangle, and it does so in place: the storage that held A holds both factors at the end. This lesson adds it to the matrix type of the previous one, solves a 3 by 3 system whose answer is known, checks the residual, and shows the message a singular matrix produces.

Elimination with partial pivoting

The loop over k eliminates the entries below the diagonal of column k, and before it does, it looks for the largest magnitude in that column below the diagonal and swaps that row into place. Partial pivoting is what keeps the factors accurate: dividing by the largest available pivot bounds every multiplier by one, and a column whose largest entry is zero is a singular matrix, which is the one error the routine reports.

The search is one line because MAXLOC over a section gives the position, and dim=1 makes it a scalar index for a rank-one section: p = k - 1 + maxloc(abs(m%a(k:, k)), dim=1). The row swap uses a vector subscript on both sides, m%a([k, p], :) = m%a([p, k], :), which the standard allows here because the right-hand side is evaluated before the assignment.

The permutation and the sign

PERM records which row of the original matrix ended up where, so that the right-hand side can be permuted in the same way before the forward substitution. SIGN flips at every swap, and it is the sign of the determinant: the determinant of the factors is the product of the diagonal of U, and the permutation multiplies it by sign. The routine returns it because it is free at that point and expensive to compute later.

Two conventions are worth seeing in the output. The unit diagonal of L is not stored, so the lower triangle of the factor matrix holds the multipliers -0.5 and 0.25 of this example. And the factors are returned in the same type as the matrix, with the same storage, so lu = a before the call is a copy and a stays intact for the residual.

Forward and back substitution

LU_SOLVE takes the factors, the permutation and the right-hand side. It permutes the vector, divides by the unit diagonal implicitly in a forward sweep over L, and then sweeps backwards over U dividing by its diagonal. The two loops are written with explicit indices rather than with array expressions, because each step of a triangular solve depends on the one before it.

The result is a plain array, not a matrix: a right-hand side is a vector, and making it a one-column matrix would add a rank test to every call. That is a design decision the type does not force, and a library that solves many systems at once would take a matrix of right-hand sides instead.

The residual

The answer is checked the way any numerical answer should be: put it back into the original equation and look at what is left. RESIDUAL returns the largest absolute component of A x - b, which is zero when the arithmetic was exact and a small number when it was not. It takes the original matrix, not the factors, so a mistake in the factorisation shows up here rather than in the solution.

The run

The file lu.f90 is the module of lesson 129 with the factorisation, the solve and the residual added, and a program that solves one system and prints the factors, the answer and the check:

module matrix_mod use, intrinsic :: iso_fortran_env, only: dp => real64 implicit none private public :: matrix, from_array, print_matrix, lu_factor, lu_solve, residual type :: matrix real(dp), allocatable :: a(:,:) contains procedure :: trace 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 trace(self) result(t) class(matrix), intent(in) :: self real(dp) :: t integer :: i t = 0.0_dp do i = 1, min(size(self%a, 1), size(self%a, 2)) t = t + self%a(i, i) end do end function trace subroutine print_matrix(name, m) character(len=*), intent(in) :: name type(matrix), intent(in) :: m integer :: i print '(a,a,i0,a,i0,a)', trim(name), ' (', size(m%a, 1), ' x ', size(m%a, 2), ')' do i = 1, size(m%a, 1) print '(10f9.3)', (m%a(i, :)) end do end subroutine print_matrix 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 end module matrix_mod program lu_demo use matrix_mod use, intrinsic :: iso_fortran_env, only: dp => real64 implicit none type(matrix) :: a, lu integer :: perm(3), sign character(len=16) :: mode type(matrix) :: s real(dp) :: b(3), x(3) call get_command_argument(1, mode) a = 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) b = [3.0_dp, 0.0_dp, 9.0_dp] call print_matrix('A', a) lu = a call lu_factor(lu, perm, sign) call print_matrix('LU', lu) print '(a,3(i3),a,i2)', 'perm = ', perm, ' sign = ', sign x = lu_solve(lu, perm, b) print '(a,3f9.4)', 'x = ', x print '(a,es10.3)', 'max residual = ', residual(a, x, b) print '(a,3f9.4)', 'check A*x = ', matmul(a%a, x) if (trim(mode) == 'singular') then s = from_array([1.0_dp, 2.0_dp, 2.0_dp, 4.0_dp], 2, 2) call print_matrix('S', s) call lu_factor(s, perm(1:2), sign) end if end program lu_demo

gfortran -Wall -Wextra -std=f2018 lu.f90 -o lu
./lu

A (3 x 3)
    4.000   -2.000    1.000
  -2.000    4.000   -2.000
    1.000   -2.000    4.000
LU (3 x 3)
    4.000   -2.000    1.000
  -0.500    3.000   -1.500
    0.250   -0.500    3.000
perm =   1  2  3   sign =  1
x =    1.0000    2.0000    3.0000
max residual =  0.000E+00
check A*x =    3.0000    0.0000    9.0000

The system was built from the answer: with x = [1, 2, 3] the right-hand side is [3, 0, 9], and the program finds 1, 2, 3 back with a residual of exactly zero. No pivot was needed, which is why perm is the identity and sign is one; the multipliers are the small numbers in the lower triangle.

A singular matrix

A matrix whose second column is twice its first has no inverse, and the routine says so instead of dividing by zero. The second argument of the program selects a 2 by 2 example:

GFORTRAN_ERROR_BACKTRACE=0 ./lu singular
echo $?

...
S (2 x 2)
    1.000    2.000
    2.000    4.000
ERROR STOP lu_factor: singular matrix
1

The first lines of that run repeat the 3 by 3 system, which the page leaves out. The status is 1, so a script sees the failure, and the message names the routine. A library that has to continue would return a flag in a result type instead, as the solver capstone did, and the caller would decide; a program that cannot do anything sensible with a singular system stops.

The tests

Everything on this page was checked by reading the output. The next lesson turns that into a program: a table of systems with known answers, a relative tolerance per case, the residual of every one, and an exit status that makes the build fail when a case does not come out. It is the last lesson of the capstone and the one that makes the library worth keeping.

Exercises

  1. Build the program with -fcheck=all and run the singular case again. Does the message change, and where does it stop?
  2. Remove the pivot search, keeping everything else, and solve the same system. Does the answer change? Try a matrix where the first pivot is zero.
  3. Print the determinant from the factors and the sign. Which product do you need, and what does the sign do to it?
  4. Solve a 50 by 50 system built from a known answer and print the residual. Why is it not exactly zero any more?

Questions

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

  1. What does the factorisation store in the matrix?

    Answer

    The multipliers below the diagonal and the triangle of U on it

    The unit diagonal of L is not stored.

  2. Why partial pivoting?

    Answer

    It bounds every multiplier by one and keeps the factors accurate

    Dividing by the largest available pivot.

  3. What does MAXLOC(..., dim=1) return for a rank-one section?

    Answer

    A scalar index

    dim collapses the only dimension.

  4. What is PERM for?

    Answer

    It records the row swaps so the right-hand side can be permuted the same way

    The identity here, because no swap was needed.

  5. What is SIGN?

    Answer

    The sign of the determinant, flipped at every swap

    Free at factorisation time.

  6. What was the answer of the 3 by 3 system?

    Answer

    1, 2, 3

    The system was built from that answer.

  7. What is the residual of the run?

    Answer

    Zero

    The arithmetic was exact for this system.

  8. What does the singular example print?

    Answer

    ERROR STOP lu_factor: singular matrix and status 1

    The pivot column is zero.

  9. Why does the residual use the original matrix?

    Answer

    A mistake in the factorisation then shows up in the check

    The factors are a different matrix.

  10. What replaces the ERROR STOP in a library that must continue?

    Answer

    A status flag in a result type

    The caller decides.

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