Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 39 ยท Projects and Practice

Project: A Linear System Solver

Write a linear equation solver in Fortran: Gaussian elimination with partial pivoting, matmul checks, residuals, singular matrices, and comparison with LAPACK dgesv.

Solving A x = b for the unknown vector x is the workhorse of scientific computing: circuits, structures, implicit time stepping, least squares and much more all reduce to it. In this project you implement Gaussian elimination with partial pivoting, verify the answer through the residual, handle singular systems, and then learn the one-line way to do it with LAPACK.

The Fortran compiler is not available on this site, so the program is read-only. A Python stand-in implements the same algorithm and prints the expected values.

The algorithm

Take this system, whose solution is x = 1, y = 2, z = 3:

TEXT
2x +  y +  z =  7
 x + 3y + 2z = 13
3x +  y + 4z = 17
  1. Forward elimination. For each column k, subtract multiples of row k from the rows below to create zeros under the diagonal. The matrix becomes upper triangular.
  2. Back substitution. Solve for the last unknown, then work upward.

Without care, a tiny or zero pivot (the diagonal entry you divide by) ruins the result. Partial pivoting fixes this: before eliminating column k, swap the row with the largest absolute value in that column (at or below the diagonal) into the pivot position. A matrix with a zero in the top-left corner is solvable only because of this swap.

flowchart TD
    A["for k = 1 .. n-1"] --> B["find row p with largest |a(p,k)|, p >= k"]
    B --> C["swap rows k and p (matrix and b)"]
    C --> D{"pivot near zero?"}
    D -->|yes| E["singular: stop with error"]
    D -->|no| F["eliminate below the pivot"]
    F --> A
    A -->|done| G["back substitution"]

Forward elimination loop with pivoting, then back substitution.

The module

FORTRAN
module linsolve_mod
  use, intrinsic :: iso_fortran_env, only: dp => real64
  implicit none
  private
  public :: dp, solve

contains

  subroutine solve(a_in, b_in, x, info)
    real(dp), intent(in)  :: a_in(:, :), b_in(:)
    real(dp), intent(out) :: x(:)
    integer,  intent(out) :: info            ! 0 = ok, 1 = singular

    real(dp), allocatable :: a(:, :), b(:)
    real(dp) :: factor, tmp
    real(dp) :: rowtmp(size(b_in))
    integer :: n, k, i, p

    n = size(b_in)
    a = a_in                                  ! work on copies
    b = b_in
    info = 0

    do k = 1, n - 1
      p = k - 1 + maxloc(abs(a(k:n, k)), dim=1)    ! pivot row
      if (abs(a(p, k)) < 1.0e-12_dp) then
        info = 1
        return
      end if
      if (p /= k) then                        ! swap rows k and p
        rowtmp = a(k, :);  a(k, :) = a(p, :);  a(p, :) = rowtmp
        tmp = b(k);        b(k) = b(p);        b(p) = tmp
      end if
      do i = k + 1, n
        factor = a(i, k) / a(k, k)
        a(i, k:n) = a(i, k:n) - factor * a(k, k:n)
        b(i) = b(i) - factor * b(k)
      end do
    end do

    if (abs(a(n, n)) < 1.0e-12_dp) then
      info = 1
      return
    end if

    do i = n, 1, -1                           ! back substitution
      x(i) = (b(i) - dot_product(a(i, i+1:n), x(i+1:n))) / a(i, i)
    end do
  end subroutine solve

end module linsolve_mod

Details worth studying:

  • Copies, not originals. The inputs are intent(in), so the routine copies them into allocatable work arrays (a = a_in allocates automatically).
  • maxloc for pivoting. maxloc(abs(a(k:n, k)), dim=1) returns the position within the slice, so add k - 1 to get the row number.
  • Array operations on rows. a(i, k:n) = a(i, k:n) - factor * a(k, k:n) updates a row segment without an inner loop. Rows are strided in column-major memory, which is fine at this size. Production codes work on columns for speed.
  • dot_product in back substitution. For i = n the slice a(n, n+1:n) is empty, so the dot product is zero: no special case.
  • An error code (info) instead of stop lets the caller decide what to do with a singular system, as LAPACK does.

