Gaussian elimination without result for acceleration

by

When you perform a Gaussian elimination, you swap rows and repeatedly subtract a multiple of one row from another to produce an upper triangular form.

When you do this on a system of equations or an “augmented matrix”, you do not use any information from the result column. The decisions about which rows to swap and which to subtract with what multiplier would be exactly the same no matter what numbers are in the result column.

Because the “result column” is not used, you can perform the same procedure on a normal square matrix. Since the operations don’t change the determinant (if you negate one row whenever you swap), you end up with an upper triangular matrix with the same det as the original.

The MIT author calls a function lu to do this in the example near the start. This does L-U decomposition on the matrix, which returns the Gaussian-eliminated matrix in the ‘U’ part: https://en.wikipedia.org/wiki/LU_decomposition.

L-U decomposition is pretty cool. It’s like doing Gaussian elimination to solve all systems with the same “matrix part” all at once, which again you can do because the process doesn’t need to see the result column at all.

Starting with a matrix M, you get L and U such that LU = M. That means, if you want to solve:

Mx = y

… where (x an y are column vectors), you have:

LUx = y

Solve Lv=y, which is easy (just substitution) because L is lower-triangular. Then you have:

Ux = v

… which is easy to solve because U is upper-triangular.

More Related Contents:

  1. The most efficient way to implement an integer based power function pow(int, int)
  2. Power by squaring for negative exponents
  3. Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?
  4. How do you print the EXACT value of a floating point number?
  5. C – How to implement Set data structure?
  6. signed and unsigned arithmetic implementation on x86
  7. A possible algorithm for determining whether two strings are anagrams of one another? [closed]
  8. Algorithm to pick values from array that sum closest to a target value?
  9. Recursive and non-recursive traversal of three degree tree
  10. how to show time performance for merge sort? [closed]
  11. Sum of the all the numbers between a and b [closed]
  12. How to check if a number is a power of 2
  13. What’s the difference between “mod” and “remainder”?
  14. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  15. All Possible Combinations of a list of Values
  16. How to reverse a singly linked list using only two pointers?
  17. Unique random number generation in an integer array [duplicate]
  18. Rounding integer division (instead of truncating)
  19. Algorithm to find which numbers from a list of size n sum to another number
  20. “undefined reference to `pow'” even with math.h and the library link -lm [duplicate]
  21. Program to print permutations of given elements [closed]
  22. sine wave that slowly ramps up frequency from f1 to f2 for a given time
  23. Why does gdb evaluate sqrt(3) to 0?
  24. Inverting a 4×4 matrix
  25. To the power of in C? [duplicate]
  26. Find maximum of three number in C without using conditional statement and ternary operator
  27. Algorithm to find all the exact divisors of a given integer
  28. How does this bitwise operation check for a power of 2?
  29. Which is better way to calculate nCr
  30. Evaluate Mathematical Function from String [closed]

Leave a Comment