Linear Algebra--Direct Methods

• Types of linear solvers
  • What are the two main methods of solving linear systems?
• If you have a system with 10,000 equation, would you use a direct method?
• Gauss elimination
  • Algorithm
    • What are the two parts and how do they work?
  • Cost
    • How does the computational cost scale with the number of unknowns $n$?
    • If you double the number of equations in a linear system, by what factor does the computational cost change for the two portions of the algorithm?
    • Can you explain why in terms of what is happening with the algorithm?
  • Pivoting
    • Why is it used?
    • There are two main types, which do we use?
    • How is it done conceptually? How is it actually implemented?
  • Scaling
    • Why is it important to use scaling when doing pivoting?
• LU Decomposition
  • How is it related to Gauss Elimination?
  • When is LU decomposition more obviously preferred to Gauss Elimination?
• Thomas algorithm
  • Why don’t we use pivoting and scaling with the Thomas algorithm?
  • If you double the number of equations in a tridiagonal linear system, by what factor does the computational cost change?

Fill in the following psuedo code

• Assume array indexes start at zero.
• Assume loops start and end on the values listed (unlike range).
• This is something to reason through, not something to memorize!

loop over columns:  do k= __, __
loop over rows:         do i= __, __
    find fac:               fac= a(__,__)/a(__,__)
    loop row elements:      do j=  ,
                                a(__,__)=a(__,__) - fac*a(__,__)
                            end
    do b vector             b(__) = b(__) - fac*b(__)
                        end
                    end