Linear Algebra - (Gaussian|Common) Elimination

> Linear Algebra

1 - Origin

Method illustrated in Chapter Eight of a Chinese text, The Nine Chapters on the Mathematical Art, that was written roughly two thousand years ago. Rediscovered in Europe by Isaac Newton (England) and Michel Rolle (France). Gauss called the method eliminiationem vulgarem (“common elimination”). Gauss adapted the method for another problem and developed notation.

2 - Use case

Advertising

2.1 - basis

Finding a basis for the span of given vectors (and then for rank and therefore for testing linear dependence.

To find a basis for the row space of a matrix A, iteratively transform A into a matrix B

Key idea: keep track of transformations performed in putting matrix in echelon form.

Computation

  • sort the rows according to position of leftmost nonzero entry (first choose a row with a nonzero in first column, then choose a row with a nonzero in second column, …)
# To handle Vecs with arbitrary D, we must order the domain (here by hash)
col_label_list = sorted(matrixRowList[0].D, key=hash)
for c in col_label_list:
    rows_with_nonzero = [r for r in rows_left if rowlist[r][c] != 0]
    # if we don't have a vector with a nonzero on this position, pass
    if rows with nonzero != []:
        # each row is only used once as a pivot-row,
        pivot = rows_with_nonzero[0]
 
        # If we have more than one vector with a non-zero on this position
        # then (addition|substract) them in order to push the zero at the right side
        if len(rows_with_nonzero) > 1:
            # over R: add suitable multiple of rowlist[pivot] to each row in rows with nonzero[1:]
            # over Gf2: add row pivot to the others
            pivot = rows_with_nonzero[0]
            for r in rows_with_nonzero[1:]:
                multiplier = rowlist[r][c]/rowlist[pivot][c]
                rowlist[r] -= multiplier * rowlist[pivot]
 
 
        # Append the pivot in the list in echelon form
        new_rowlist.append(rowlist[pivot])
        # Remove the pivot row from the origin list
        rows_left.remove(pivot)

2.1.1 - round-off error

As the computation use floating-point numbers, the Gaussian elimination method got the wrong answer due to round-off error.

These problems can be mitigated by choosing the pivot element carefully:

  • Partial pivoting: Among rows with non-zero entries in column c, choose row with entry having largest absolute value.
  • Complete pivoting: Instead of selecting order of columns beforehand, in each iteration choose column to maximize absolute value of pivot element.
Advertising
linear_algebra/gaussian_elimination.txt · Last modified: 2013/08/24 19:23 by gerardnico