Linear Algebra - (Gaussian|Common) Elimination

Card Puncher Data Processing

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.

Use case

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)

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.





Discover More
Card Puncher Data Processing
Linear Algebra - Authentication Challenge

Password Authentication challenge Password is an n-vector over GF(2) Send: Computer sends random n-vector a Response: Human sends back . Repeated until Computer is convinced that Human knowns...
Card Puncher Data Processing
Linear Algebra - Closest point in higher dimension than a plane

Solving closest point in the span of many vectors Goal: An algorithm that, given a vector b and vectors v1, . . . , vn, finds the vector in Span {v1, . . . , vn} that is closest to b. Special case:...
Card Puncher Data Processing
Linear Algebra - Row Space of a matrix

Row space If a matrix is in echelon form, the nonzero rows form a basis for the row space. Applying elementary row-addition operations does not change the row space. To find basis for row...



Share this page:
Follow us:
Task Runner