Gaussian Elimination

Preliminaries

Motivation

REF

Counting Operations

Gaussian and Gauss-Jordan elimination are examples of algorithms: q finite sequence of rigorous instructions designed to implement a particular task, In our case of solving systems of linear equations it involves the row reduction of the augmented matrix. Algorithms are particularly well suited to computer implementation, but not all algorithms are created equal. Apart from the speed, memory, and other attributes of the computer system on which they are running, some algorithms are faster than others. One measure of the so-called of an algorithm (a measure of its efficiency, or ability to perform its task in a reasonable number of steps) is the number of basic operations it performs as a func­ tion of the number of variables that are input.

Let's examine two stages of solving systems of equations that include forward elimination or Gaussian elimination involving REF (reduced echelon form) and then back substitution, or Gauss--Jordan procedure, RREF. In general, the forward phase takes much longer than the backward phase. So we focus on REF procedure. For our purposes, the basic operations are multiplication, addition, subtraction, and division. Of these arithmetic operations, multiplications are performed on computers faster than all other arithmetic operations. The slowest operation is division (that could be least accurate: four divisions may alter the last decmal place of the number). An algorithm for solving a linear system is usually measured in flops (or floating point operations). Note that the "S" in the acronym "FLOPS" stands for "second" and is used in combination with "P" (for "per") to indicate a rate. We will ignore operations of switching rows in augmented matrices because they are performed much more rapidly than arithmetic operations and actually involve just relabeling.

We consider m × n matrices that include augmented matrices corresponding to systems of equations with m × (n−1) coefficient matrices, so, if the augmented matrix is m × n, the number of input variables is n−1. Thus, our task is to find or estimate the number of arithmetic operations performed by Gaussian and Gauss-Jordan elimination as a function of m and n. Furthermore, we will not worry about special cases that may arise, but rather establish the worst case that can arise---when the algorithm takes as long as possible. Since this will give us an estimate of the time it will take a computer to perform the algorithm (if we know how long it takes a computer to perform a single operation) , we will denote the number of operations performed by an algorithm by N(m, n). We will typically be interested in behavior of this function for large values of m and n.

There is often a gap between mathematical theory and its practical implementation---Gaussian elimination and modification of a matrix to the reduced row echelon form being good examples. Computers usually operate with floating point approximations to real numbers. A number is, in general, represented approximately to a fixed number of significant digits (the significand or mantissa) and scaled using an exponent in some fixed base, normally two. For example, the rational number 4.5 is converted to single binary normalized floating format as follows

where .001 is the mantissa and 2 is the exponent with respect to base 2. A well known number π is represented as 3.1415926, where 0.1415926 is the mantissa. The double precision format has 52 bits for significand (1 represents implied bit), 10 bits for exponent and 1 bit for sign, while single precision has only 23 bits for mantissa and 7+1 for exponent. Accuracy in floating point representation is governed by number of significand bits, whereas range is limited by exponent. Not all real numbers can exactly be represented in floating point format.

Therefore, arithmetic operations with these numbers on a computer are not exact and introduce roundoff errors. In practical computation it is not just zero pivots that are unwelcome but also small pivots. The problem with small pivots is that they can lead to large multipliers. There are various techniques for minimizing roundoff error and instability. In computer jargon, an arithmetic operation (+, –, *, ÷) on two real numbers is called a flop, which is an acronym for "floating-point operation." While executing each arithmetic operation takes different time for a computer (multiplication being the fastest and division being the slowest), we need to determine the cost in flops for a computer processor to perform Gaussian elimination.

Consider a linear system of equations, written in vector form Ax = b, of m equations in n unknowns to be solved by Gaussian elimination. So in the above equation, A is the given m×n matrix and b is the known m column vector. We build the m×(n+1) augmented matrix B = [A | b]. Assuming that we perform Gaussian elimination without exchanging rows and pivots are all situated in appropriate sequential rows, on the first step we need to eliminate entries marked by ⊗ in the augmented matrix: ⊙

where ♦ denotes the pivot's position, ⊗ denotes element to be eliminates, and • denotes a quantity that is not being computed. To eliminate the first term in position (2,1), we need to make n+1 multiplications (by the value in this position) and the same number of divisions (by the value at the first pivot) and finally make n+1 subtractions. So the total number of operations will be where M stands for multiplication, S for subtraction, and D for division. Since we have m rows, we need to repeat the same number of arithmetic operations m-1 times. Therefore, using Now in the second step, we eliminate entries in the second column below the pivot: where × denotes a quantity that is being computed. To achieve this, we need to make Proceeding in a similar manner, we need to make To find the explicit expression for the the sum, we use the famous formulas (see V. Dobrushkin's book for their derivations): Then we get When n = m, we have

 

References