Math 110 Fall 05 Lectures notes 20 Oct 14 Friday We will cover the contents of Chapter 3 slightly differently than the textbook showing how to compute range A rank A nullspace A nullity A A 1 if it exists solve Ax b determine if there are no solutions 1 solution or infinitely many solutions all by computing a single matrix factorization of A called the LU factorization or LU decomposition which is a formula for A as product of much simpler matrices The algorithm for computing this factorization is just Gaussian elimination where we keep track of all the elementary matrix operations we do reordering rows and or columns adding a multiply of one row to another multiplying a row or column by a scalar as a product of simple matrices When you use computer software to do matrix operations it will return your answer as a product of simpler matrices much like the ones we show here LU decomposition plays an important role in government high technology policy the largest computers in the world called supercomputers are regularly measured by how fast they can solve Ax b using LU decomposition on very large matrices with the ratings appearing on the web site www top500 org This web site keeps track of the 500 fastest computers anywhere in the world at least those not at secret government sites For example as of June 2005 the top computer was an IBM Blue Gene L consisting of 65 536 parallel processors The machine solved a linear system of n 1 277 951 equations using the LU decomposition algorithm described below at a speed of 136 8 Teraflops that is 136 8 trillion 136 8 x 10 12 arithmetic operations per second Since the number of arithmetic operations required by the algorithm will turn out to be about 2 3 n 3 the time required to solve this single linear system was 2 3 1 277 951 3 136 8x10 12 10161 seconds 2 8 hours Recall that multiplying 2 matrices takes about 2n 3 operations 3 times more operations A few years ago the fastest machine on the Top 500 list was the NEC Earth Simulator which ran at a speed of 35 9 Teraflops as fast as the next four machines combined This caught the attention of parts 1 of the US government responsible for national security because NEC is a Japanese company and one national security goal of the US government is to have better technology including faster computers than anyone else in the world This is because these computers are used for breaking secret codes designing weapons and other national security purposes Indeed the largest computers in the US have been built for these purposes for decades The speed of the NEC machine led to a flurry of government studies and reports to analyze the situation for example www sc doe gov ascr FOSCfinalreport pdf More aspects of implementing linear algebra algorithms on parallel machines are discussed in the course CS267 see www cs berkeley edu demmel cs267 Spr05 One of the most widely used software packages for solving linear algebra problems is called LAPACK its parallel version is ScaLAPACK for example it is used within Matlab This software was produced in a joint project between UC Berkeley the University of Tennessee and other groups We have recently been funded to produce a new version See www netlib org lapack for the current software Ex Suppose L is square and lower triangular L 1 0 0 1 2 0 3 1 3 Then we can solve Lx b for x given any b by substitution Solve 1 x 1 b 1 for x 1 Solve 1 x 1 2 x 2 b 2 for x 2 Solve 3 x 1 1 x 2 3 x 3 b 3 for x 3 As long as each L ii is nonzero so we can divide by it we can solve any Lx b for x and get a unique answer In particular the only solution of Lx 0 is x 0 so that L is one to one This implies that L is invertible We can compute L 1 by solving for it one column at a time Let X L 1 so L X I and e j j th standard basis vector so L X e j I e j or L X e j e j or L column j of X e j so we can solve for X L 1 one column at a time Ex Suppose U is square upper triangular and each U ii is nonzero Then we can similarly solve any U x b for a unique x given b by substitution solving first for x n then x n 1 and so on We can also compute U 1 as above 2 Ex Suppose A L U where L and U are n by n and nonsingular Then A is invertible why and A 1 L U 1 U 1 L 1 and solving A x b for x given b means computing x A 1 b U 1 L 1 b U 1 L 1 b by associativity U 1 y where we compute y L 1 b i e solve L y b by substitution where we finally compute x U 1 y i e solve U x y by substitution again In other words if we know A L U where L and U are invertible triangular matrices we can solve A x b by 2 steps 1 solve L y b by substitution 2 solve U x y by substitution If we want to compute A 1 we use the same idea as above solving A X I for X one column of X at a time Stop Ask Suppose A U L where U and L are n by n and invertible How do we solve A x b It may seem strange to expect to know A in the form A L U but this is in fact exactly what Gaussian elimination applied to A computes Ex A 3 1 2 6 0 10 3 3 17 To apply Gaussian elimination we do the following for i 1 to n 1 3 1 2 in this case subtract multiples of row i from rows i 1 through n in order to zero out A below the diagonal Subtract 2 row 1 from row 2 Subtract 1 row 1 from row 3 yielding A 3 1 2 0 2 6 0 4 15 Subtract 2 row 2 from row 2 yielding A 3 1 2 0 2 6 0 0 3 Note that A U is upper triangular Let s take the multipliers we computed and put them into a lower triangular matrix L 3 L 1 0 0 2 1 0 1 2 1 Then we can confirm that L U A We will see that this is true in general as long as we never get a 0 on the diagonal ASK WAIT What happens if A 11 0 What happens at any point if some diagonal entry 0 If A is m by …