The driver and the residual check

FORTRAN
program use_solver
  use linsolve_mod
  implicit none
  real(dp) :: a(3, 3), b(3), x(3), r(3)
  integer :: info

  a = reshape([2, 1, 3,   1, 3, 1,   1, 2, 4], [3, 3]) * 1.0_dp
  b = [7, 13, 17] * 1.0_dp

  call solve(a, b, x, info)
  if (info /= 0) stop "matrix is singular"

  r = matmul(a, x) - b
  print "(a, 3f8.4)", "x        = ", x
  print "(a, es10.2)", "max |res| = ", maxval(abs(r))
end program use_solver

reshape fills column by column, so the first three numbers are the first column of a: [2, 1, 3]. Written out, that makes the matrix rows (2 1 1), (1 3 2), (3 1 4) as in the system above. This ordering trips up almost everyone coming from row-major languages.

The residual A x - b is the honest test of a solver: it should be near machine epsilon (1e-15 or smaller, relative to the data). A small residual means the answer satisfies the equations, even if you do not know the true solution.

Python Stand-in: the same algorithm in Python

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second system, [[0,2],[3,1]] x = [4,5], has solution x = 1, y = 2 and shows pivoting in action: without the swap, step one would divide by zero. The last system has proportional rows (the second row is twice the first), so the pivot collapses to zero and the solver reports None, the stand-in for info = 1.

Accuracy and conditioning

A small residual does not guarantee a small error in x. If the matrix is ill-conditioned (nearly singular), tiny changes in b cause large changes in x. Hilbert matrices are the classic example. The condition number measures this: roughly, you lose log10(cond) digits of accuracy. Remedies include higher precision (real64 instead of real32), scaling rows, and iterative refinement: compute r = b - A x, solve A dx = r, update x = x + dx.

The professional way: LAPACK

Write your own solver to learn, but use a library in real work. LAPACK's dgesv does LU factorization with partial pivoting, much faster and better tested:

FORTRAN
real(dp) :: a(n, n), b(n, 1)
integer :: ipiv(n), info

call dgesv(n, 1, a, n, ipiv, b, n, info)   ! a is overwritten by its LU factors,
                                           ! b by the solution x

Link with -llapack -lblas (or OpenBLAS or Intel MKL). info = 0 is success, a positive value means a zero pivot, and the arguments n, nrhs, a, lda, ipiv, b, ldb, info follow the standard LAPACK pattern. Because it overwrites a and b, copy them first if you need them. You can describe the routine with an interface block (interfaces) to get argument checking.

The intrinsic matmul and dot_product are fine for small matrices, but for large products call BLAS dgemm, which is cache-blocked and often an order of magnitude faster.

Extensions

  1. Add a det function: the product of the diagonal after elimination, times (-1) per row swap.
  2. Return the matrix inverse by solving for each column of the identity.
  3. Implement LU factorization once and solve for many right-hand sides.
  4. Add tridiagonal (Thomas) solving for implicit heat diffusion (heat project).
  5. Compare timing against dgesv for n = 100, 500, 1000.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does Gaussian elimination use partial pivoting?

    Swapping in the largest available entry keeps the multipliers small and the elimination stable.
  2. 2. reshape([2, 1, 3, 1, 3, 1, 1, 2, 4], [3, 3]) fills the matrix:

    Fortran arrays are column-major, so reshape fills the first column first.
  3. 3. What does a small residual |A x - b| tell you?

    It shows the equations hold, though an ill-conditioned matrix can still give inaccurate x.
  4. 4. What does LAPACK dgesv do to its arrays a and b?

    dgesv works in place, so copy the inputs first if you still need them.

Summary

  • Gaussian elimination: forward elimination to an upper triangle, then back substitution.
  • Partial pivoting swaps in the largest pivot; check for (near) zero pivots and report info.
  • Array slices and dot_product replace inner loops; reshape fills column by column.
  • Verify with the residual; mind conditioning.
  • In production, call LAPACK (dgesv) and BLAS.

Next: Practice problems