gepp.py

# -*- coding: utf-8 -*-
"""GEPP.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/16c-OCuJG8megZDBXh4T09aNH98-hFjGT
"""

import numpy as np

"""##### Utility"""

def swap(B,swaps):
  A=np.copy(B)
  n=len(swaps)
  for i in range(n):
    A[[i,swaps[i]],:]=A[[swaps[i],i],:]
  return A

def split(A):
  U=np.zeros((len(A),len(A)))
  L=np.eye(len(A))
  for i in range(len(A)):
    U[i,i:]=A[i,i:]
    L[i+1:,i]=A[i+1:,i]
  return L, U

def myLU(B):
  A = np.copy(B)
  p=np.zeros(len(A)-1).astype(np.intc) #indices are int
  for i in range(len(A)):
    row = np.argmax(np.absolute(A[i:,i])) + i #find the max row
    if row != i:
      A[[i,row],:]=A[[row,i],:] # swap the two rows
    if i < len(p):
      p[i] = row #populate p vector as in Problem 1
    A[(i+1):,i]=A[(i+1):,i]/A[i,i]
    A[(i+1):,(i+1):]-=np.outer(A[(i+1):,i], A[i,(i+1):])
  L, U = split(A) #use the split method from Lab1 to split A into L, U
  return L, U, p

# Perform Row-Oriented Forward-Substitution for Lower-Tri System Ax=b
# Single for-loop
def lowerfSub(A,b):
  n=len(A) # get the dimension of A in 0-indexing
  x=np.zeros(n)
  x[0] = b[0]/A[0][0] # the first entry
  for i in range(1,n):
    x[i]=(b[i]-np.dot(A[i,:], x))/A[i][i]
  return x

# Example of Row-Oriented Back-Substituion to solve Upper-Tri System Ax=b
def upperbSub(A,b):
  n=len(A)
  x=np.zeros(n)
  x[n-1]=b[n-1]/A[n-1,n-1]
  for i in range(1,n):
    x[n-1-i]=1/A[n-1-i,n-1-i]*(b[n-1-i]-np.dot(A[n-1-i,n-i:],x[n-i:]))
  return x

# Implemented swap() to permute a vector
def swapfV(b,swaps):
  a=np.copy(b)
  n=len(swaps)
  for i in range(n):
    if swaps[i]!=i:
      temp = a[i]
      a[i]=a[swaps[i]]
      a[swaps[i]] = temp
  return a

"""### LU-PA Decomposition"""

def myLU(B):
  A = np.copy(B)
  p=np.zeros(len(A)-1).astype(np.intc) #indices are int
  for i in range(len(A)):
    row = np.argmax(np.absolute(A[i:,i])) + i #find the max row
    if row != i:
      A[[i,row],:]=A[[row,i],:] # swap the two rows
    if i < len(p):
      p[i] = row #populate p vector as in Problem 1
    A[(i+1):,i]=A[(i+1):,i]/A[i,i]
    A[(i+1):,(i+1):]-=np.outer(A[(i+1):,i], A[i,(i+1):])
  L, U = split(A) #use the split method from Lab1 to split A into L, U
  return L, U, p

"""### Gaussian Elimination with Partial Pivoting"""

def mySolve(A, b):
  x = x=np.zeros(len(b))
  L, U, p = myLU(A)
  newB = swapfV(b, p)
  y = lowerfSub(L, newB)
  x = upperbSub(U, y)
  return x

"""### Testing"""

# LU-PA Decomposition
for i in range(10):
  A=np.random.rand(20,20)
  L, U, p= myLU(A)
  print(np.allclose(L@U, swap(A, p)))

# GEPP
for i in range(10):
  A=np.random.rand(20,20)
  b=np.random.rand(20)
  x=mySolve(A,b)
  print(np.allclose(A@x,b)) # test if the result is correct
  print(np.max(np.abs(np.linalg.solve(A,b)-mySolve(A,b)))) # test accuracy

"""### Note
GEPP(myLU()) is more stable compared to outerGEWP() on large-scale linear systems. 
"""