1.2.1 Solving Linear Equations

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: An m x n matrix A, and an m x 1 vector b, representing m linear equations with n variables.

Problem: What is the vector x such that A \cdot x = b?

Excerpt from The Algorithm Design Manual: Solving linear systems is a problem of such scientific and commercial importance that excellent codes are readily available. There is likely no good reason to implement your own solver, even though the basic algorithm (Gaussian elimination) is one we learned in high school. This is especially true if you are working with large systems.

Gaussian elimination is based on the fact that the solution to a system of linear equations is invariant under scaling (multiplying both sides by a constant; i.e. if x=y, then 2x=2y) and adding equations (i.e. the solution to the equations x=y and w=z is the same as the solution to x=y and x+w=y+z). Gaussian elimination scales and adds equations so as to eliminate each variable from all but one equation, leaving the system in such a state that the solution can just be read off from the equations.

The best books available for this problem are Matrix Computations by Gene H. Golub and Charles F. Van Loan, and Numerical Recipes in C , Fortran 77 , Fortran 90 , or Pascal , by William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Programs from these books in C and Fortran are also available.


Implementations

  • LAPACK and LINPACK -- Linear Algebra PACKages (FORTRAN) (rating 10)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 7)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 3)

    Related Problems

  • Bandwidth Reduction
  • Determinants and Permanents
  • Matrix Multiplication


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .