Created
November 16, 2013 17:56
-
-
Save LemonPi/7503270 to your computer and use it in GitHub Desktop.
Reduced normal form in python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Naive implementation of reduce normal form with some helper functions | |
from fractions import * | |
# helper functions | |
def row_sub(reduceby, reduceto, index): | |
""" | |
Take row to reduce and row to reduce by with the index of the element to | |
reduce to 0. Assume reduce by has value 1 in the index of reduceto. | |
""" | |
row_merged = [] | |
for i in range(len(reduceby)): # for each number in reduceby | |
# subtract each by reduceby * whatever is above reduceby's leading 1 | |
row_merged.append(reduceto[i] - reduceby[i] * reduceto[index]) | |
return row_merged | |
def row_reduce(row): | |
""" | |
Reduces row to lead with 1. | |
""" | |
# near_zero = 10 ** (-10) # threshold for rounding errors | |
for i in range(len(row)): | |
if abs(row[i]) > 0: # first non-zero element | |
row[:] = [x / row[i] for x in row] | |
for x in range(len(row)): | |
row[x] = round(row[x], 15) | |
break | |
def augment(mat1, mat2): | |
""" | |
Return the augmentation of mat2 onto mat1. | |
""" | |
for i in range(len(mat1)): | |
mat1[i] += mat2[i] | |
# main RNF function | |
def rnf(mat): | |
""" | |
Return the reduced normal form of a matrix. No pivoting is used. | |
""" | |
for r in range(len(mat)): # convert each mat element to decimal, exact value | |
for c in range(len(mat[0])): | |
mat[r][c] = Fraction('{}'.format(mat[r][c])) | |
mat.sort(reverse = True) # leading 0's naturally fall down | |
for row in range(len(mat)): # forward step | |
row_reduce(mat[row]) # to get leading 1 | |
leading_one = 0 # need index of leading one for reverse, could have 0's | |
for i in range(len(mat[0])): | |
if abs(mat[row][i]) > 0: | |
leading_one = i | |
break | |
for rowbelow in range(row + 1, len(mat)): # all rows below row | |
mat[rowbelow] = row_sub(mat[row], mat[rowbelow], leading_one) # 0 column | |
for row in reversed(range(len(mat))): # reverse step | |
leading_one = 0 # need index of leading one for reverse, could have 0's | |
for i in range(len(mat[0])): | |
if abs(mat[row][i]) > 0: | |
leading_one = i | |
break | |
for rowabove in reversed(range(row)): # all rows above row | |
mat[rowabove] = row_sub(mat[row], mat[rowabove], leading_one) | |
for r in range(len(mat)): # convert each element back to float | |
for c in range(len(mat[0])): | |
mat[r][c] = float(mat[r][c]) | |
return mat |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment