Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Have you done PA=LU factorization?

  1. Feb 15, 2015 #1
    I'm trying to figure out what this quote means and what our strategy is just looking at the matrix what kind of permutations we need to do.

    Quotes: "The first permutation step is trivial (since the pivot element 10 is already the largest). The corresponding permutation matrix is the identity, and we need not write it down. The first elimination step is:"

    Why do we need to do permutations at all? How do we know by looking?

    upload_2015-2-15_4-27-42.png

    https://www.student.cs.uwaterloo.ca/~cs370/notes/LUExample2.pdf
     
  2. jcsd
  3. Feb 15, 2015 #2
    So as a start, why do we care at all that 10 is the largest?
     
  4. Feb 15, 2015 #3

    lurflurf

    User Avatar
    Homework Helper

    Dividing by small numbers is bad. We do permutations so we may divide by a big number. In step 1 10 is already the biggest available. In step 2 5/2 is larger than 1/10 so we do a permutation so we can divide by 5/2 instead of 1/10.
     
  5. Feb 15, 2015 #4

    statdad

    User Avatar
    Homework Helper

    "... what kind of permutations we need to do."
    Are you referring to what permutations have to do in this setting (I may be grossly misunderstanding the thrust of your question)? If so, they are referring to rearranging (permuting is rearranging) the rows in order to bring a more desirable value to the pivot location.

    If that wasn't your question - apologies.
     
  6. Feb 15, 2015 #5
    1. Why is dividing by big numbers bad? Aside from inconvenient I don't see why big number necessarily necessitates row swaps

    2. 10 is already the biggest available" <- available of _____ ? Of the numbers down the column

    I'm a bit confused about P

    Given a matrix A, does it always have a fixed P for LU factorization? Couldn't we have multiple different P's depending on how we RREF the problem ?
     
  7. Feb 15, 2015 #6

    statdad

    User Avatar
    Homework Helper

    "Why is dividing by big numbers bad?"
    Read again - dividing by small numbers is to be avoided

    "Of the numbers down the column" Yes

    "Given a matrix A, does it always have a fixed P for LU factorization? Couldn't we have multiple different P's depending on how we RREF the problem"
    Yes, you can: each time rows are swapped there is another P: take a look here:
    http://staff.imsa.edu/~fogel/LinAlg/PDF/17 Permutations and Row Swaps.pdf
     
  8. Feb 15, 2015 #7
    ""Why is dividing by big numbers bad?"
    Read again - dividing by small numbers is to be avoided"

    Yup I read that the first time. Now - why do we want this or even if we want it why is it necessary? Maybe it is obvious to you

    Aside from inconvenient I don't see why big number necessarily necessitates row swaps


    ____________

    upload_2015-2-15_20-38-44.png

    1. Why does L have 1's down the diagonal? Couldn't it have anything down the diagonal?

    2. Is P is not unique, then LU is not unique right. So how have linear algebra people been grading tests all these years? They can't enumerate all possible LU's can they or take the time to manually multiply every studetn's answer out can they?
     

    Attached Files:

  9. Feb 15, 2015 #8

    statdad

    User Avatar
    Homework Helper

  10. Feb 16, 2015 #9
    ""Why is dividing by big numbers bad?"
    Read again - dividing by small numbers is to be avoided"

    Yup I read that the first time. Now - why do we want this or even if we want it why is it necessary? Maybe it is obvious to you

    not in wikipedia
     
  11. Feb 16, 2015 #10

    lurflurf

    User Avatar
    Homework Helper

    The wikipedia gives a classic example of the need for pivoting consider two systems
    $$\left[ \begin{array}{cc|c}
    0.00300 & 59.14 & 59.17 \\
    5.291 & -6.130 & 46.78 \\
    \end{array} \right]
    \\
    \left[ \begin{array}{cc|c}
    5.291 & -6.130 & 46.78 \\
    0.00300 & 59.14 & 59.17 \\
    \end{array} \right]$$
    If we work with 4 digits and no pivoting we get for the first system
    {9873.3,4}
    for the second
    {10.00,1.000}
    We see the two systems should have the same solution, but the first one came out wrong due to dividing by small numbers.
    So we decide to divide by the largest number available.

    Edit: I got something different when I checked the wikipedia result, I probably added wrong somewhere.
     
    Last edited: Feb 16, 2015
  12. Feb 16, 2015 #11

    statdad

    User Avatar
    Homework Helper

    Why do we want the LU decomposition? As one example - look up LU and solving systems of linear equations
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Have you done PA=LU factorization?
  1. LU Split (Replies: 8)

  2. LU Decomposition (Replies: 1)

Loading...